B234/S01234V puzzle in a newspaper

[Tim Hutton]

There is an interesting puzzle in today's Guardian:

Certain squares in an n x n array grid have become infected. The rules of transmission are simple. When two or more edges of a square become infected squares it also becomes infected. Show that for an n x n array of squares at least n squares must be infected for all to become so. The example shows a 4 x 4 array with 4 squares infected.
Chris Maslanka's puzzles, Guardian 14th Jan 2012

Their example is:

Code: Select all

o . . .
. o . .
. . . .
. o . o

or as an RLE:

Code: Select all

x = 4, y = 4, rule = B234/S01234V
o$bo2$bobo!

Which after 5 iterations has indeed filled a 4x4 square. (You will need Golly 2.3 or later for this, because it uses the von Neumann neighborhood - the 'V' at the end of the rule.)

[Tim Hutton]

Bonus question (from me, not the paper): What's the slowest way of filling an n x n array?

E.g. for 10x10 this is quite slow (25 steps) but we can do a lot better.

Code: Select all

x = 10, y = 10, rule = B234/S01234V
obo$4bo$o5bo$8bo$bo2$2bo2$3bo$9bo!

[knightlife]

Code: Select all

x = 10, y = 10, rule = B234/S01234V
bo3bo3bo$o2$bo2$o2$bo2$o2bo3bo!

This one takes 57 steps to fill.

[Wojowu]

Another one takes 57 steps

Code: Select all

x = 10, y = 10, rule = B234/S01234V
o8bo2$2bo4bo2$5bo$4bo2bo2$2bo6bo2$o!

Back into Guardian puzzle, as far as I can see n infected squares can infect at most n^2 squares. If we have 1 cell and we add another cell we can increase bounding box from 1x1 to 1x3 or 2x2. If we have m x n square and we add one cell outside the bounding box we can make rectangle m+1 x n, m+2 x n or m+1 x n+1. Adding one cell to both sides is optimal, so adding one cell to 1x1 square we can maximally have 2x2 square. Adding another cell will make 3x3 square etc. So n cells can maximally cover n x n square, so they can't cover any bigger square. I'm not sure that this proof is correct, but I won't think of anything more

[Tim Hutton]

58 steps:

Code: Select all

x = 10, y = 10, rule = B234/S01234V
o3bo3bo2$obo3bo$9bo2$o2$9bo2$o!

With the Guardian puzzle I'd got about as far as you Wojowu before giving up and looking at the answer. I can confirm that this puzzle has a simple and completely clear and easily explainable solution.

Edit:Here it is as rot13 text:

Jvgu rnpu vasrpgvba, gur gbgny crevzrgre bs gur vasrpgrq nern pna arire vapernfr, bayl fgnl gur fnzr be qrpernfr. Gur crevzrgre bs na a k a fdhner vf 4 k a, urapr gurer zhfg unir orra ng yrnfg a fdhnerf vavgvnyyl.

[knightlife]

65 steps:

Code: Select all

x = 10, y = 10, rule = B234/S01234V
3bo2bo2bo$o$bo2$o2$bo2$o$2bo2bo2bo!

[Macbi]

This problem was rediscovered on the discord, and Mateon1 found the following improvement to 66 generations (which is optimal):

Code: Select all

x = 10, y = 10, rule = B234/S01234V
o$9bo2$o$9bo2$o$2bobo3bo$2bo3bo$o8bo!