Maths Olympiad Prep

Library / /1268 of 1394

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:

Sophie is at (0,0)(0,0) on a coordinate grid and would like to get to (3,3)(3,3). If Sophie is at (x,y)(x,y), in a single step she can move to one of (x+1,y)(x + 1, y), (x,y+1)(x, y + 1), (x1,y+1)(x - 1, y + 1), or (x+1,y1)(x + 1, y - 1). She cannot revisit any points along her path, and neither her xx-coordinate nor her yy-coordinate can ever be less than 00 or greater than 33. Compute the number of ways for Sophie to reach (3,3)(3,3).

Solution

Solution:

Let a lateral move refer to one which is either up or right. Then the lateral moves are the only ones which increase Kelvin's sum of coordinates by 11, while all other moves do not change the sum, so Kelvin must make 66 of them, one to increase this sum from ii to i+1i + 1 for each i[0,5]i \in [0, 5].

Figure 1

We claim there exists a unique path corresponding to each set of 66 lateral moves chosen in this way. Indeed, the diagonal moves allow Kelvin to get from any point on x+y=ix + y = i to any second point on x+y=ix + y = i in exactly one way.

Observe that when i2i \leq 2, the number of lateral moves that increase the sum of coordinates from ii to i+1i + 1 is 2i2i, as is the number that increase it from 5i5 - i to 6i6 - i. Thus the answer is 246642=23042 \cdot 4 \cdot 6 \cdot 6 \cdot 4 \cdot 2 = \lfloor 2304 \rfloor.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.