2005 AIME I Problems/Problem 13

From AoPSWiki

Problem

A particle moves in the Cartesian Plane according to the following rules:

From any lattice point $(a,b),$ the particle may only move to $(a+1,b), (a,b+1),$ or $(a+1,b+1).$
There are no right angle turns in the particle's path.

How many different paths can the particle take from $(0,0)$ to $(5,5)$ ?

Solution

Solution 1

The length of the path (the number of times the particle moves) can range from $l = 5$ to $9$ ; notice that $d = 10-l$ gives the number of diagonals. Let $R$ represent a move to the right, $U$ represent a move upwards, and $D$ to be a move that is diagonal. Casework upon the number of diagonal moves:

Case $d = 1$ : It is easy to see only $2$ cases.
Case $d = 2$ : There are two diagonals. We need to generate a string with $3$ $R$ 's, $3$ $U$ 's, and $2$ $D$ 's such that no two $R$ 's or $U$ 's are adjacent. The $D$ 's split the string into three sections ( $-D-D-$ ): 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 $R$ and $U$ stay together, then there are $3 \cdot 2=6$ ways.

If either $R$ or $U$ splits, then there are $3$ places to put the letter that splits, which has $2$ possibilities. The remaining letter must divide into $2$ in one section and $1$ in the next, giving $2$ ways. This totals $6 + 3\cdot 2\cdot 2 = 18$ ways.

Case $d = 3$ : Now $2$ $R$ 's, $2$ $U$ 's, and $3$ $D$ 's, so the string is divided into $4$ partitions ( $-D-D-D-$ ).

If the $R$ 's and $U$ 's stay together, then there are $4 \cdot 3 = 12$ places to put them.

If one of them splits and the other stays together, then there are $4 \cdot {3\choose 2}$ places to put them, and $2$ ways to pick which splits, giving $4 \cdot 3 \cdot 2 = 24$ ways.

If both groups split, then there are ${4\choose 2}=6$ ways to arrange them. These add up to $12 + 24 + 6 = 42$ ways.

Case $d = 4$ : Now $1$ $R$ , $1$ $U$ , $4$ $D$ 's ( $-D-D-D-D-$ ). There are $5$ places to put $R$ , $4$ places to put $U$ , giving $20$ ways.
Case $d = 5$ : It is easy to see only $1$ case.

Together, these add up to $2 + 18 + 42 + 20 + 1 = \boxed{83}$ .

Solution 2

Another possibility is to use block-walking and recursion: for each vertex, the number of ways to reach it is $a + b + c$ , where $a$ 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), $b$ is the number of ways to reach the vertex from the vertex diagonally down and left, and $c$ 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 $(i,j)$ the triplet $(a_{i,j}, b_{i,j}, c_{i,j})$ . Let $s(i,j) = a_{i,j}+ b_{i,j}+ c_{i,j}$ . Let all lattice points that contain exactly one negative coordinate be assigned to $(0,0,0)$ . This leaves the lattice points of the first quadrant, the positive parts of the $x$ and $y$ axes, and the origin unassigned. As a seed, assign to $(0,1,0)$ . (We will see how this correlates with the problem.) Then define for each lattice point $(i,j)$ its triplet thus:

$a_{i,j} = s(i-1,j) - c_{i-1,j}$

$b_{i,j} = s(i-1,j-1)$

$c_{i,j} = s(i,j-1) - a_{i,j-1}$

It is evident that $s(i,j)$ is the number of ways to reach $(i,j)$ from $(0,0)$ . Therefore we compute vertex by vertex the triplets $(a_{i,j}, b_{i,j}, c_{i,j})$ with $0 \leq i, j \leq 5$ . Finally, after simple but tedious calculations, we find that $(a_{5,5}, b_{5,5}, c_{5,5}) = (28,27,28)$ , so $s(i,j)=28+27+28 = \boxed{83}$ .

[Note:Someone may wish to add an image.] This solution is incomplete. You can help us out by completing it.

2005 AIME I (Problems • Resources)
Preceded by Problem 12	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox