Team Selection Tests

The answer to the problem depends on the values of $n$. We have the following cases

* If $n = 3$ then it is obvious that $k_n = 1$.

* If $n = 4$ then $k_n = 4$ because $A_4$ has 4 subsets with 3 elements. For example, color (1, 2) blue and (3, 4) red. Each set contains one of the two numbers above, so it has two colors.

* If $n = 5$ then $k_n \le 10$ because $A_5$ has 10 subsets with 3 elements. According to pigeonhole principle, since $n = 5$, there are at least 3 elements of $A_5$ of the same color, so the subset with these 3 elements does not satisfy the problem. So $k_n \le 9$. For $k_n = 9$, say $\{x, y, z\}$ is a subset that is not taken. Coloring $x, y, z$ in red and the other two numbers in blue. Since $K = \{x, y, z\}$ is not chosen, and $|A_5 \setminus K| = 2$, every selected subset has an element of $K$ and an element that is not in $K$. Therefore, every selected subset has two different colors.

* If $n = 6$, since $k_5 = 9$ then $k_6 \le 10$ because one can take 10 subsets of $A_5$ that can not be colored to satisfy the problem. We show that 9 is the answer in this case. Since there are 10 pairs of 3-subsets of $A_6$, and the union of two subsets each is equal to $A_6$, there exists a pair where both sets are not selected. Coloring the first set in green, the second set in red. Obviously every selected subset intersects with one of the above two subsets, since if it doesn't intersect the first set then it has at most 3 elements, and it must be the second set, a contradiction. So $k_6 = 9$.

Finally $n \ge 7$ is the hardest case. Consider the following subsets $\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\}$.
We will show that there is no satisfactory coloring of $A_n$ in this case. Assuming 1 is blue, then (2, 3), (4, 5), (6, 7) have a symmetrical role, and each pair can't all be blue. If (2, 3) is both red then 4 or 6 is blue, assuming 4 is blue, then 5 is red because $\{1, 4, 5\}$ cannot be the same green. Since $\{3, 5, 6\}$ is not the same red, 6 is blue. Finally, $\{2, 5, 7\}$ is not all red, $\{1, 6, 7\}$ is not all green so there is no way to color the number 7.

Next, consider the case of 2 is blue and 3 is red. As mentioned, (4, 5) and (6, 7) have a symmetric role. Similarly for (2, 3) then these pairs do not have the same color. Now, it is easy to see that 4 cases of color of pairs (4, 5) and (6, 7) lead to absurdity. For example 4, 6 is in the same set as 2 and 3 so they cannot be the same color and neither 4, 7.

Let $A_1, A_2, \dots, A_6$ be the selected sets and $A = A_1 \cup \dots \cup A_6$. We prove the problem according to the maximum number of times an element of $A$ belongs to one of 6 chosen subset. Assume $1 \in A$ is the element that occurs most times. In the argument below, a set is said to be selected if it is some $A_i$ with $i \in \{1, \dots, 6\}$.

* If 1 appears 6 times then color 1 red and $A \setminus \{1\}$ green. Since 1 belongs to a set of 6, each set has a red element and only 1 of red elements, so each set has 2 of blue elements.

* If 1 appears 5 times then color 1 in red. Assume $A_6 = \{x, y, z\}$ does not contain 1. Color $x$ red, $y$ and $z$ green. Since there are 2 red elements, there is no set that has 3 red elements and since $A_1, A_2, \dots, A_5$ contains 1, they have at least one red element.

* If 1 appears 4 times, assume $A_5$ and $A_6$ do not contain 1. If there exists $x$ that both belong to $A_5$ and $A_6$, color 1, $x$ in red and the remaining elements of $A_n$ in blue. The statement can be proved as in previous case. Conversely, if $A_5 \cap A_6 = \emptyset$ then there are 9 pairs $(a, b)$ where $a \in A_5$ and $b \in A_6$. Since there is only 4 subset containing 1, according to the pigeonhole principle there exist $a \in A_5$ and $b \in A_6$ such that $\{1, a, b\}$ is not selected. Color 1, $a$, $b$ red and the rest of the elements blue. Since there are exactly 3 of red elements and $\{1, a, b\}$ is not selected, every set has two colors.

* If 1 appears 3 times and is not in $A_4, A_5, A_6$. Let $x$ be the element that belongs to the most sets in this set 3. If $x$ appears 3 times then color 1, $x$ in red and this way satisfies the problem. If $x$ occurs twice, and is not in $A_6$, then we show that there is $y \in A_6$ so that $\{1, x, y\}$ is not selected. Indeed, $x$ appears at most 3 times because 1 occurs the most, but $x \in A_4, A_5$ so it is chosen in 1 other subset. So there is an element of $A_6$ which is $y$ so that $\{1, x, y\}$ is not selected. Fill these three elements with red, the rest with blue to satisfy the problem. Finally, if every element in $A_4, A_5, A_6$ appears exactly 1 times, similar to the case where 1 appears 4 times, we will show there is
$$(x, y, z) \in A_4 \times A_5 \times A_6$$
such that the subsets $A_1, A_2, A_3$ do not have the form $\{1, a, b\}$ where $a, b \in \{x, y, z\}$. There are 3 pairs $(a, b)$ for which $\{1, a, b\}$ is chosen. However, for a pair $(a, b)$, there exists at most 7 elements $c$ belonging to $A_4 \cup A_5 \cup A_6$ so that $(a, b, c) \in A_4 \times A_5 \times A_6$. Thus, there are at most 21 tuples $(a, b, c) \in A_4 \times A_5 \times A_6$ such that two of three elements of this tuple together with 1 form a chosen set. There are 27 tuples $(x, y, z) \in A_4 \times A_5 \times A_6$ so there is a tuple $(x, y, z)$ that every 2 of its elements does not form with 1 a selected set. Coloring 1, $x, y, z$ in red and the remaining numbers in blue to satisfy the problem.

* If 1 appears 2 times and belongs to $A_1, A_2$. Assume 2 is the element that occurs most times in $A_3 \cup \dots \cup A_6$. We have the following cases

- If 2 occurs 2 times in $A_3, \dots, A_6$, then 1 and 2 do not appear together. We consider 1 and 2 to be the same element $x$ and $x$ that appear 4 times, reducing the problem to the case where 1 occurs 4 times.
- If 2 occurs 1 times, that means $A_3 \cup \dots \cup A_6$ has 12 elements and there exists an element that is not in $A_1 \cup A_2$. Assuming it's $y$, again let 1 and $y$ be the same element $x$ appearing 3 times, reducing the problem to the case where 1 occurs 3 times.

* If 1 appears 1 times, then every element appear once. Choose an arbitrary element from each set and color them red. Other elements are blue.

So we have $k_3 = 1, k_4 = 4, k_5 = k_6 = 9$ and $k_n = 6, \forall n \ge 7$. $\square$