# Green Hexagons Puzzle

Start by choosing some hexagons to be green. If a hexagon is touching at least 3 green hexagons, it becomes green. This repeats for as long as possible. What's the minimal number of initial green hexagons to make all hexagons green? Here we see 3 layers of hexagons. What if there were n layers?

• Is this an [optimization] problem? If so, are you aware of a provably optimal solution? Commented May 14, 2023 at 16:07
• @JaapScherphuis Look at the center hexagon in the grid pictured. That's a grid with 1 layer. Now surround that with 6 hexagons. That's a grid with 2 layers. The grid pictured has 3 layers, etc. Commented May 14, 2023 at 16:24
• @bobble I had a solution which I suspected was minimal, but no proof. The answer by Quuxplusone beats my solution, so I guess I have an upper bound. If this question no longer belongs here we can delete it, but I think it would be interesting to hear what others have to say regarding an upper bound or proof of an optimal solution, so personally, I hope it's acceptable as is. Commented May 14, 2023 at 16:28

For three layers of hexagons, the minimal answer is

five

:

          .
.   .
G   G   G
.   .
.   .   .
G   .
.   .   .
.   .
G

which fills in like this. 1 hexes fill in on turn 1, 2 on turn 2, etc., until the whole board is green after turn 6.

          5
2   4
G   G   G
1   3
2   2   5
G   4
5   3   .
4   5
G

I have no particular insight into the general solution for larger boards.

UPDATE: For four layers (37 cells), the minimal solution is

seven:

           9
5   8
2   4   7
G   G   G   G
1   3   6
2   2   5   8
G   4   7
5   3   6   9
4   5   8
9   G   7   .
8   6   9
7   8
G

This pattern already strongly suggests that the answer for n layers is always

2n+1

initially green tiles, laid out in the

"7"-shaped

pattern apparent from these examples.

• I thought the answer was 6, so this is very interesting. Based on your answer, I think every time you add a layer, you add 2 greens, maintaining the < shape for the initial configuration, but I don't have a proof this is minimal. Commented May 14, 2023 at 16:35
• I think you mean to say "four layers" Commented May 15, 2023 at 3:35
• (...and so your answer for n layers is correctly incorrect.) Commented May 15, 2023 at 4:22
• @RichardBirkett: Thanks — edited! Commented May 17, 2023 at 17:01

Proof that 5 is minimal:

Note that the perimeter of the green region never increases. Every time a hexagon turns green, you lose at least 3 edges, and gain at most 3 edges. Since the final configuration has a perimeter of 30, there must be at least 30/6 = 5 green hexagons at the start.

For larger configurations, this gives a lower bound of

2n-1 hexagons

• Remark: @Quuxplusone gave a strategy that attains this bound, so we have optimised the problem. If the proof of their strategy for n layers is not obvious, I am happy to provide it in an answer, but the credit should be theirs. It is a proof by induction. Commented May 15, 2023 at 4:19
• @RichardBirkett Please do! Commented May 15, 2023 at 9:12
• FWIW, I gave an apparent strategy that attains this bound. I didn't prove that my strategy always does fill the whole board (for larger n). It sure looks like it does; and I bet someone can prove it in a single paragraph that's obvious in hindsight; but I don't take any credit for proving it. :) Btw, the very neat trick of trading off perimeter for area is used to even greater effect in Green Triangles! Commented May 19, 2023 at 21:35