Paying attention to the hints

Dean has three colors of the hibiscus: red, orange, and yellow. He wants to plant them in a straight hedge of shrubs (each of which is one color) so that the order appears somewhat random, but not truly random. More specifically, he wants the following to be true:

• No two adjacent shrubs have the same color.
• No ordering of three consecutive shrubs appears more than once in the hedge.

What is the greatest number of shrubs Dean’s hedge can contain?

I should have picked up on the otherwise extraneous information regarding Rivka Lipkovitz's interest in the base-$7$ Doomsday algorithm to divine that my Ore's theorem base upper bound was not exactly the sharpest bound in the shed. Well, you can't fool me again! I know that since I did indeed like the previous week's Fiddler involved Hamiltonian cycles, that somehow this one will too ....

So let's design Dean's hedge instructions as a directional graph. Let $O$ denotes an orange hibiscus, $R$ a red one, and $Y$ a yellow one. Then a triplet $v = (v_1,v_2,v_3)$ with $v_i \in \{O,R,Y\}$ with $v_2 \ne v_1$ and $v_3 \ne v_2$ is one of the possible orderings of three consecutive shrubs that satisfies both of the conditions. Let

$$V = \{ ORO, ORY, OYO, OYR, ROR, ROY, RYO, RYR, YOR, YOY, YRO, YRY \}$$ be the set of vertices. We can draw a directional edge between $v_1$ and $v_2$ if the first two characters of $v_2$ are the last two characters of $v_1,$ so for instance, there is an edge from $RYR$ to $YRO$ but not one that starts at $YRO$ and ends at $RYR.$ Thus all possible edges are $$E = \{ (v_1, v_2) \mid v_{12} = v_{21}, v_{13} = v_{22} \}.$$

Sure enough, there is a Hamiltonian cycle on the graph $G = (V,E)$ covering all $12$ possible vertices, which gives a maximal Dean-approved hibiscus hedge length of 14 shurbs (count the first three shrubs of the initial vertex, then each subsequent vertex only adds one new shrub so $3 + 11 = 14$). One possible instance of this Hamiltonian cylce is given by

$$\begin{align*} ORO \to ROY \to OYO &\to YOR \to ORY \to RYO \to YOY\\ &\to OYR \to YRY \to RYR \to YRO \to ROR \to ORO,\end{align*}$$ which when put altogether gives a hedge denoted as $OROYORYOYRYROR.$

Striking Ore while digging into Lipkovitz's Hamiltonian puzzle

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.