Maths Olympiad Prep

Library / /44 of 54

Combinatorics Difficulty 6.8 National olympiad Prove it China

Given a positive integer n2n \ge 2, let B1,B2,,BnB_1, B_2, \dots, B_n denote nn arbitrary subsets of set XX, each of which contains exactly two elements. Find the minimum value of X|X| such that there exists a subset YY of set XX satisfying:
(a) Y=n|Y| = n;
(b) YBi1|Y \cap B_i| \le 1 for i=1,2,,ni = 1, 2, \dots, n,
where A|A| denotes the number of elements of the finite set AA.

Solution

We first prove that X>2n2|X| > 2n - 2. In fact, if X=2n2|X| = 2n - 2, let X={1,2,,2n2}X = \{1, 2, \dots, 2n - 2\}, B1={1,2}B_1 = \{1, 2\}, B2={3,4}B_2 = \{3, 4\}, \dots, Bn1={2n3,2n2}B_{n-1} = \{2n - 3, 2n - 2\}. Since Y=n|Y| = n, there exist two elements in YY that belong to the same BiB_i, then YBi>1|Y \cap B_i| > 1, a contradiction.

Let X=2n1|X| = 2n - 1.
Let B=i=1nBiB = \bigcup_{i=1}^n B_i, then B=2n1z|B| = 2n - 1 - z, where zz is the number of subset XBX \setminus B. Suppose the elements of XBX \setminus B are a1,a2,,aza_1, a_2, \dots, a_z.

If zn1z \ge n - 1, take Y={a1,,an1,d}Y = \{a_1, \dots, a_{n-1}, d\}, and dBd \in B, as desired.

If z<n1z < n - 1, suppose there are tt elements that occur once in B1,B2,,BnB_1, B_2, \dots, B_n. Since i=1nBi=2n\sum_{i=1}^n |B_i| = 2n, then
t+2(2n1zt)2n, t + 2(2n - 1 - z - t) \le 2n,
it follows that t2n22zt \ge 2n - 2 - 2z. So the elements that occur twice or more than twice in B1,B2,,BnB_1, B_2, \dots, B_n occur repeatedly by 2n(2n22z)=2+2z2n - (2n - 2 - 2z) = 2 + 2z times.

Consider the elements that occur once in B1,B2,,BnB_1, B_2, \dots, B_n:
b1,b2,,btb_1, b_2, \dots, b_t. Thus, there are at most 2+2z2=1+z\frac{2+2z}{2} = 1+z subsets in B1,B2,,BnB_1, B_2, \dots, B_n that do not contain the elements b1,b2,,btb_1, b_2, \dots, b_t. So, there exist n(z+1)=nz1n - (z+1) = n-z-1 subsets containing at least the elements b1,b2,,btb_1, b_2, \dots, b_t.

Suppose that B1,B2,,Bn1zB_1, B_2, \dots, B_{n-1-z} contain the elements b~1,b~2,,b~n1z\tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_{n-1-z} of b1,b2,,btb_1, b_2, \dots, b_t, respectively. Since
2(n1z)+z=2n2z<2n1, 2(n - 1 - z) + z = 2n - 2 - z < 2n - 1,
there must exist an element dd that is not in B1,B2,,Bn1zB_1, B_2, \dots, B_{n-1-z} but is in Bnz,,BnB_{n-z}, \dots, B_n.

Write Y={a1,,az,b~1,b~2,,b~n1z,d}Y = \{a_1, \dots, a_z, \tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_{n-1-z}, d\}, as desired.

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.