AIME 2014 I · 第 11 题

Solution 1 (Slick Solution)

Perform the coordinate transformation $(x, y)\rightarrow (x+y, x-y)$. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors $\langle 1, -1 \rangle$, $\langle 1, 1 \rangle$, $\langle -1, -1 \rangle$, $\langle -1, 1 \rangle$ respectively. Moreover, the transformation takes the equation $|y| = |x|$ to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of $UUUDDD$, which is just $\binom63 = 20$. The probability of any of these sequences happening is $\left(\frac12\right)^6$. Thus, the probability of ending on the x axis is $\frac{20}{2^6}$. Similarly, the probability of ending on the y axis is the same.

However, we overcount exactly one case: ending at $(0, 0)$. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply $\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}$. Using PIE, the total probability is $\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}$, giving an answer of $\boxed{391}$.

~sampai7

Solution 2 (Casework)

We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is $4^6$, or $4096$. There are 4 possible cases that land along the line $y = x$: $x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;$ or $x = y = 0$. We will count the number of ways to end up at $(1,1), (2,2),$ and $(3,3)$, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at $(0,0)$.

• Case 1: The token ends at $(3, 3)$. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence $RRRUUU$, which is ${6\choose 3} = 20.$

• Case 2: The token ends at $(2,2)$. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences $RRRLUU$ and $UUUDRR$, both of which are ${6\choose 1}{5\choose 2} = 60$, for a total of $120$ possibilities.

• Case 3: The token ends at $(1,1)$. In order for the token to end up here, it could have had:

  • 1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence $RUUUDD$ is ${6\choose 1}{5\choose 2} = 60.$
  • 1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence $URRRLL$ is ${6\choose 1}{5\choose 2} = 60.$
  • 2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence $UUDRRL$ is ${6\choose 1}{5\choose 1}{4\choose 2} = 180.$

Thus, the total number of ways to end up at $(1,1)$ is $300$.

• Case 4: The token ends at $(0,0)$. In order for the token to end up here, it could have had:
  • 3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence $RRRLLL$ is ${6\choose 3} = 20.$
  • 3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence $UUUDDD$ is ${6\choose 3} = 20.$
  • 1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence $RLUUDD$ is ${6\choose 1}{5\choose 1}{4\choose 2} = 180.$
  • 1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence $RRLLUD$ is ${6\choose 1}{5\choose 1}{4\choose 2} = 180.$

Thus, the total number of ways to end up at $(0,0)$ is $400$.

Adding these cases together, we get that the total number of ways to end up on $y = x$ is $4(20 + 120 + 300) + 400 = 2160$. Thus, our probability is $\frac{2160}{4096}$. When this fraction is fully reduced, it is $\frac{135}{256}$, so our answer is $135 + 256 = \boxed{391}.$

Solution 3 (Casework)

We split this into cases by making a chart. In each row, the entries $(\pm1)$ before the dividing line represent the right or left steps (without regard to order), and the entries after the dividing line represent the up or down steps (again, without regard to order). This table only represents the cases where the ending position $(x,y)$ satisfies $x=y$.

$$\begin{array}{ccccccccccccl} \multicolumn{5}{c}{R (+)\qquad L (-)}& |&\multicolumn{5}{c}{U (+)\qquad D (-)}\\ +1&& +1&& +1&| & +1&& +1&& +1\\ +1&& +1&& -1& | & +1&& +1&& -1\\ +1&& -1&& -1& | & +1&& -1&& -1\\ -1 && -1&& -1& | & -1&& -1&& -1\\ \\ +1&& +1&& +1&& -1 &|& +1&& +1\\ +1&& +1&& -1 && -1 &|& +1 && -1\\ +1&& -1&& -1 && -1 &|& -1 && -1 &&(\times 2 \text{ for symmetry by swapping }R-L\text{ and }U-D)\\ \\ +1&& +1 &&+1 &&-1&& -1& |& +1\\ +1&& +1 &&-1&& -1&& -1 &|& -1&& (\times 2\text{ symmetry})\\ \\ +1&& +1 &&+1&& -1&& -1 &&-1&| & (\times2 \text{ symmetry})\\ \end{array}$$ Note that to account for the cases when $x=-y$, we can simply multiply the $U-D$ steps by $-1$, so for example, the first row would become

$$+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.$$ Therefore, we must multiply the number of possibilities in each case by $2$, except for when $x=y=0$.

Now, we compute the number of possibilities for each case. In particular, we must compute the number of $RLUD$ words, where $R$ represents $+1$ to the left of $|$, $L$ represents $-1$ to the left of $|$, $U$ represents $+1$ to the right of $|$, and $D$ represents $-1$ to the right of $|$. Using multinomials, we compute the following numbers of possibilities for each case.

