In how many ways can one reach the point 3n+1?
Source: Austrian Mathematical Olympiad 2002, Part 2, D2, P2
June 25, 2011
combinatorics unsolvedcombinatorics
Problem Statement
In the net drawn below, in how many ways can one reach the point starting from the point so that the labels of the points on the way increase?[asy]
import graph; size(12cm); real lsf=0.5; pen dps=linewidth(0.7)+fontsize(10); defaultpen(dps); pen ds=black; real xmin=-4.3,xmax=12.32,ymin=-10.66,ymax=6.3; draw((1,2)--(xmax,0*xmax+2)); draw((1,0)--(xmax,0*xmax+0)); draw((0,1)--(1,2)); draw((1,0)--(0,1)); draw((1,2)--(3,0)); draw((1,0)--(3,2)); draw((3,2)--(5,0)); draw((3,0)--(5,2)); draw((5,2)--(7,0)); draw((5,0)--(7,2)); draw((7,2)--(9,0)); draw((7,0)--(9,2));
dot((1,0),linewidth(1pt)+ds); label("2",(0.96,-0.5),NE*lsf); dot((0,1),linewidth(1pt)+ds); label("1",(-0.42,0.9),NE*lsf); dot((1,2),linewidth(1pt)+ds); label("3",(0.98,2.2),NE*lsf); dot((2,1),linewidth(1pt)+ds); label("4",(1.92,1.32),NE*lsf); dot((3,2),linewidth(1pt)+ds); label("6",(2.94,2.2),NE*lsf); dot((4,1),linewidth(1pt)+ds); label("7",(3.94,1.32),NE*lsf); dot((6,1),linewidth(1pt)+ds); label("10",(5.84,1.32),NE*lsf); dot((3,0),linewidth(1pt)+ds); label("5",(2.98,-0.46),NE*lsf); dot((5,2),linewidth(1pt)+ds); label("9",(4.92,2.24),NE*lsf); dot((5,0),linewidth(1pt)+ds); label("8",(4.94,-0.42),NE*lsf); dot((8,1),linewidth(1pt)+ds); label("13",(7.88,1.34),NE*lsf); dot((7,2),linewidth(1pt)+ds); label("12",(6.8,2.26),NE*lsf); dot((7,0),linewidth(1pt)+ds); label("11",(6.88,-0.38),NE*lsf);
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
[/asy]