This week the question is: Can You Grow a Hibiscus Hedge? #permutation #sequence

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. (But a prior ordering can appear in reverse. For example, ROYOR is an acceptable hedge, but ROYROY is not.)

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

And for extra credit:

In addition to red, orange, and yellow hibiscus flowers, Dean now includes a fourth color: pink. Again, he wants to plant a straight hedge of shrubs that appears somewhat random. Here are the rules for ordering the shrubs this time:

– No two adjacent shrubs have the same color. – No ordering of four consecutive shrubs appears more than once in the hedge. (Again, a prior ordering can appear in reverse.) – Among any group of four consecutive shrubs, at least three distinct colors are represented.

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

Intermission.

I am sort of obsessed with the candy puzzle from last week. Handled correctly, it’s possible to see, that the important graph has a structure, and that this structure can be used to find the required path. (This picture has a few connections missing, but hopefully it still demonstrates the principle.)

Oh! And I’ve just discovered that years ago a similar puzzle was featured on the riddler. Scroll down to the classic solution.

Last week I had to guess at the solution to the extra credit question. As it happens, I had the right idea: 21 students. But that wasn’t what the question actually asked for. Sigh. Read the question carefully, next time, me! Anyway. I got 21 points out of 26 possible in Q1. Actually not bad.

Highlight to reveal (possibly incorrect) solution:

Related problem. Program.

What are we actually looking for here?

We are interested in the permutations of the 3 colors with 3 elements. However, a permutation cannot have 2 neighbors with the same color. And in the final sequence, a permutation can appear at most once.

My program (brute forcing all possible sequences) tells me, 1) there are 12 of these permutations, 2) it is possible to build a sequence with all of them, and this sequence therefore has length 14.

One possible sequence: ROROYRYOYORYRO.

And for extra credit:

Now there are 4 colors and the permutations have 4 elements. As an extra requirement, each permutation has at least 3 colors. (Having a similar requirement doesn’t change anything in the fiddler case.)

My program tells me, 1) there are 96 of these permutations, 2) it is possible to build a sequence with all of them, and this sequence therefore has length 99.

One possible sequence (split up in smaller chunks for readability):

RORYRORPRO
YROYOROYPR
OPRYRPRYOR
YOYRYOPRPO
ROPORYPRYP
ORPOYRPOPY
ROPYORPYRY
PYRPYOYPOY
OPOYPYOPYP
RPYPOPROR