Fdtxjr

I was solving some combinatorics question and I came upon one I've been trying to solve for 2 days and I'm curios how to solve it.

It is known that in every set of 15 cars, at least 3 were manufactured from the same country (there can also be another 3 (or more) cars in the set which came from another country). prove that in every set of 100 cars, 15 were made manufactured in the same country.

Thanks to anyone who helps!

Consider a set $A$ of $100$ cars such that no $15$ are manufactured in the same country; we will show that there must be a subset of $15$ cars no three of which are from the same country.

So consider any hypothetical particular subset $Ssubset A$.

1) No country has contributed more than $14$ cars to $A$, since if it had, then choose $15$ cars among that country's produce, and you violated the definition of $A$.

2) The countries contributing to $A$ can be divided into $n_1$ countries contributing just one car, and $n_2$ countries contributing between $2$ and $14$ cars. $n_1 + 14n_2 geq 100$.

3) If $n_2>7$ we can choose $2$ cars from each of those countries for $S$, and this violates the rule that every $S$ of 15 cars contains three or more cars from the same country. So $n_2 leq 7$.

4) $n_1 geq 100 - 14 n_2 geq 100 - 98 = 2$. So if $n_2 = 7$ we can choose for $S$ two cars from each of those seven countries and one car from an $n_1$ country, and this violates the rule that every $S$ of 15 cars contains three or more cars from the same country. So $n_2 < 7$.

5) If $n_2 leq 6$ then $n_1 geq 100 - 14 n_2 geq 100 - 84 = 16$. Thus if $n_2 < 7$ we can form a set $S$ of more than $15$ cars no two of which are from the same country, again violating the rules.

6) Therefore whenever we have a set of $100$ cars no $15$ of which are from the same country, we can form a set $S$ of $15$ cars no $3$ of which are from the same country.

Let $n$ be the number of countries who made exactly one car appearing in the $100$.

Let $m$ be the number of countries who made more than one car appearing in the $100$.

Assume by way of contradiction that no country made $15$ cars. Then $$n+14mge 100,$$ because $n$ countries contribute $1$ car each and $m$ countries contribute at most $14$ each, and $$n+2mle 14,$$ for otherwise selecting one car from the $n$ countries and two from the $m$ countries would give $15$ cars with no three alike. Therefore,
$$
(n+14m)-(n+2m)ge 100-14implies 12mge 86implies mge lceil 86/12rceil = 8
$$
But this is a contradiction, because selecting two cars from eight of the countries with more than one car would give $16$ cars with no three alike.

Edit: See the very final paragraph for the same argument, but starting from the other end. Perhaps that will clarify.

It is impossible for there to be 8 or more manufacturing countries. If there were 8 or more manufacturing countries, then you could have a set of 15 cars in which no country made 3 or more cars: you could have each of the first 7 countries manufacture two of the cars, and the final country manufacture exactly 1 car. That means that if there were 8 or more manufacturing countries, the hypothesis ("in every set of 15 cars at least 3 were manufactured in the same country") would not be true.

Thus, the maximum number of manufacturing countries is 7. If there are 7 or fewer manufacturing countries, then by the pigeonhole principle, if we are distributing 100 items among (at most) 7 "boxes" (the countries), then at least one box contains 15 or more items (since otherwise, you would have at most $14times 7 = 98$ items).

In light of comments, let me clarify what this approach is doing.

There are two ways to read the problem: either as describing a specific run of cars made by an unknown number of countries, or as describing a specific set of manufacturing countries that make runs of productions of cars.

In essence: I'm showing that it is impossible to construct a counterexample by considering the number of countries involved. Other approaches show that it is impossible to have a counterexample by considering the cars involved. The two approaches amount to the same thing, because a potential counterexample would be "detected" by either approach.

Sigh; apparently, this is creating way more controversy than it should. I do not dispute other approaches, but apparently some people are having issues with this approach.

What the approach does is show that no counterexample can exist; that is, we cannot have a set of cars in which the premise holds but not the conclusion. I do this by attempting to build such a counterexample, but showing that none can be made. I attempt to build such a counterexample by considering the number of countries that would be included in such a counterexample.

When I say "you could have a set of 15 cars in which no country made 3 or more cars: you could have each of the first 7 countries manufacture two of the cars, and the final country make exactly one car", how does that fit into a potential counterexample? It tells you that if you have a particular run in which there are 8 or more manufacturing countries, then you would either trivially satisfy the conclusion, or else fail to satisfy the hypothesis; the situation described is the extreme case, where it is least clear that the hypothesis may fail (obviously, if we knew there are 15 or more manufacturing countries we would know the premise fails, etc). Any larger number of countries make it easier to construct a subset of 15 with no more than 2 from the same country. So in a search for a potential counterexample (with 100+ cars), we may restrict to the case in which there are no more than 7 manufacturing countries.

It's just that I'm thinking about "building a counterexample" as countries pumping out cars to whatever specification, rather than "we have a bunch of cars, let's figure out who made them."

Any potential counterexample would be detected by this approach. The fact that this approach does not detect a counterexample shows that no counterexample exists.

Let me do the same argument, but starting with the "fewer countries" case first.

If a counterexample set of 100 cars involved 7 or fewer countries, then we would get at most 98 cars (14 cars each for the at most 7 countries); so the counterexample involves 8 or more countries. On the other hand, if you had 8 or more countries, and exactly $kleq 7$ make at least 2 cars, and at least $15-2k$ make exactly one, you fail the assumption; so if we have exactly $k$ making at least 2 cars, and at most $14-2k$ make exactly $1$ car, then you still need to distribute $100- (2k) - (14-2k) = 86$ cars among the $k$ countries that make at least $2$ cars. If we are to avoid going over $14$ for any given country, we want $k$ to be as large as possible. The largest possible is $7$ with $1$ country making exactly 1 car, which is the case I opened with.

I originally did the same thing, but did it in the other order, by first dismissing the counterexamples with 8 or more countries, then noting no counterexample can have 7 or fewer.