Maths Olympiad Prep

Library / /139 of 196

Combinatorics Difficulty 5.7 AIME, harder Prove it Soviet Union

Problem:

a. A committee has met 40 times, with 10 members at every meeting. No two people have met more than once at committee meetings. Prove that there are more than 60 people on the committee.

b. Prove that you cannot make more than 30 subcommittees of 5 members from a committee of 25 members with no two subcommittees having more than one common member.

Solution

Solution:

a. Each meeting involves 1092=45\frac{10 \cdot 9}{2} = 45 pairs. So after 40 meetings, there have been 40×45=180040 \times 45 = 1800 pairs. We are told that these are all distinct. But if there are NN people on the committee, then there are only N(N1)2\frac{N(N-1)}{2} pairs available. For N=60N=60, this is only 60592=1770\frac{60 \cdot 59}{2} = 1770. Therefore, N>60N > 60.

b. A subcommittee of 5 has 542=10\frac{5 \cdot 4}{2} = 10 pairs. So 31 subcommittees have 31×10=31031 \times 10 = 310 pairs, and these are all distinct, since no two people are on more than one subcommittee. But a committee of 25 only has 25242=300\frac{25 \cdot 24}{2} = 300 pairs available. Therefore, you cannot make more than 30 such subcommittees.

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.