2006 Alabama ARML TST Problems/Problem 15

Problem

Ying lives on Strangeland, a tiny planet with 4 little cities that are each 100 miles apart from each other. One day, Ying begins driving from her home city of Viavesta to the city of Havennew, which takes her about an hour. When she gets to Havennew, she decides she wants to go straight to another city on Strangeland, so she randomly chooses one of the other three cities (possibly Viavesta), and starts driving there. Ying drives like this for most of the day, making 8 total trips between cities on Strangeland, choosing randomly where to drive to next from each stop. She then stops at her final city of destination, digs a hole, and buries her car.

Let $p$ be the probability Ying buried her car in Viavesta and let q be the probability she buried it in Havennew. Find the value of $p + q$ .

Solution

After the first trip she is surely in Havennew. From this moment on, the other three cities can not be distinguished, so the probability that she is in Viavesta at some point in time is equal to the probability that she is in any of the other two towns.

Let $p_n$ be the probability that she is in Havennew after $n$ trips. We already know that $p_1=1$ , and that after $n$ trips the probability of being in each of the other three towns is $\frac{1-p_n}3$ .

We will now express $p_{n+1}$ using $p_n$ . How can Ying get to Havennew after the $n+1$ -th trip? After $n$ trips she must be in some other town (this happens with probability $1-p_n$ ), and in that town she must pick to go to Havennew (this happens with probability $\frac 13$ ). Therefore $p_{n+1}=\frac{1-p_n}3$ .

Using this recurrence, we compute:

$p_2 = \frac{1-1}3 = 0$ $p_3 = \frac{1-0}3 = \frac 13$ $p_4 = \frac{1-1/3}3 = \frac 29$ $p_5 = \frac{1-2/9}3 = \frac 7{27}$ $p_6 = \frac{1-7/27}3 = \frac {20}{81}$ $p_7 = \frac{1-20/81}3 = \frac {61}{243}$ $p_8 = \frac{1-61/243}3 = \frac{182}{729}$

The probability that the car is buried in Havennew is $q = p_8 = \frac{182}{729}$ . The probability it is buried in Viavesta is $\frac{1-p_n}3 = \frac{547}{2187}$ .

The result is $p+q = \frac{547}{2187} + \frac{182}{729} = \frac{547 + 3\cdot 182}{2187} = \boxed{\frac{1093}{2187}}$ .

Note

It is worth noting that $\lim_{n\to\infty} p_n=\frac 14$ . In fact, already $p_8 \simeq 0.2497$ , and the answer to our question is $\frac{1093}{2187}\simeq 0.4998$ . The eight steps were enough to virtually eliminate the initial bias that came from starting in a fixed town.

2006 Alabama ARML TST (Problems)
Preceded by: Problem 14	Followed by: Final Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Page

Toolbox

Search

2006 Alabama ARML TST Problems/Problem 15

Contents

Problem

Solution

Note

See also