8
$\begingroup$

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?

enter image description here

$\endgroup$
3
  • $\begingroup$ Is this an [optimization] problem? If so, are you aware of a provably optimal solution? $\endgroup$
    – bobble
    May 14, 2023 at 16:07
  • $\begingroup$ @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. $\endgroup$
    – PuzzleAndy
    May 14, 2023 at 16:24
  • $\begingroup$ @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. $\endgroup$
    – PuzzleAndy
    May 14, 2023 at 16:28

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – PuzzleAndy
    May 14, 2023 at 16:35
  • 2
    $\begingroup$ I think you mean to say "four layers" $\endgroup$ May 15, 2023 at 3:35
  • $\begingroup$ (...and so your answer for n layers is correctly incorrect.) $\endgroup$ May 15, 2023 at 4:22
  • $\begingroup$ @RichardBirkett: Thanks — edited! $\endgroup$ May 17, 2023 at 17:01
14
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ May 15, 2023 at 4:19
  • $\begingroup$ @RichardBirkett Please do! $\endgroup$
    – PuzzleAndy
    May 15, 2023 at 9:12
  • $\begingroup$ 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! $\endgroup$ May 19, 2023 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.