B234/S01234V puzzle in a newspaper

For discussion of other cellular automata.
Post Reply
User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

B234/S01234V puzzle in a newspaper

Post by Tim Hutton » January 14th, 2012, 7:10 pm

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.)
Last edited by Tim Hutton on April 5th, 2013, 5:45 am, edited 1 time in total.

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: B234/S01234V puzzle in a newspaper

Post by Tim Hutton » January 14th, 2012, 8:08 pm

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
Posts: 566
Joined: May 31st, 2009, 12:08 am

Re: B234/S01234V puzzle in a newspaper

Post by knightlife » January 14th, 2012, 8:30 pm

Code: Select all

x = 10, y = 10, rule = B234/S01234V
bo3bo3bo$o2$bo2$o2$bo2$o2bo3bo!
This one takes 57 steps to fill.

User avatar
Wojowu
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: B234/S01234V puzzle in a newspaper

Post by Wojowu » January 15th, 2012, 5:33 am

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
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: B234/S01234V puzzle in a newspaper

Post by Tim Hutton » January 15th, 2012, 3:48 pm

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.
Last edited by Tim Hutton on January 16th, 2012, 10:24 am, edited 1 time in total.

knightlife
Posts: 566
Joined: May 31st, 2009, 12:08 am

Re: B234/S01234V puzzle in a newspaper

Post by knightlife » January 15th, 2012, 11:50 pm

65 steps:

Code: Select all

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

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: B234/S01234V puzzle in a newspaper

Post by Macbi » June 24th, 2020, 3:24 am

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!

Post Reply