Each student at a school divided 18 subjects into six disjoint triples. Could it happen that every triple of subjects is among the triples of exactly one student?
Problem
Source: 239 School Open MO, 2023, Senior league, Problem 7
Tags: combinatorics, set theory
23.12.2024 08:24
The answer is yes. Identify subjects as elements of $\mathbb{Z}/6\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$. I'll also assume that subject triples are unordered; this doesn't change the problem, since to obtain a construction for ordered triples we simply take the unordered triples and apply all $3!$ permutations on each family. We are being asked to partition three-subject triples into pairwise-disjoint families of six triples each. We choose the family for a subject triple $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ as follows: If all $x_i$ are distinct, then let $\mathbb{Z}/6\mathbb{Z} \setminus \{x_1,x_2,x_3\}=\{x_1',x_2',x_3'\}$ and form the family out of $\{(x_1,y_1+i),(x_2,y_2+i),(x_3,y_3+i)\}$ and $\{(x_1',y_1+i),(x_2',y_2+i),(x_3',y_3+i)\}$ for $0 \leq i \leq 2$. If all $y_i$ are distinct, so form a family out of $\{(x_1+i,y_1),(x_2+i,y_2),(x_3+i,y_3)\}$ for $0 \leq i \leq 5$. Otherwise, there must be exactly two distinct values among the $x_i$ and $y_i$. WLOG let $y_1=y_2$ and $x_1=x_3$. Then there are two subcases If $x_1-x_2 \in \{-1,1\}$, then let $y'$ be the element of $\mathbb{Z}/3\mathbb{Z}$ not in $\{y_1,y_2,y_3\}$ and form the family out of $\{(x_1+2i,y_1),(x_2+2i,y_1),(x_1+2i,y_3)\}$ and $\{(x_1+2i,y'),(x_2+2i,y'),(x_2+2i,y_3)\}$ for $0 \leq i \leq 2$. If $x_1-x_2 \in \{-3,3\}$, then define $y'$ as before and form the family out of $\{(x_1,y_1),(x_2,y_1),(x_1,y_3)\}$, $\{(x_1,y'),(x_2,y'),(x_2,y_3)\}$, $\{(x_1+1,y_1),(x_1-1,y_1),(x_1+1,y_3)\}$, $\{(x_1+1,y'),(x_1-1,y'),(x_1-1,y_3)\}$, $\{(x_2+1,y_1),(x_2-1,y_1),(x_2+1,y_3)\}$, and $\{(x_2+1,y'),(x_2-1,y'),(x_2-1,y_3)\}$. Collectively, these families also cover all cases where $x_1-x_2 \in \{-2,2\}$. It's easy to check that these families contain pairwise disjoint triples, and that they are defined consistently regardless of which representative "starting element" is used.