2005 AIME I Problems/Problem 13
A particle moves in the Cartesian plane according to the following rules:
- From any lattice point the particle may only move to or
- There are no right angle turns in the particle's path.
How many different paths can the particle take from to ?
The length of the path (the number of times the particle moves) can range from to ; notice that gives the number of diagonals. Let represent a move to the right, represent a move upwards, and to be a move that is diagonal. Casework upon the number of diagonal moves:
- Case : It is easy to see only cases.
- Case : There are two diagonals. We need to generate a string with 's, 's, and 's such that no two 's or 's are adjacent. The 's split the string into three sections (): by the Pigeonhole principle all of at least one of the two letters must be all together (i.e., stay in a row).
- If both and stay together, then there are ways.
- If either or splits, then there are places to put the letter that splits, which has possibilities. The remaining letter must divide into in one section and in the next, giving ways. This totals ways.
- Case : Now 's, 's, and 's, so the string is divided into partitions ().
- If the 's and 's stay together, then there are places to put them.
- If one of them splits and the other stays together, then there are places to put them, and ways to pick which splits, giving ways.
- If both groups split, then there are ways to arrange them. These add up to ways.
- Case : Now , , 's (). There are places to put , places to put , giving ways.
- Case : It is easy to see only case.
Together, these add up to .
Another possibility is to use block-walking and recursion: for each vertex, the number of ways to reach it is , where is the number of ways to reach the vertex from the left (without having come to that vertex (the one on the left) from below), is the number of ways to reach the vertex from the vertex diagonally down and left, and is the number of ways to reach the vertex from below (without having come to that vertex (the one below) from the left).
Assign to each point the triplet . Let . Let all lattice points that contain exactly one negative coordinate be assigned to . This leaves the lattice points of the first quadrant, the positive parts of the and axes, and the origin unassigned. As a seed, assign to . (We will see how this correlates with the problem.) Then define for each lattice point its triplet thus:
It is evident that is the number of ways to reach from . Therefore we compute vertex by vertex the triplets with . Finally, after simple but tedious calculations, we find that , so .
|2005 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|