Can You Grow a Hibiscus Hedge?

Dean plants a hedge using three shrub colours (red, orange, yellow). No two adjacent shrubs may match, and no ordered run of three consecutive shrubs may repeat anywhere in the hedge. What is the greatest number of shrubs?

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

Solution

Build a de Bruijn graph whose vertices are the valid colour pairs ($x\neq y$, six of them) and whose edges are the valid triples ($x\neq y\neq z$, twelve of them). A hedge is a walk that uses no triple twice, i.e. a trail; using every triple once is an Eulerian trail, which exists here (the graph is connected and balanced). Twelve triples make a sequence of $$12+2=\boxed{14}\ \text{shrubs}$$ (for example RORYROYRYOYORO).

The computation

Lay out the de Bruijn graph (valid triples as edges between valid pairs) and check it admits an Eulerian trail; the longest hedge then uses all twelve triples, $12+2$ shrubs.

import networkx as nx
G = nx.MultiDiGraph()
for x in 'ROY':
    for y in 'ROY':
        if x != y:
            for z in 'ROY':
                if y != z: G.add_edge((x, y), (y, z))
print(nx.has_eulerian_path(G), G.number_of_edges() + 2)   # True 14

Extra Credit

With four colours (adding pink), no two adjacent equal, no ordered run of four consecutive repeated, and every four consecutive shrubs showing at least three distinct colours, what is the greatest length?

Solution

Now the vertices are valid triples and the edges are the valid four-runs (distinct neighbours and at least three colours): there are $96$ such edges on $36$ vertices, and the graph is connected and balanced, so an Eulerian trail uses all $96$. That gives $$96+3=\boxed{99}\ \text{shrubs}.$$ (The source’s value is paywalled; this is my own.)

The computation

Enumerate the valid four-runs, then check the in/out degrees balance at every triple (so an Eulerian trail exists); the length is the edge count plus three.

import itertools as it
from collections import defaultdict
ok = lambda q: q[0] != q[1] and q[1] != q[2] and q[2] != q[3] and len(set(q)) >= 3
quads = [q for q in it.product('ROYP', repeat=4) if ok(q)]
deg = defaultdict(int)
for q in quads: deg[q[:3]] += 1; deg[q[1:]] -= 1
print(len(quads) + 3, all(v == 0 for v in deg.values()))   # 99 True (balanced -> Eulerian)