Maths Olympiad Prep

Library / /50 of 377

Algebra Difficulty 4.5 AIME Find the answer United States

Problem:

An ant starts at one vertex of a tetrahedron. Each minute it walks along a random edge to an adjacent vertex. What is the probability that after one hour the ant winds up at the same vertex it started at?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Let pnp_n be the probability that the ant is at the original vertex after nn minutes; then p0=1p_0 = 1. The chance that the ant is at each of the other three vertices after nn minutes is 13(1pn)\frac{1}{3}(1 - p_n). Since the ant can only walk to the original vertex from one of the three others, and at each there is a 13\frac{1}{3} probability of doing so, we have that
pn+1=13(1pn). p_{n+1} = \frac{1}{3}(1 - p_n).
Let qn=pn14q_n = p_n - \frac{1}{4}. Substituting this into the recurrence, we find that
qn+1=14+13(qn34)=13qn. q_{n+1} = \frac{1}{4} + \frac{1}{3}\left(-q_n - \frac{3}{4}\right) = -\frac{1}{3} q_n.
Since q0=34q_0 = \frac{3}{4}, qn=34(13)nq_n = \frac{3}{4} \cdot \left(-\frac{1}{3}\right)^n. In particular, this implies that
p60=14+q60=14+341360=359+14359. p_{60} = \frac{1}{4} + q_{60} = \frac{1}{4} + \frac{3}{4} \cdot \frac{1}{3^{60}} = \frac{3^{59} + 1}{4 \cdot 3^{59}}.

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.