Track / Stage 5 / 338 of 400 #938 of 2000

Problem 938

AIME late

Combinatorics Difficulty 5.8 Prove it

[ Dirichlet's Principle (continued).]

a) Prove that in any football team there are two players who were born on the same day of the week. b) Prove that among the residents of Moscow, there are ten thousand who celebrate their birthday on the same day.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

a) Let football players be rabbits, and days of the week be cells. We get 7 cells into which we need to place at least 11 rabbits, which means that by the Pigeonhole Principle, at least one cell will contain at least two rabbits.

b) Suppose that fewer than 10000 Muscovites were born on each of the 366 days of the year. But this would mean that the total population of Moscow is no more than 366 * $9999=3659634$ , which is, of course, incorrect.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.