Maths Olympiad Prep

Library / /55 of 155

Combinatorics Difficulty 5.7 AIME, harder Prove it Saudi Arabia

Given six three-element subsets of the set XX with at least 55 elements, show that it is possible to color the elements of XX in two colors such that none of the given subsets is all in one color.

Solution

Let A1,,A6A_1, \ldots, A_6 be the subsets. We induct on the number nn of elements of XX.

If n=5n = 5, since (53)=10>6\binom{5}{3} = 10 > 6, we can find a three-element subset YY of XX not equal to any of A1,,A6A_1, \ldots, A_6; coloring the elements of YY in one color and the other elements in the other color.

If n=6n = 6, since (63)=20>6×2=12\binom{6}{3} = 20 > 6 \times 2 = 12, we can find a three-element subset YY of XX not equal to any of A1,,A6A_1, \ldots, A_6 or its complements; coloring the elements of YY in one color and the other elements in the other color meets the desired condition.

Now suppose n7n \geq 7. There must be two elements u,vu, v of XX such that {u,v}\{u, v\} is not a subset of any AiA_i, since there are at least (72)=21\binom{7}{2} = 21 pairs, and at most
6×{(x,y)x,yAi,i=1,,6}=6×3=18 6 \times \left| \{ (x, y) \mid x, y \in A_i, i = 1, \ldots, 6 \} \right| = 6 \times 3 = 18
lie in an AiA_i. Replace all occurrences of uu and vv by a new element ww, and color the resulting elements using the induction hypothesis.

Now color the original set by giving uu and vv the same color given to ww.

\square

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.