13
$\begingroup$

On a magic chessboard of infinite size, the squares are either wooden or golden. If 4 or more of its 8 neighbors (a king's move away) are golden, a wooden square becomes golden the next day. Golden squares stay golden forever.

On day one, all squares are wooden, but you're allowed to switch 100 squares to golden ones. You want as many squares as possible to become golden ultimately. How should you choose your squares? How many golden squares can you get eventually?

Edit

Hmmm, I just discovered a game with the same rule was asked before. The answer there gives an upper bound on how much golden squares you can produce, and also a wonderful toy to simulate the game of life. Have fun!

Improve this question
$\endgroup$
0

4 Answers 4

Reset to default
16
$\begingroup$

I've achieved

5686

tiles, and can prove that this is the optimal solution.

Reasoning:

The semi-invariant we need to track is the score $X$ of pairs of adjacent squares where one is gold and one is not. Initially, $X$ is at most eight times the number of golden squares, which is $100$ in this puzzle, so $X \leq 800$, and because of how golden squares propagate the score will never increase over time.

Observe that $X$ is always even, because $X=0$ with zero golden squares and $X$ always changes by an even amount if you turn any square golden. Also note that if $X=800$ in the beginning, then the score will decrease at least once within the next four days unless the pattern stabilizes before that time. We can safely assume that the optimal pattern takes more than four days to stabilize, so we know that $X\leq 798$ by the time it does.

We are now looking for the largest possible pattern with score at most $798$. A short computer search determines that one such pattern is the octagon obtained by starting with an $86 \times 85$ rectangle and cutting off four equal triangular corners with $28$ grid squares to a side. This octagon has an area of $5686$ grid squares.

Finally, we must find an initial configuration of at most $100$ golden squares that ends up filling this entire octagon. A bit of manual experimentation in Golly lets us obtain such a configuration:

Animated solution

Aside: Finding this by hand was trickier than expected, since it is surprisingly difficult to reach all sides at once without losing any score at any time. I'm sure there are prettier solutions.

Golly 4.0+ pastable RLE of this solution:

x = 86, y = 85, rule = B45678/S012345678History
28.2EBEBEBE22B$27.32B$26.BEBE30B$25.36B$24.2BE2BE32B$23.40B$22.BEBE3B
E7BEBEBEBEBEBE16B$21.10BE33B$20.13BE17BEBEBEBE8B$19.48B$18.21BE28B$
17.52B$16.23BE30B$15.56B$14.25BE32B$13.53BEBEBEBE$12.27BE34B$11.20BE
17BE25B$10.19BE46B$9.18BE49B$8.17BE52B$7.30BE41B$6.74B$5.32BE43B$4.
78B$3.34BE45B$2.82B$.36BE47B$41BE44B$43BE42B$45BE40B$47BE10BE27B$86B$
47BE11BE26B$86B$47BE12BE25B$86B$47BE13BE24B$86B$47BE14BE23B$42BE43B$
63BE22B$42BE43B$40BE23BE21B$86B$40BE45B$38BE47B$86B$38BE47B$3BEBEBEBE
BEBEBEBEBEBE64B$38BE47B$EBE83B$38BE47B$86B$38BE35BEBEBEBEBEBEB$86B$
38BE46BE$.84B$2.36BE45B$3.80B$4.34BE43B$5.76B$6.32BE41B$7.72B$8.30BE
39B$9.68B$10.33BE32B$11.64B$12.31BE30B$13.60B$14.29BE28B$15.56B$16.
27BE26B$17.52B$18.25BE24B$19.48B$20.23BE22B$21.44B$22.21BE20B$23.40B$
24.3BE34B$25.36B$26.15BE18B$27.E31B$28.14BE15B!
Improve this answer
$\endgroup$
4
  • $\begingroup$ all i can say is wow $\endgroup$
    – JLee
    Jun 9, 2022 at 23:44
  • $\begingroup$ So did you find this optimal solution all by hand (trial and error)? That's amazing! $\endgroup$
    – Eric
    Jun 10, 2022 at 2:12
  • $\begingroup$ I am amazed at how surprisingly asymmetric and arbitrary it looks like. $\endgroup$
    – htmlcoderexe
    Jun 10, 2022 at 8:07
  • $\begingroup$ @htmlcoderexe That's because it is arbitrary. If you have a general octagon, near each of its vertices there are exactly two positions where you can place another golden square that extends the octagon without losing any score. I just repeatedly placed squares in such positions while the Golly simulation ran, with a lot of undoing and backtracking until the result fit the desired shape. $\endgroup$
    – Magma
    Jun 10, 2022 at 9:30
8
$\begingroup$

Update: Up to

5048

by introducing a small asymmetry

enter image description here

Update ends.

Original answer:

I can do

4999

using this

            ...

             x

             x

    ... x x xxx x x ...

             x

             x

            ...

setup.

This is essentially a big

cross ("+") with every other square left out except at the intersection of its arms where there are three golden squares next to each other. The arms are as even in length as possible.

Over time (1275 turns) this will fill up to a

diamond of height and width 100 give or take a square. enter image description here Final state with age of gold squares colour coded. Oldest (1275 turns) are yellow. Dark blue squares are wooden.

First few groups of steps:

            ...

             x
            333
           32x23
          3211123
    ... x x2xxx2x x ...
          3211123
           32x23
            333
             x

            ...

Improve this answer
$\endgroup$
10
  • $\begingroup$ You still have a whole 1 square you can turn into gold! $\endgroup$
    – Auribouros
    Jun 9, 2022 at 15:24
  • $\begingroup$ @Auribouros thanks. But I spent all 100. (The arms are not all the same length.) $\endgroup$
    – loopy walt
    Jun 9, 2022 at 15:43
  • $\begingroup$ I don't see how this is possible. If you're skipping every other cell then you will not have 4 neighbors to turn the next cell gold. Can you show a brief diagram of it working? $\endgroup$
    – mkinson
    Jun 9, 2022 at 15:48
  • 1
    $\begingroup$ @fljx no you don't. $\endgroup$
    – loopy walt
    Jun 9, 2022 at 16:15
  • 1
    $\begingroup$ @mkinson It is groups of steps not individual steps to reduce clutter. The grouping is by what is supported by subcrosses. Group 1 is generated by a 5 gold cross. A 7 gold cross generates groups 1 and 2 and so on. $\endgroup$
    – loopy walt
    Jun 9, 2022 at 16:37
2
$\begingroup$

While I cannot beat loopywalt's answer, my construction got just over halfway there. I'm posting it in case it sparks ideas for better constructions.

Illustrated here is a smaller version, with base length $b=8$ and sides of height $h=6$, using a total of $8+6$ squares.

enter image description here

It fills to a $b\times (h+1)$ rectangle with $2$ corners missing, area $b(h+1)-2$.
A solution with $b=50$ and $h=50$ produces a score of $50^2-2=2548$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I don't see how your diagram works? If I start with the lower-left corner I can fill in two boxes, and then another two on the lower right corner, but then there's no further growth. No other cells have 4 boxes around them. $\endgroup$
    – mkinson
    Jun 9, 2022 at 15:54
  • 1
    $\begingroup$ @mkinson Oops! I fixed i now. I thought I had a trick to add one extra row, but as you pointed out that did not work, so I had to revert to using a straight base. $\endgroup$
    – Jaap Scherphuis
    Jun 9, 2022 at 16:06
1
$\begingroup$

I can get up to

2428

How do:

It starts a bit like @loopy walt's answer, making a size 25 diamond, 4 to be precise, when all 4 diamonds are done, their vertices touch (making something a bit like this)
◆◆
◆◆
This will then create 3 additional diamonds (4 halves from the outer empty triangles and 1 full from the inner gap), which should amount to 2428

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Are you sure this works? Those 4 size 25 diamonds fit in a 50x50 box, therefore can not create more than 2500 squares. I think you dropped a factor of 1/4. $\endgroup$
    – loopy walt
    Jun 9, 2022 at 14:35
  • $\begingroup$ It does fit in a 50x50 box, I had a math problem and will fix $\endgroup$
    – Auribouros
    Jun 9, 2022 at 14:45
  • $\begingroup$ The ending shape is basically a 50x50 square with its corners cut, which is 72 squares less from a perfect square. $\endgroup$
    – Auribouros
    Jun 9, 2022 at 15:23

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.