Maths Olympiad Prep

Library / /11 of 48

Combinatorics Difficulty 5.4 AIME, harder Prove it Greece

In a School formed 112112 groups each contained 1111 students. Every pair of groups had exactly one common student. Prove that:

a. There exists a student belonging at least to 1212 groups.

b. There exists a student belonging to all groups.

Solution

a. We consider an arbitrary group OO. Each of the rest 111111 groups has exactly one student belonging to OO. Since 111=1110+1111 = 11 \cdot 10 + 1, from the pigeonhole's rule we conclude that there exists one student xOx \in O who belongs at least to 1111 other groups. Hence xx belongs at least to 1212 groups, say O1,O2,,O12O_1, O_2, \dots, O_{12}.

b. We will prove that xx belongs to all groups. In fact, let xOx \notin O'. Then the group OO' has exactly one common student with the groups O1,O2,,O12O_1, O_2, \dots, O_{12}. Since OO' has 1111 students, then there will exist two groups, say Oi,OjO_i, O_j having the same common student with the group OO', say yy. However, in this case the groups Oi,OjO_i, O_j will have two common students xx and yy, absurd.

Therefore xx belongs to all groups.

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 and solution reproduced as published; topic and difficulty added by this site.