Probability of reaching net 4 heads when tossing coin 8 times

Question

This problem is #19 from the AMC 12 2016A, and goes as follows:

Jerry starts at $0$ on the real number line. He tosses a fair coin $8$ times. When he gets heads, he moves $1$ unit in the positive direction; when he gets tails, he moves $1$ unit in the negative direction. The probability that he reaches $4$ at some time during this process $\frac{a}{b},$ where $a$ and $b$ are relatively prime positive integers. What is $a + b?$

Even though the link above does provide a solution (which I understand), I tried to solve it in a different way. I came up with a different answer, and can’t figure out what’s wrong with my approach.

I tried counting all the ways in which you can reach 4 heads (net) at some point, which can be divided into 3 categories.

1. You win if you start with 4 heads, which means the last 4 throws don’t matter, so there are ${2}^{4}$ or 16 possibilities for the last 4 and thus there’s 16 possible solutions from this.
2. If you start with 5 heads and 1 tail, the last two throws don’t matter, which contributes 4 different solutions. That tail can come at the first, second, third, or fourth position (if it’s at the 5th or 6th spot, we would be overcounting because it would be covered by the #1), so we multiply by 4 and get 16 more solutions from this one.
3. If we start with 6 heads and 2 tails, we get that the two tails can be at the 1,2 | 1,3 | 1,4 | 1,5 | 2,3 | 2,4 | 2,5 | 3,4 | 3,5 | 4,5 positions, which is 10 (if either one is in the 6th or 7th position, we would be over counting), so this leads to 10 more solutions.

Therefore, my solution was $\frac{16+16+10}{{2}^{8}}=\frac{42}{256}=\frac{21}{128}\Rightarrow 149$. However, the solution given by the AoPS is $\frac{46}{256}=\frac{23}{128}\Rightarrow 151$. This means that I am missing 4 different combinations that my method doesn’t cover. What am I doing wrong?

Thank you in advance.

Answer 1

Your logic, broken down a bit more effectively, is to break into cases based on on which turn did he win, and this occurs either on the fourth turn, the sixth turn, or the eighth turn.

You say "If either one is in the sixth or seventh position we would be overcounting" but that is not entirely the case.

Consider the scenario that you have a tail in the first and sixth positions. That is $THHHHTHH$. letting red denote negative numbers, the sequence of scores is then: $\color{red}{1}0123234$. Despite a tail on the sixth turn, he won specifically on the eighth turn and not earlier.

Your final case is missing then the cases 1,6 | 2,6 | 3,6 | 4,6. You are correct in noting that 5,6 would fall under the first case.

Correcting this then, there are a total of $14$ outcomes in the third case, for then $\frac{16+16+14}{2^8}=\frac{23}{128}$ giving the answer of $151$ as expected.

Answer 2

It boils down to counting the last ones. You'll have to have two $T$, and the arrival at $4$ net $H$ must occur exactly at toss $8$, which means it can't occur before.

The way I saw this visually was to write down the times that had the winning toss on toss $7$. As soon as I got a $T$ on toss $7$ as I was writing these down, I knew I was double counting. So the two $T$s must be within the first six tosses, but cannot be in the fifth and sixth tosses (because I would have won on toss $4$).

Here they are:

$$TTHHHHHH$$ $$THTHHHHH$$ $$THHTHHHH$$ $$THHHTHHH$$ $$THHHHTHH$$ $$HTTHHHHH$$ $$HTHTHHHH$$ $$HTHHTHHH$$ $$HTHHHTHH$$ $$HHTTHHHH$$ $$HHTHTHHH$$ $$HHTHHTHH$$ $$HHHTTHHH$$ $$HHHTHTHH$$

Fourteen in all.

Answer 3

"Therefore, my solution was" $\frac{16+16+16}{{2}^{8}}=\frac{42}{256}$

Should be 16 + 16 + 10 in the numerator.

3) If we start with 6 heads and 2 tails, we get that the two tails can be at the 1,2 | 1,3 | 1,4 | 1,5 | 2,3 | 2,4 | 2,5 | 3,4 | 3,5 | 4,5 positions, which is 10 (if either one is in the 6th or 7th position, we would be over counting), so this leads to 10 more solutions.

It your first head comes up in the first 4 flips, your second head could comes up in the 6th flip. You have 1 tails and 4 heads in the first 5 flips. We have not counted this scenario yet. Then a tails in the 6th flip. And two more heads for the win.

You are missing |1,6|, |2,6|, |3,6| and |4,6|.