prove something must happen with pigeonhole principle

Question

I'm given the following problem:

In every group of 15 cars , there are 3 that were manufactured in the same country. prove that in a group of 100 cars there are 15 cars that were manufactured in the same country.

does anyone have an idea of how to implement pigeonhole principle here? I'm kind of stuck because I can't assign cars to countries since I don't know how many countries are there.. Any help is appreciated . Thanks.

Answer 1

First we argue that there cannot be more than $8$ countries. If there were, then we could choose $2$ cars of each of these $8$ countries and discard any of the chosen cars to receive a group of $15$ cars which does not have $3$ cars which were manufactured in the same country. So there are $\leq 7$ countries. Thus by the pigeon-hole principle we have that for every group of $100$ cars at least $\lceil100 / 7\rceil = 15$ were manufactured in the same country.

Note that this argumentation fails if for some country there is only 1 car.

Answer 2

Suppose each country manifactured at most $14$ cars and let $C_1,C_2,..C_n$ be al countries.

Then we have $$100=|C_1|+|C_2|+...+|C_n| \leq 14n \implies n\geq8$$

So we have at least $8$ countries. If we take from each country $2$ cars we have $16$ cars and no $3$ from the same country. A contradiction.