A teacher is handing out candy to his students. He abides by the following rules:
- He hands out candy to groups of three students (i.e., “trios”) at a time. Each member of the trio gets one piece of candy.
- Each unique trio can ask for candy, but that same trio can’t come back for seconds. If students in the trio want more candy, they must return as part of a different trio.
- When a trio gets candy, the next trio can’t contain any students from that previous trio.
It turns out that every possible trio can get a helping of candy together. What is the smallest class size for which this is possible?
Obviously, I assume that we are not talking about the trivial case of $N=3$ students, because, ... lame!
So let's assume that there are $N \gt 3$ students. Then there will be $$M = \binom{N}{3} = \frac{1}{6}N(N-1)(N-2)$$ possible trios in the class. Let's assume that the set $V = \{ v_1, v_2, \dots, v_M \}$ enumerates all such trios. Based on the teacher's final condition, we can see that if $v_i$ and $v_j$ share a common student, then $v_j$ cannot be the next trio to ask if $v_i$ has just received candy. Let's define a set of edges on the vertex set $$E = \{ (v_i, v_j) \in V \times V \mid j \gt i, v_i \cap v_j = \emptyset \},$$ that is, if the trio $v_i$ could immediately follow the trio $v_j$ (or vice versa), then there is an edge between $v_i$ and $v_j.$ We will call vertices $v_i$ and $v_j$ adjacent if there is an edge $e \in E$ connecting $v_i$ and $v_j.$ Let's define the graph $\mathcal{G} = (V, E).$ Note that we define the degree of a vertex, denoted $\delta(v)$, to be the number of vertices $w \in V$ that are adjacent to $v,$ that is, $$\delta(v) = \# \{ w \in V \mid e = (v,w) \in E \}.$$
Since it turns out that every possible trio can get a helping of candy together, but based on the second condition each trio can only ask for candy once, then there must be some path that on $\mathcal{G}$ that visits each vertex exactly once. This type of path is known in graph theory as a Hamiltonian path. A graph is called Hamiltonian if it admits a Hamiltonian path starts and ends at adjacent vertices. The Norwegian graph theorist Øystein Ore provided the following sufficient condition for a graph to Hamiltonian based on the degrees of its vertices:
Ore's Theorem: A graph $\mathcal{G} = (V, E)$ with $|V| = n$ is Hamiltonian if for every pair of non-adjacent vertices $v, w \in V,$ $$\delta(v) + \delta(w) \geq n.$$
Let's note that for our graph $\mathcal{G}_N$, since any vertex $v$ is adjacent to any other trio made up of distinct students, we have $$\delta(v) = \binom{N-3}{3} = \frac{1}{6} (N-3)(N-4)(N-5) = \frac{N^3 -12N^2 + 47N - 60}{6}.$$ So from an application of Ore's theorem, whenever $$M = \frac{N^3-3N^2+2N}{6} \leq 2 \frac{N^3 -12N^2 +47N - 60}{6}$$ or equivalently, whenever $$N^3 - 21N^2 +92N -120 \geq 0,$$ then $\mathcal{G}$ is Hamiltonian. Since the real root of the polynomial $p(t) = t^3 -21t^2 +92t -120$ is at $t^* \approx 15.59....$ we have that whenever $N \geq 16,$ then every possible trio can have a helping of candy together.
No comments:
Post a Comment