$${6\choose 3}\cdot 2+ \frac{6!}{2!2!}\cdot 2 + \frac{6!}{2!2!} \cdot 2 + {6\choose 3} \cdot 2 = 2(20 + 180 + 180 + 20) = 800$$ $$\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})$$ $$\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})$$ $${6\choose 3} = 20\ (\times 2\text{ for symmetry})$$ Thus, there are $800 + 840 + 480 + 40 = 2160$ possibilities where $|x|=|y|$. Because there are $4^6$ total possibilities, the probability is $\frac{2160}{4^6} = \frac{135}{256}$, so the answer is $\boxed{391}.$

Solution 4 (States)

Denote $(x, y)_n$ the probability that starting from point $(x, y)$, the token reaches a point on the graph of $|y| = |x|$ in exactly $n$ moves. The problem asks us to find $(0, 0)_6$. We start by breaking this down:

$$(0, 0)_6 = \frac14 \cdot ((0, 1)_5 + (0, -1)_5 + (1, 0)_5 + (-1, 0)_5)$$ Notice that by symmetry, $(0, 1)_5 = (0, -1)_5 = (1, 0)_5 = (-1, 0)_5$, so the equation simplifies to

$$(0, 0)_6 = (0, 1)_5$$ We now expand $(0, 1)_5$.

$$(0, 1)_5 = \frac14 \cdot ((0, 0)_4 + (0, 2)_4 + 2(1, 1)_4)$$ First, we find $(0, 0)_4$.

$$(0, 0)_4 = (0, 1)_3$$ $$(0, 1)_3 = \frac14 \cdot ((0, 0)_2 + (0, 2)_2 + 2(1, 1)_2)$$ At this point, we can just count the possibilities to find $(0, 0)_2 = \frac34$, $(0, 2)_2 = \frac{7}{16}$, and $(1, 1)_2 = \frac58$. Therefore,

$$(0, 1)_3 = \frac14 \cdot (\frac34 + \frac{7}{16} + 2 \cdot \frac58)$$ $$(0, 1)_3 = \frac{39}{64}$$ Next, we find $(0, 2)_4$.

$$(0, 2)_4 = \frac14 \cdot ((0, 1)_3 + (0, 3)_3 + 2(1, 2)_3)$$ We already calculated $(0, 1)_3$, so we just need to find $(0, 3)_3$ and $(1, 2)_3$

$$(0, 3)_3 = \frac14 \cdot ((0, 2)_2 + (0, 4)_2 + 2(1, 3)_2)$$ $$(0, 3)_3 = \frac14 \cdot (\frac{7}{16} + 0 + 2 \cdot \frac{1}{4})$$ $$(0, 3)_3 = \frac{15}{64}$$ $$(1, 2)_3 = \frac14 \cdot ((1, 3)_2 + (1, 1)_2 + (0, 2)_2 + (2, 2)_2)$$ $$(1, 2)_3 = \frac14 \cdot (\frac14 + \frac58 + \frac{7}{16} + \frac12)$$ $$(1, 2)_3 = \frac{29}{64}$$ Therefore,

$$(0, 2)_4 = \frac14 \cdot (\frac{39}{64} + \frac{15}{64} + 2 \cdot \frac{29}{64})$$ $$(0, 2)_4 = \frac{7}{16}$$ Finally, we find $(1, 1)_4$.

$$(1, 1)_4 = \frac12 \cdot ((0, 1)_3 + (1, 2)_3)$$ $$(1, 1)_4 = \frac12 \cdot (\frac{39}{64} + \frac{29}{64})$$ $$(1, 1)_4 = \frac{17}{32}$$ Putting it all together,

$$(0, 0)_6 = (0, 1)_5 =\frac14 \cdot (\frac{39}{64} + \frac{7}{16} + 2 \cdot \frac{17}{32})$$ $$(0, 0)_6 = \frac{135}{256}$$ Thus, the answer is $135 + 256 = \boxed{391}$.

Solution 5 (Generating Functions)

For any point $(x,y)$ on the coordinate plane, we can represent it as the term $a^xb^y$. Then, moving right is equivalent to multiplying by $a$, moving left is equivalent to multiplying by $1/a$, and similarly for up/down with $b$ and $1/b$. Because, on every move, the possibilities are these four directions, and each is equally likely, each move can be represented by multiplying by $a+\frac{1}{a}+b+\frac{1}{b}$. Thus, the possibilities after $6$ moves are the same as the coefficients of $\left(a+\frac{1}{a}+b+\frac{1}{b}\right)^6$. By symmetry, we just need to find the number of ways for the token to reach $(0,0),(1,1),(2,2),\text{ and }(3,3)$. By the multinomial theorem, the coefficient of $a^3b^3$ is $\binom{6}{3,3}=20$. Similarly, the coefficient of $a^2b^2$ is $2\binom{6}{3,2,1}=120$. The coefficient of $ab$ is $\binom{6}{2,2,1,1}+2\binom{6}{3,2,1}=300$. Finally, the constant term is $2\binom{6}{2,2,1,1}+2\binom{6}{3,3}=400$. Because the total number of possibilities is $4^6$, the probability is

$$\frac{4(20+120+300)+400}{4^6}=\frac{5+30+75+25}{4^4}=\frac{135}{256},$$ and the answer is $391$. --brainiacmaniac31