# General Pigeonhole Principle - Coin Flips

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.

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!

• I made an edit to fix the typo but the pigeonhold sounds like a move in wrestling. :-) Jul 20, 2014 at 20:21

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.

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.

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