Olympiad Maths Prep

Library / /7 of 16

Combinatorics Difficulty 5.8 AIME, harder Prove it Czech Republic

Mathematics clubs are very popular in a certain city. Any two of them have at least one common member. Prove that one can distribute rulers and compasses to the citizens in such a way that only one citizen gets both (compass and ruler) and any club has at its disposal both, compass and ruler, from its members.

Solution

Let us consider the club KK with the least number of its members (in case there is more such clubs, we take any). We give to one of its members (let us call him Jacob) both a compass and a ruler. Each of the other members of the club will get a compass. Any other citizen will get a ruler. We show that this distribution complies with the conditions of the problem:

Any club which has Jacob as its member has certainly both instruments.

If there is a club where Jacob does not belong, then it has at least one common member with the club KK, that is, there is at least a compass at disposal in the club. If there were no ruler in the club, it would mean that it is a “subclub” of KK and therefore has at least one member (Jacob) less than KK, which is a contradiction with the choice of KK. The described distribution really satisfies the conditions of the problem.

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.