General Pigeonhole Principle - Coin Flips

Question

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows:

A coin is flipped three times and the outcomes recorded. So, HTT might be recorded for 1 round of 3 flips. How many times must we flip a coin three times to be guaranteed that there are two identical outcomes?

I am struggling to understand the correct way to solve this problem. When I use the formula: $$ N = k(r - 1) + 1 $$ Where k = 2 for the number of identical outcomes we want, r = 3 for the number of coin flips, I get 5. The answer in my book is written as 9. When I multiply the $$ k(r - 1) $$ part of the equation by 2 and then add 1, I am able to get this answer, but I feel like I am just doing this without any real understanding of what's going on. I thought maybe it's related to the outcome of each individual coin flip (H or T), but I just don't have a firm grasp on this yet. Any hints or guidance with this is greatly appreciated.

Answer 1

I'm not sure where it is that you're getting that formula. It seems to me like it was the application of the Pigeonhole Principle to a different question.

The Pigeonhole Principle states—in laymen's terms—that if you have $N + 1$ objects and $N$ places to put them, then there must be at least one place that has more than one object. Here, we have $2^3 = 8$ possible results of tossing three coins. If we want to assure that there is a doubling up of one of the results, we need to perform one more set of coin tosses, i.e. $8 + 1 = 9$.

Here, we have $8$ results: 8 places to put the results of flipping three coins. In order to assure that we double up, we need to put $9$ objects in those places, i.e. flip $9$ sets of coins.

Hope that helps!

Answer 2

There are $2^3 = 8$ different possible outcomes. To guarantee that we get at least two identical outcomes, we must perform the experiment $8+1 = 9$ times.

Answer 3

There's a couple of problems here. First is that the number of possible outcomes is $2^3 = 8$. Each of the three flips can be H or T, 2 possibilities. $2*2*2 = 8$. (This assumes that order matters, and that HHT is different than HTH. This seems true from the wording of the question.

Second, in the formula $ N = k(r - 1) + 1 $, k is the number of possible outcomes and r is the number of repetitions we want. $ 9 = 8 ( 2 - 1 ) + 1 $. The reason for this is that if there are only $ N = k(r - 1) $ trials, each of the $k$ outcomes could occur exactly $r-1$ times, thus not meeting the goal. But given 1 more trial, whichever outcome you get, will now have happened $(r-1) + 1 = r$ times, meeting the goal.

Answer 4

Since possible outcomes for each set of flip is 8 = ( 2^3 ), a repeat output is guaranteed at 9th ( for the least probable case ).