How to prove that for all 25 ppl and 4 groups, there is a group of at least 6 ppl from the same group?

Question

As of Jun.17, I predict that Brazil, Germany, Italy, and Argentina will make it to the semi-finals of the FIFA World Cup. Suppose you have a group of 25 footballers from those four countries. Prove that out of those 25, there is a group of at least 6 footballers who come from the same country. (It is not necessary to use the detailed structured proof format, but you still must justify every step.)

Thank you guys.

Answer 1

Let's take a look at the essence of this problem:

Suppose you have a group of $25$ footballers from those four countries. Prove that out of those $25$, there is a group of at least $6$ footballers who come from the same country.

This can be restated as

Suppose you have $4$ buckets with an assorted number of balls in them. I claim that if you take $25$ balls out of these buckets at least $6$ of them come from the same bucket.

Now let's take a look at some cases:

Case 1: $25$ balls all come from one bucket. Well then clearly $6$ come from one bucket (pick any $6$ of the $25$).

Case 2: $24$ balls come from one bucket and one comes from another bucket.

Do you see the pattern I'm forming here? Try to take this down the line to see what happens with the pattern (i.e. what condition will be created on the balls not in the first bucket if we have less than $6$ in it).

While you said you didn't need a rigorous proof, I still wouldn't consider the above a proof at all, more of a good starter for intuition. Once you walk through that however you should be able to see how to conjure a proof by contradiction, i.e. suppose we have $25$ balls from $4$ buckets but that we only selected at most $5$ balls from each bucket. I think when stating it in this last proof-by-contradiction form you can really see the solution.

Hope this helps!

Answer 2

Here is why there must be group of size seven. If all four groups were of size six or smaller, you would have at most 24 players, since there are four groups and no player belongs to more than one.