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

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

2 Answers 2

Reset to default
9
$\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.

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

Improve this answer
$\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$
    – Richard Birkett
    May 15 at 4:19
  • $\begingroup$ @RichardBirkett Please do! $\endgroup$
    – PuzzleAndy
    May 15 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$
    – Quuxplusone
    May 19 at 21:35

Your Answer

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

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