Problem 1130

Assume there exists a set $\mathscr{S}$ of sets of three children such that any set of two children is a subset of exactly one member of $\mathscr{S}$, and assume that the children $A$ and $B$ make a common present to $C$ if and only if $\{A, B, C\} \in \mathscr{S}$. Then it is true that any two children $A$ and $B$ make a common present to exactly one other child $C$, namely the unique child such that $\{A, B, C\} \in \mathscr{S}$. Because $\{A, B, C\}=\{A, C, B\}$ it is also true that if $A$ and $B$ make a present to $C$ then $A$ and $C$ make a present to $B$. We shall construct such a set $\mathscr{S}$.

Let $A_{1}, \ldots, A_{n}, B_{1}, \ldots B_{n}, C_{1}, \ldots, C_{n}$ be the children, and let the following sets belong to $\mathscr{S}$. (1) $\left\{A_{i}, B_{i}, C_{i}\right\}$ for $1 \leq i \leq n$. (2) $\left\{A_{i}, A_{j}, B_{k}\right\},\left\{B_{i}, B_{j}, C_{k}\right\}$ and $\left\{C_{i}, C_{j}, A_{k}\right\}$ for $1 \leq i<j \leq n, 1 \leq k \leq n$ and $i+j \equiv 2 k(\bmod n)$. We note that because $n$ is odd, the congruence $i+j \equiv 2 k(\bmod n)$ has a unique solution with respect to $k$ in the interval $1 \leq k \leq n$. Hence for $1 \leq i<j \leq n$ the set $\left\{A_{i}, A_{j}\right\}$ is a subset of a unique set $\left\{A_{i}, A_{j}, B_{k}\right\} \in \mathscr{S}$, and similarly the sets $\left\{B_{i}, B_{j}\right\}$ and $\left\{C_{i}, C_{j}\right\}$. The relations $i+j \equiv 2 i(\bmod n)$ and $i+j \equiv 2 j(\bmod n)$ both imply $i \equiv j(\bmod n)$, which contradicts $1 \leq i<j \leq n$. Hence for $1 \leq i \leq n$, the set $\left\{A_{i}, B_{i}, C_{i}\right\}$ is the only set in $\mathscr{S}$ of which any of the sets $\left\{A_{i}, B_{i}\right\}\left\{A_{i}, C_{i}\right\}$ and $\left\{B_{i}, C_{i}\right\}$ is a subset. For $i \neq k$, the relations $i+j \equiv 2 k$ $(\bmod n)$ and $1 \leq j \leq n$ determine $j$ uniquely, and we have $i \neq j$ because otherwise $i+j \equiv 2 k(\bmod n)$ implies $i \equiv k(\bmod n)$, which contradicts $i \neq k$. Thus $\left\{A_{i}, B_{k}\right\}$ is a subset of the unique set $\left\{A_{i}, A_{j}, B_{k}\right\} \in \mathscr{S}$. Similarly $\left\{B_{i}, C_{k}\right\}$ and $\left\{A_{i}, C_{k}\right\}$. Altogether, each set of two children is thus a subset of a unique set in $\mathscr{S}$.

1. Labeling the Children:
Let the children be labeled as $X_i, Y_i, Z_i$ for $0 \leq i \leq n-1$. We will consider the subscripts modulo $n$. The key observation here is that $2$ is invertible modulo $n$ when $n$ is odd. This means there exists an integer $k$ such that $2k \equiv 1 \pmod{n}$.

2. Forming Initial Triples:
We need to form triples such that each pair of children makes a present to exactly one other child. First, we create the triples $(X_i, Y_i, Z_i)$ for each $i$. This ensures that within each triple, the pairs $(X_i, Y_i)$, $(Y_i, Z_i)$, and $(Z_i, X_i)$ make presents to the third child in the triple.

3. Forming Additional Triples:
For $i \neq j$, if $k$ is equal to $\frac{i+j}{2}$ modulo $n$, we form the following triples:
$$(X_i, X_j, Y_k), \quad (Y_i, Y_j, Z_k), \quad (Z_i, Z_j, X_k)$$
This step ensures that any two children labeled with the same letter (e.g., $X$) are paired with a child labeled with a different letter (e.g., $Y$).

4. Verification of the Grouping:
Given two children $X_a$ and $Y_b$ (with $a \neq b$), we need to determine the third child in the triple. According to our construction, the third child is $X_{2b-a}$. This is because:
$$k = \frac{a + b}{2} \implies 2k = a + b \implies k = \frac{a + b}{2} \pmod{n}$$
Therefore, the triple $(X_a, Y_b, X_{2b-a})$ is well-defined. Similarly, the pair $Y_b, X_{2b-a}$ implies that $X_a$ is the third child by the same rule.

5. Ensuring the Condition:
We need to ensure that for any three children $A, B,$ and $C$ in the class, if $A$ and $B$ make a present to $C$, then $A$ and $C$ make a present to $B$. This is satisfied by our construction because:
- If $(A, B) \to C$, then $(A, C) \to B$ and $(B, C) \to A$ are automatically satisfied by the symmetry of our triples.

Thus, the construction satisfies the given condition for all odd $n$.

$\blacksquare$