Problem:
A token starts at the point (0,0) of an xy-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of ∣y∣=∣x∣ is nm, where m and n are relatively prime positive integers. Find m+n.
Solution:
By symmetry, the same number of sequences of moves will end in each of the four quadrants of the coordinate plane. Let r,l,u, and d represent the number of moves made in the positive x-direction, the negative x-direction, the positive y-direction, and the negative y-direction, respectively.
The token ends at (3,3) if and only if (r,l,u,d)=(3,0,3,0). The number of such sequences of moves is 3!⋅0!⋅3!⋅0!6!=20.
The token ends at (2,2) if and only if (r,l,u,d)=(2,0,3,1) or (3,1,2,0). The number of such sequences of moves is 2⋅2!⋅0!⋅3!⋅1!6!=120.
The token ends at (1,1) if and only if (r,l,u,d)=(1,0,3,2),(2,1,2,1), or (3,2,1,0). The number of such sequences of moves is 2⋅1!⋅0!⋅3!⋅2!6!+2!⋅1!⋅2!⋅1!6!=300.
The token ends at (0,0) if and only if (r,l,u,d)=(0,0,3,3),(1,1,2,2),(2,2,1,1), or (3,3,0,0). The number of such sequences of moves is 2(0!⋅0!⋅3!⋅3!6!+1!⋅1!⋅2!⋅2!6!)=400.
Thus the number of sequence of moves that end on the graph of ∣y∣=∣x∣ is 400+4(20+120+300)=2160. The total number of six-move sequences possible is 46, so the sequence ends on the graph of ∣y∣=∣x∣ with probability 462160=44135=256135. The requested sum is 135+256=391.
The problems on this page are the property of the MAA's American Mathematics Competitions