Maths Olympiad Prep

Library / /24 of 33

Combinatorics Difficulty 8.4 Shortlist Prove it Turkey

We say that a group of 25 students is a *team* if any two students in this group are friends. It is known that in the school any student belongs to at least one team but if any two students end their friendships at least one student does not belong to any team. We say that a team is *special* if at least one student of the team has no friend outside of this team. Show that any two friends belong to some special team.

Solution

Let us prove that any two friends AA and BB belong to some special team. Let us define a longest sequence S1,S2,,SmS_1, S_2, \dots, S_m of students such that

* for all 1i<jm1 \le i < j \le m we have SiSjS_i \ne S_j
* for each 1im1 \le i \le m any team containing SiS_i also contains A,B,S1,S2,,Si1A, B, S_1, S_2, \dots, S_{i-1}.

Note that the sequence is well defined since it contains at least one element. Indeed, if AA and BB end their friendship then some student S1S_1 does not belong to any team. Therefore any team containing S1S_1 contains both AA and BB (S1S_1 may coincide with AA or BB).

Let TT be any team of SmS_m. Assume that SmS_m has a friend SS' outside of TT. If SmS_m and SS' end their friendship then there is a student SS'' which does not belong to any team. Therefore, any team containing SS'' contains also SmS_m and consequently contains A,B,S1,S2,,Sm1A, B, S_1, S_2, \dots, S_{m-1}. Note that SS'' does not coincide with S1,S2,,Sm1S_1, S_2, \dots, S_{m-1} since any team of SmS_m contains S1,S2,,Sm1S_1, S_2, \dots, S_{m-1} and any team of SS'' contains SS'. Then SS'' can be added to the sequence S1,S2,,SmS_1, S_2, \dots, S_m. This contradicts the maximality of this sequence. Thus, the team TT is special (and it is the only team of SmS_m). Done.

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.