<p>@rspence
I’ve been thinking about that problem since yesterday, and imo it’s a bit too hard for AIME, since I can’t find any way to solve it apart from massive (and I mean MASSIVE) amounts of casework. I thought about balls and urns, but then we have 5 in a row, not 2, and the fact that we have 5 answer choices also complicates this.</p>
<p>^watch though, my logic is probably flawed somewhere and there’s a really simple way to do this somehow</p>
<p>Sorry about that, I guess I wasn’t paying enough attention when I read it.</p>
<p>I think I have a solution…please correct me if I’m wrong.</p>
<p>Denote by A_n the number of strings of n H,T with no 5-in-a-row. For example,</p>
<p>A<em>m = 2^m where 1 <= m <= 4
A</em>5 = 30
A<em>6 = 58
A</em>7 = 112 (done by brute-forcing a bit)</p>
<p>Suppose we know A<em>5, …, A</em>k. We wish to find A<em>{k+1}. If you treat the k+1 coin flips as a string of k flips followed by the k+1th flip, we can say that A</em>{k+1} = 2A_k. </p>
<p>However we have to subtract the number of (k+1)-sequences that end with five of the same type. Here, we only need to consider (k+1)-sequences ending in …THHHHH or …HTTTTT (if it ends in HHHHHH we wouldn’t have counted it in the first place).</p>
<p>This is equivalent/bijective to finding the number of (k-4)-sequences ending in T, plus the number of (k-4)-sequences ending in H (since we are adding HHHHH or TTTTT). However these two must add up to A_(k-4).</p>
<p>Therefore, we have the recursion A<em>(k+1) = 2A</em>k - A_(k-4) for k >= 5. We can check this because</p>
<p>k=5 → A<em>6 = 2A</em>5 - A<em>1 → 58 = 2(30) - 2
k=6 → A</em>7 = 2A<em>6 - A</em>2 → 112 = 2(58) - 4</p>
<p>This recurrence can be solved using the characteristic polynomial x^5 - 2x^4 + 1 = 0.</p>
<p>^this.
<em>facepalm</em>
Never thought of using recursion. Nice. I read up to about half of it, understood the rest implicitly. Although, you’d probably need a computer to solve this up to 100.</p>
<p>AND we also have 5 different answer choices rather than 2. I’m pretty sure that this is remedied very easily by taking the formula instead to be A<em>(k+1) = 5A</em>k - A_(k-4), and using 5^m rather than 2^m at the very beginning for m <= 4.</p>
<p>Yeah, with 5 answer choices you’ll have much bigger numbers (although the characteristic polynomial should be similar).</p>
<p>I don’t really feel like solving x^5 - 2x^4 + 1 = 0 without a computer. x = 1 works, but there are four other roots. Clearly, the probability is (A_100)/(2^100) (or 1 minus that if you’re looking for 5-in-a-row).</p>
<p>Basically, the probability of obtaining a 5-in-a-row increases as the number of coin flips increases. Intuitively, it should converge to 1.</p>
<p>OK, so I was right about one thing: it’s a much harder problem than it looks like…</p>
<p>Check out this forum:</p>
<p>[Math</a> Forum - Ask Dr. Math](<a href=“Classroom Resources - National Council of Teachers of Mathematics”>Classroom Resources - National Council of Teachers of Mathematics)</p>
<p>And in particular, this quote:</p>
<p>“I’m afraid if you want the full theory behind the approximate solution
shown above you will need to study ‘Recurrent Events and Renewal
Theory’ in books like that by William Feller. The treatment requires a
knowledge of probability-generating functions, solution of recurrence
relations, and the theoretical application of Normal approximations
for large n. It covers about 23 pages in the Feller book and cannot be
reproduced here.”</p>
<p>He then goes on to describe a difficult method for exact solutions – and RSpence had the right flavor (I think)!</p>
<p>Since that math is over my head, I think my next move would be to write a computer simulation and let it run a few million trials.</p>
<p>And I guess we can stop worrying about whether this will be on the SAT… :)</p>
<p>Yeah, a question like this definitely won’t appear on the SAT. It might be in the #12-15 range on AIME, provided that the recursion isn’t a 5th-degree polynomial.</p>
<p>An SAT-level question could be, “A coin is flipped 100 times. What is the probability of obtaining at least two heads or two tails in a row?” That one should take seconds to solve.</p>
<p>^ (2^99-1)/(2^99)?</p>
<p>@Kyrix1, yep.</p>
<p>^^ …still too hard to be an SAT question. Change it to 5 flips and MAYBE it would be on the SAT2 level 2…</p>