Olympiad Maths Prep

Library / /4 of 10

Combinatorics Difficulty 5.9 AIME, harder Prove it Czech Republic

In a certain club, some pairs of members are friends. Given k3k \ge 3, we say that a club is *k*-good if every group of *k* members can be seated around a round table such that every two neighbors are friends. Prove that if a club is 6-*good* then it is 7-*good*.

(Josef Tkadlec)

Solution

Consider a 6-good club and denote some seven of its members by A,,GA, \dots, G. It suffices to show that A,,GA, \dots, G can be seated around a table as required. Consider only friendships among A,,GA, \dots, G. First, we show that every member has at least three friends.

Without loss of generality consider GG. By assumption, B,,GB, \dots, G can be seated as required, hence GG has at least two friends. Without loss of generality, FF is one of them. By assumption, A,,E,GA, \dots, E, G (omitting FF) can be seated as required, hence GG has at least two more friends apart from FF for a total of at least three friends.

Since every member has at least three friends, there exists a member with at least four friends (otherwise the number of friendly pairs equals 1273\frac{1}{2} \cdot 7 \cdot 3, which is clearly impossible). Without loss of generality, assume GG has at least four friends.

By assumption, A,,FA, \dots, F can be seated as required. In such a seating, some two of the four friends of GG are neighbors and we can seat GG in between them.

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.