João works selling astrological prediction packages. To boost sales of his predictions, he offers discounts if people of the same sign want to hire his services. In the Greek Horoscope, since there are exactly 12 signs, therefore, in a group of 13 people, at least two of them will have the same sign and may be interested in the promotional package.

a) What is the minimum number of people a group must have for him to be certain that there will be at least 3 people of the same sign in the Greek Horoscope?

b) In the Chinese Horoscope, there are also exactly 12 signs. If João wants to be certain that, in a certain group of people, there will be two people with exactly the same signs in both the Greek and Chinese Horoscopes, what is the minimum number of people that such a group must have?

#
Solution

a) The minimum is 25. If in a group of 24 people each zodiac sign appears at most twice, we will have at most $2 \cdot 12=24$ people. Since $24<25$, this shows that at least one of the zodiac signs must appear three times. Indeed, this is the minimum where such a property occurs, because if we consider 24 people divided into 12 pairs with the same zodiac sign, the property in the statement will not be found.

b) The minimum number is $12 \cdot 12+1=145$. Note that there are at most $12 \cdot 12=144$ possible pairs of combinations between Greek and Chinese zodiac signs. If we choose 145 people and divide them according to these pairs, at least one of them must be used twice. It is not possible to conclude this with fewer than 145, because it is possible for 144 people to exhibit all possible pairs of combinations without repetitions.

Note: The arguments used in both items are applications of the Pigeonhole Principle. See problem 11 of level 1 of the 2014 Bank.