Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 Alabama ARML TST Problems/Problem 15"

(wrong answer.)
 
Line 5: Line 5:
  
 
==Solution==
 
==Solution==
−
{{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 <math>p_n</math> be the probability that she is in Havennew after <math>n</math> trips. We already know that <math>p_1=1</math>, and that after <math>n</math> trips the probability of being in each of the other three towns is <math>\frac{1-p_n}3</math>.
 +
 
 +
We will now express <math>p_{n+1}</math> using <math>p_n</math>. How can Ying get to Havennew after the <math>n+1</math>-th trip? After <math>n</math> trips she must be in some other town (this happens with probability <math>1-p_n</math>), and in that town she must pick to go to Havennew (this happens with probability <math>\frac 13</math>). Therefore <math>p_{n+1}=\frac{1-p_n}3</math>.
 +
 
 +
Using this recurrence, we compute:
 +
 
 +
<cmath> p_2 = \frac{1-1}3 = 0 </cmath>
 +
<cmath> p_3 = \frac{1-0}3 = \frac 13 </cmath>
 +
<cmath> p_4 = \frac{1-1/3}3 = \frac 29 </cmath>
 +
<cmath> p_5 = \frac{1-2/9}3 = \frac 7{27}</cmath>
 +
<cmath> p_6 = \frac{1-7/27}3 = \frac {20}{81}</cmath>
 +
<cmath> p_7 = \frac{1-20/81}3 = \frac {61}{243}</cmath>
 +
<cmath> p_8 = \frac{1-61/243}3 = \frac{182}{729}</cmath>
 +
 
 +
The probability that the car is buried in Havennew is <math>q = p_8 = \frac{182}{729}</math>. The probability it is buried in Viavesta is
 +
<math>\frac{1-p_n}3 = \frac{547}{2187}</math>.
 +
 
 +
The result is <math>p+q = \frac{547}{2187} + \frac{182}{729} = \frac{547 + 3\cdot 182}{2187} = \boxed{\frac{1093}{2187}}</math>.
 +
 
 +
=== Note ===
 +
 
 +
It is worth noting that <math>\lim_{n\to\infty} p_n=\frac 14</math>. In fact, already <math>p_8 \simeq 0.2497</math>, and the answer to our question is <math>\frac{1093}{2187}\simeq 0.4998</math>. The eight steps were enough to virtually eliminate the initial bias that came from starting in a fixed town.
  
 
==See also==
 
==See also==
 
{{ARML box|year=2006|state=Alabama|num-b=14|after=Final Question}}
 
{{ARML box|year=2006|state=Alabama|num-b=14|after=Final Question}}

Latest revision as of 00:12, 28 January 2009

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.

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Alabama_ARML_TST_Problems/Problem_15&oldid=29782"