Problem 1703

(a) Proving that 4 colors are sufficient:

1. Let the 4 colors be $A, B, C, D$.
2. Color all 3-element subsets of $X$ whose largest element is at most 5 with color $A$. These subsets are:
$$\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{1, 3, 4\}, \{1, 3, 5\}, \{1, 4, 5\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}$$
3. Color all 3-element subsets of $X$ whose largest element is 6 with color $B$. These subsets are:
$$\{1, 2, 6\}, \{1, 3, 6\}, \{1, 4, 6\}, \{1, 5, 6\}, \{2, 3, 6\}, \{2, 4, 6\}, \{2, 5, 6\}, \{3, 4, 6\}, \{3, 5, 6\}, \{4, 5, 6\}$$
4. Color all 3-element subsets of $X$ whose largest element is 7 with color $C$. These subsets are:
$$\{1, 2, 7\}, \{1, 3, 7\}, \{1, 4, 7\}, \{1, 5, 7\}, \{1, 6, 7\}, \{2, 3, 7\}, \{2, 4, 7\}, \{2, 5, 7\}, \{2, 6, 7\}, \{3, 4, 7\}, \{3, 5, 7\}, \{3, 6, 7\}, \{4, 5, 7\}, \{4, 6, 7\}, \{5, 6, 7\}$$
5. Color all 3-element subsets of $X$ whose largest element is 8 with color $D$. These subsets are:
$$\{1, 2, 8\}, \{1, 3, 8\}, \{1, 4, 8\}, \{1, 5, 8\}, \{1, 6, 8\}, \{1, 7, 8\}, \{2, 3, 8\}, \{2, 4, 8\}, \{2, 5, 8\}, \{2, 6, 8\}, \{2, 7, 8\}, \{3, 4, 8\}, \{3, 5, 8\}, \{3, 6, 8\}, \{3, 7, 8\}, \{4, 5, 8\}, \{4, 6, 8\}, \{4, 7, 8\}, \{5, 6, 8\}, \{5, 7, 8\}, \{6, 7, 8\}$$
6. Since any two disjoint 3-element subsets must have their largest elements different, they will be colored differently. Thus, 4 colors are sufficient.

(b) Proving that 3 colors are not sufficient:

1. Assume we have 3 colors $A, B, C$ and a valid coloring.
2. Claim: There exists a pair of 3-element subsets that have two elements in common and have different colors.
3. Proof: Assume otherwise. Then all pairs of 3-element subsets that share two elements must have the same color. Consider the subsets:
$$\{1, 2, 3\}, \{1, 2, 4\}, \{1, 4, 5\}, \{4, 5, 6\}$$
These subsets must all have the same color, which is a contradiction since they are not all disjoint.
4. Assume without loss of generality that $\{1, 2, 3\}$ is colored $A$ and $\{1, 2, 4\}$ is colored $B$.
5. All 3-element subsets of $\{5, 6, 7, 8\}$ must be colored $C$ since they are disjoint with both $\{1, 2, 3\}$ and $\{1, 2, 4\}$.
6. If a 3-element subset has exactly one element in the set $\{5, 6, 7, 8\}$, it is disjoint with one of $\{5, 6, 7\}, \{5, 6, 8\}, \{5, 7, 8\}, \{6, 7, 8\}$, so it cannot be colored $C$, and it must be colored with $A$ or $B$.
7. $\{3, 5, 6\}$ is disjoint with $\{1, 2, 4\}$, so it must be colored with $A$ or $C$. $\{4, 7, 8\}$ is disjoint with $\{1, 2, 3\}$, so it must be colored with $B$ or $C$.
8. Since $\{3, 5, 6\}$ and $\{4, 7, 8\}$ are disjoint, they can't both be colored $C$. So either $\{3, 5, 6\}$ is colored $A$, $\{4, 7, 8\}$ is colored $B$, or both.
9. Without loss of generality, assume $\{3, 5, 6\}$ is colored $A$.
10. Then $\{1, 2, 7\}$ is colored $B$ since it has exactly one element in $\{5, 6, 7, 8\}$ and it is disjoint with $\{3, 5, 6\}$.
11. By similar reasoning, $\{3, 4, 8\}$ is colored $A$, $\{1, 2, 5\}$ is colored $B$, $\{4, 7, 8\}$ is colored $C$, and $\{2, 5, 6\}$ is colored $B$.
12. But $\{1, 4, 7\}$ can't be colored $A$ or $B$ because it is disjoint with $\{3, 5, 6\}$ and $\{2, 5, 6\}$, and can't be colored $C$ because it has exactly one element in $\{5, 6, 7, 8\}$. Therefore, 3 colors are not sufficient.