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"

(→‎See also)
 
(One intermediate revision by one other user not shown)
Line 5: Line 5:
  
 
==Solution==
 
==Solution==
−
Since the probability that Ying buries her car in a city that is not Havennew is equal for each city, we just need to find the probability that she buries it in Havennew, and we can find the probability of it being buried in Viavesta.
+
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.
  
−
She begins in Havennew, and she makes 7 trips. Let's define going to somewhere other than Havennew <math>a</math>, and driving to Havennew <math>b</math>. We can arrange <math>a</math>'s and <math>b</math>'s and find the probability of each arrangement happening. No two <math>b</math>'s can be consecutive, an <math>a</math> must be first, and a <math>b</math> must be last. So we have <math>a----ab</math>. We can fill in those dashes with <math>aaaa</math>, <math>aaab</math>, <math>aaba</math>, <math>abaa</math>, <math>baaa</math>, <math>baba</math>, <math>baab</math>, and <math>abab</math>. The probability of <math>aaaaaab</math> happening is <math>\frac{32}{729}</math>, the probability of <math>aaaabab</math>, <math>aaabaab</math>, <math>aabaaab</math>, or <math>abaaaab</math> happening is <math>\frac{8}{243}</math>, and the probability of <math>ababaab</math>, <math>abaabab</math>, or <math>aababab</math> happening is <math>\frac{2}{81}</math>. Thus <math>q=\frac{182}{729}</math>. Thus the probability that she buried it in a city other than Havennew is <math>\frac{547}{729}</math>, and the probability she buried it in Viavesta is <math>\frac{547}{2187}</math>. <math>p+q=\frac{547+546}{2187}=\frac{1093}{2187}</math>.
+
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 01: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"