Monday, April 14, 2025

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.$

No comments:

Post a Comment