Olympiad Maths Prep

Library / /8 of 16

Combinatorics Difficulty 5.3 AIME, harder Prove it Ukraine

A committee has 4 subcommittees, each controlled by 3 leaders from the committee. For effective coordination, each two subcommittees must have exactly one leader in common. What is the least possible number of people in the committee?

Solution

If we consider two subcommittees, they have exactly one leader in common, therefore, together they have exactly 5 members. Hence there are at least 5 people in the committee. Denote them by A={1,2,3,4,5}A = \{1, 2, 3, 4, 5\}. However it's impossible to choose leaders for another subcommittee out of them. Therefore, the committee must have at least 6 members. Here's an example of four subcommittees and their leaders:
A={1,2,3,4,5,6}{1,2,3};{3,4,5};{1,5,6};{2,4,6}. A = \{1, 2, 3, 4, 5, 6\} \rightarrow \{1, 2, 3\}; \{3, 4, 5\}; \{1, 5, 6\}; \{2, 4, 6\}.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.