Maths Olympiad Prep

Library / /19 of 33

, 2011

Combinatorics Difficulty 8.0 Shortlist Prove it Baltic Way

There are 20112011 people in a city. For some period of time every day a group of at least 44 people went to a restaurant to have dinner. No group of 33 people went together to more than one dinner. Prove that there exists a group of 2424 people such that at every dinner there was a person not belonging to this group.

Solution

We can assume that at every dinner there were exactly 44 people (just remove the surplus people from every dinner, which does not affect the condition that no group of 33 people went together to two different dinners, and can only make the task of finding a suitable 2424-people group harder).

Consider a group AA with the greatest possible cardinality such that at every dinner there was a person not from AA. Assume there are mm people in AA. It is sufficient to show that m24m \ge 24.

By the definition of AA, for every person pAp \notin A there exists a group GpA{p}G_p \subset A \cup \{p\} of 44 people which went to the restaurant together one day. But Gp⊄AG_p \not\subset A, so there are exactly 33 elements in AGpA \cap G_p. In other words, every GpG_p consists of 33 people from AA and the person pp. Also, for different people p1,p2Ap_1, p_2 \notin A we obtain distinct intersections AGp1,AGp2A \cap G_{p_1}, A \cap G_{p_2} — otherwise the groups Gp1,Gp2G_{p_1}, G_{p_2} would have 33 people in common, which by our assumptions would mean that Gp1=Gp2G_{p_1} = G_{p_2}, but this is not possible, since p1Gp1p_1 \in G_{p_1} and p1Gp2p_1 \notin G_{p_2}.

Thus the number of people not in AA (equal to 2011m2011 - m) does not exceed the number of 33-element subsets of AA:
2011m+(m3)=16(6m+m(m1)(m2))=16m(m23m+8). 2011 \le m + \binom{m}{3} = \frac{1}{6}(6m + m(m-1)(m-2)) = \frac{1}{6}m(m^2 - 3m + 8).
The right hand side is increasing for m1m \ge 1 and is equal to 17941794 for m=23m = 23. Therefore m24m \ge 24, as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.