Competition problem — Combinatorics

Library / /9 of 15

Combinatorics Difficulty 8.0 Shortlist Prove it Romania

Consider a finite collection of 3-element sets $A_i$ no two of which share more than one element, whose union has cardinality $2017$ . Show that the elements of this union can be coloured one of two colours, blue and red, so that at least $64$ elements are blue, and each $A_i$ contains at least one red element.

Solution

Let $U$ be the union of the $A_i$ . It is sufficient to show that a maximal (relative to set-theoretic inclusion) subset $T$ of $U$ containing no $A_i$ satisfies the required cardinality condition.

By maximality, for each element $x$ of $U \setminus T$ , there exists a 2-element subset $S$ of $T$ such that $S \cup \{x\}$ is an $A_i$ .

If $x$ and $x'$ are distinct elements of $U \setminus T$ , and $S$ and $S'$ are 2-element subsets of $T$ such that $S \cup \{x\}$ and $S' \cup \{x'\}$ are both amongst the $A_i$ , then $S$ and $S'$ are also distinct, since two distinct $A_i$ 's share at most one element.

Therefore, choosing for each $x$ in $U \setminus T$ a 2-element subset $S$ of $T$ such that $S \cup \{x\}$ is an $A_i$ defines an injection of $U \setminus T$ into the collection of 2-element subsets of $T$ . Consequently, $|U| - |T| = |U \setminus T| \le \binom{|T|}{2}$ , so $|T| \ge (-1 + \sqrt{8|U| + 1})/2$ ; if $|U| = 2017$ , then $|T| \ge 64$ .

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.