There are $12$ signs of zodiac. How many people are needed to guarantee that at least $6$ of these people have the same sign?

Question

There are $12$ signs of zodiac. How many people are needed to guarantee that at least $6$ of these people have the same sign?

My attempt

I used the formula $r(k-1)+1$

=$12(6-1)+1=61$

But how to know what values should be taken for "r" and "k"..

Answer 1

Yes, the answer is 61. This is related to a mathematical principle called the Pigeonhole Principle, which states that if you are trying to sort $n+1$ objects into $k$ sets (where $\frac{n}{k}=r; n, k, r \in \mathbb{Z}^+$), at least one set must contain at least $r+1$ objects. (This can be proven by proof by contradiction, but is pretty standard and so generally can just be used as justification of an answer by itself.)

For your problem, you have 12 signs of the zodiac - these are your 12 sets (so $k=12$). You are looking to find how many it takes before a set contains 6 objects (so $r+1=6$ and thus $r=5$). Therefore, $n+1 = r \times k + 1 = 12 \times 5 +1 = 61$.

Hope this helps!

Answer 2

In spite of being half asleep I will give this a naive try:

Take 12 people - worst case: all different.

Add another 12 people - still worst case, we got two of each sign now...

Continue with worst case... We got five of each sign.

One more required: Gotcha!

So my answer would be $5 \cdot 12 + 1 = 61$. Matches your result.

Not sure if that answers your question - I think it is how that formula is derived,...

Edit:

Well, the formula is hidden in the algorithm that I sloppily (admitted!) wrote down above. You just add more and more "whole sets" of possibilities (signs) until you have one less of each sign than you will need. That is the worst case relevant here.

$r$ would be the size of your "outcome set", that is $12$. $k$ would be the required amount of identical outcomes, that is $6$.

If you approach the problem "sequentially" like I did - picking more and more people and having the "worst possible luck" you can pick $\left(k-1\right)\cdot r$ and still not have $6$ identical. But that is the worst it can get, you will have $5$ of each then, pick one more and you cannot fail.