Olympiad Maths Prep

Library / /6 of 6

Combinatorics Difficulty 8.6 Shortlist Prove it Bulgaria

There are 2k2k citizens in a town every two of which are either friends or enemies. For some positive integer tt each citizen has at most tt enemies and there exists a citizen having exactly tt enemies. A group is called *friendly* if any two members of the group are friends. It is known that a friendly group with more than kk members does not exist and all citizens can be partitioned into two friendly groups having kk members each. Prove that the number of friendly groups having kk members is not greater than 2k1+2kt2^{k-1} + 2^{k-t}.

Solution

Let A={a1,a2,,ak}A = \{a_1, a_2, \dots, a_k\} and B={b1,b2,,bk}B = \{b_1, b_2, \dots, b_k\} be the two friendly groups. For arbitrary group CC from AA denote by SCS_C the group of all people from BB each of which is an enemy of at least one person from CC. If C>SC|C| > |S_C| then C(BSC)C \cup (B \setminus S_C) is a friendly group having more than kk members, a contradiction.

Therefore the sets S{ai}S_{\{a_i\}} satisfy the Hall's condition for system of distinct representatives. Hence, we may assume that aia_i and bib_i are enemies for all i=1,2,,ki = 1, 2, \dots, k.

This means that every friendly group of kk members include one person from every pair (ai,bi)(a_i, b_i) for i=1,2,,ki = 1, 2, \dots, k.

Suppose the enemies of a1a_1 are b1,,btb_1, \dots, b_t. For a friendly group SS such that a1Sa_1 \in S we have b1,,btSb_1, \dots, b_t \notin S. Hence, a2,,atSa_2, \dots, a_t \in S. From every of the remaining ktk-t pairs (aj,bj)(a_j, b_j), j>tj > t we have to choose one of aja_j and bjb_j to be an element of SS. Therefore there are at most 2kt2^{k-t} such group.

For a friendly group SS with kk members such that a1Sa_1 \notin S we have b1Sb_1 \in S. Since from each of the remaining k1k-1 pairs (aj,bj)(a_j, b_j), j>1j > 1 we have to choose one of aja_j and bjb_j to be an element of SS we find that there are at most 2k12^{k-1} such groups.

Therefore, the total number of friendly groups of kk members is at most 2k1+2kt2^{k-1} + 2^{k-t}.

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.