A High Schooler’s Favorite Puzzle

A teacher gives candy to trios of students. Every possible trio gets a turn exactly once, but no trio may share a student with the trio immediately before it. For every trio to be served this way, what is the smallest the class can be?

The Fiddler, Zach Wissner-Gross, April 4, 2025(original post)

Solution

Order the $\binom{n}{3}$ trios so that consecutive ones are disjoint: this is a Hamiltonian path in the Kneser graph $\mathrm{KG}(n,3)$ (vertices are trios, edges join disjoint trios). Two disjoint trios already need $6$ students, so $n\ge6$; but for $n=6$ every trio has exactly one disjoint partner, so the graph is a perfect matching with no Hamiltonian path. At $n=7$ a Hamiltonian path exists, so the answer is $$\boxed{7}\ \text{students}\quad(\text{all }\tbinom{7}{3}=35\text{ trios}).$$

The computation

Build the Kneser graph (trios joined when disjoint) and ask whether a single path visits every trio once. Brute depth-first search confirms no such ordering at $n=6$ and one at $n=7$.

import itertools as it
def ham_path(n, k):
    subs = list(it.combinations(range(n), k)); N = len(subs)
    adj = [[j for j in range(N) if i != j and not set(subs[i]) & set(subs[j])]
           for i in range(N)]
    found = [False]
    def dfs(u, vis, c):
        if found[0]: return
        if c == N: found[0] = True; return
        for v in adj[u]:
            if not vis >> v & 1: dfs(v, vis | 1 << v, c + 1)
    for s in range(N):
        dfs(s, 1 << s, 1)
        if found[0]: break
    return found[0]
print(ham_path(6, 3), ham_path(7, 3))     # False True

Extra Credit

Now the groups are of $10$ students, the class has at least $11$, and consecutive groups again share no one. At the smallest class size for which every group of $10$ is served, how many pieces of candy does each student receive?

Solution

A group of $2k$ students splits each $k$-set off from a single disjoint partner, so $\mathrm{KG}(2k,k)$ is a perfect matching; the first Hamiltonian size is $n=2k+1$ (Kneser graphs are Hamiltonian for $n\ge2k+1$). For $k=10$ that is $n=21$. Every group of $10$ is served once, so a fixed student receives one piece for each group of $10$ that contains them, which is $\binom{20}{9}$: $$\binom{20}{9}=\boxed{167960}\ \text{pieces}.$$ (The source’s value is paywalled; this is my own.)

The computation

At $n=21$ the search itself is out of brute-force reach (Kneser’s theorem supplies the Hamiltonicity), but the count is direct: a student’s pieces equal the number of $10$-groups they sit in, $\binom{20}{9}$.

from math import comb
print(comb(20, 9))                        # 167960  (groups of 10 containing one student)