Maths Olympiad Prep

Library / /1298 of 1394

, 2019

Combinatorics Difficulty 6.0 National Olympiad Prove it United States

Problem:

Contessa is taking a random lattice walk in the plane, starting at (1,1)(1,1). (In a random lattice walk, one moves up, down, left, or right 1 unit with equal probability at each step.) If she lands on a point of the form (6m,6n)(6m, 6n) for m,nZm, n \in \mathbb{Z}, she ascends to heaven, but if she lands on a point of the form (6m+3,6n+3)(6m+3, 6n+3) for m,nZm, n \in \mathbb{Z}, she descends to hell. What is the probability that she ascends to heaven?

Solution

Solution:

Let P(m,n)P(m, n) be the probability that she ascends to heaven from point (m,n)(m, n). Then P(6m,6n)=1P(6m, 6n) = 1 and P(6m+3,6n+3)=0P(6m+3, 6n+3) = 0 for all integers m,nZm, n \in \mathbb{Z}. At all other points,
4P(m,n)=P(m1,n)+P(m+1,n)+P(m,n1)+P(m,n+1) 4P(m, n) = P(m-1, n) + P(m+1, n) + P(m, n-1) + P(m, n+1)
This gives an infinite system of equations. However, we can apply symmetry arguments to cut down the number of variables to something more manageable. We have P(m,n)=P(m+6a,n+6b)P(m, n) = P(m+6a, n+6b) for a,bZa, b \in \mathbb{Z}, and P(m,n)=P(n,m)P(m, n) = P(n, m), and P(m,n)=P(m,n)P(m, n) = P(-m, n), and P(m,n)=1P(m+3,n+3)P(m, n) = 1 - P(m+3, n+3) (since any path from the latter point to heaven corresponds with a path from the former point to hell, and vice versa).
Thus for example we have
P(1,2)=P(1,2)=1P(2,1)=1P(1,2), P(1,2) = P(-1,-2) = 1 - P(2,1) = 1 - P(1,2),
so P(1,2)=1/2P(1,2) = 1/2.
Applying Equation (1) to points (1,1)(1,1), (0,1)(0,1), and (0,2)(0,2), and using the above symmetries, we get the equations
4P(1,1)=2P(0,1)+14P(0,1)=P(0,2)+2P(1,1)+14P(0,2)=P(0,1)+3/2 \begin{gathered} 4P(1,1) = 2P(0,1) + 1 \\ 4P(0,1) = P(0,2) + 2P(1,1) + 1 \\ 4P(0,2) = P(0,1) + 3/2 \end{gathered}
Solving yields P(1,1)=13/22P(1,1) = 13/22.

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.