```

wu :: forums
(http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)

riddles >> hard >> "Erik's Puzzle" (Conway's Game of Life)
(Message started by: william wu on Mar 31st, 2003, 10:37am)

```

Title: "Erik's Puzzle" (Conway's Game of Life)
Post by william wu on Mar 31st, 2003, 10:37am
In a stripped-down version of Conway's game of life, cells are arranged on a square grid. Each cell is either alive or dead. Live cells do not die. Dead cells become alive if two or more of their immediate neighbours are alive. (Neighbours to north, south, east and west.) What is the smallest number of live cells needed in order that these rules lead to an entire N X N square being alive?

In a d-dimensional version of the same game, the rule is that if d neighbours are alive then you come to life. What is the smallest number of live cells needed in order that an entire N X N X ... X N hypercube becomes alive? (And how should those live cells be arranged?)

Author: I presume some guy named Erik. From David MacKay's book: Information Theory, Inference, and Learning Algorithms.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by william wu on Mar 31st, 2003, 1:48pm
I have a simple answer for this on the order of N -- most of you guys will probably come up with the same answer -- but I don't know how to formally prove it's optimal.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by James Fingas on Apr 1st, 2003, 1:56pm
William,

I think I could prove it was [hide]ceil((N+1)/2).[/hide]

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by william wu on Apr 2nd, 2003, 2:26am
You can't fill up a 3 x 3 grid with only 2 initial alive cells ... but you could if the neighbors could also be to the northeast, northwest, southeast, southwest. I'm not sure what's the right way to interpret "immediate neighbors" ... the problem phrasing is taken verbatim from the text. I'll e-mail the author. I guess in either case it's not that hard ... for the square case, my idea is to [hide]put all initial alive cells along the diagonal. As far as proving that this is the best you can do, I have some informal ideas: 1. alive cells cannot be generated outside of the rectangular "convex hull" of the initial alive cells; 2. then prove by induction that initial alive cells along the diagonal of the square will result in the whole square coming alive. [/hide]

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by william wu on Apr 2nd, 2003, 3:53am
david mackay says only n, s, e, and w. he also says there is a neat way to prove it. interesting hint: [hide]lyapunov function[/hide]

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by towr on Apr 2nd, 2003, 4:24am
There are other configuration that will work which also take the same number of cells to start with.
for example
[hide]
`|0|_|0|      |0|_|_||_|_|_|      |_|_|0||_|0|_|  or  |_|0|_|`
[/hide]
you may think, 'yeah, but that's only for the 3x3 case', but once it is grown full it can be used as subsquare for a larger square.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by william wu on Apr 2nd, 2003, 4:40am
Yes, i noticed that for the 3x3 case ... but from my envelope scratchwork it seems that such [hide]non-diagonal[/hide] solutions don't scale well when n gets larger. for instance, when n is 10 can you use these more scattered structures and fill the whole plane with only 10 initial alive cells? (10 is the length of the [hide]diagonal[/hide].) I think you'd have to put these subsquare structures in too many places.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by aero_guy on Apr 2nd, 2003, 4:57am
You could place the substructures diagonal to each other with one other cell in the corner.  Think of each 3x3 substructure as a single cell.  Place these extended cells along the diagonal of the larger grid.

Also, a nifty way that expands nicely is:

x_x_x_x_x_x
_
x
_
x
_
x
_
x
_
x

This expands for all square grids with an odd number of cells per side.  For an even one, throw an x in the lower right corner too.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by towr on Apr 2nd, 2003, 8:08am

on 04/02/03 at 04:40:53, william wu wrote:
 I think you'd have to put these subsquare structures in too many places.
Actually you can just put them on the [hide]diagonal[/hide] Once they filled out their square the rest comes naturally..
You can also rotate them and mirror them. So the number of ways to get a live square increases dramatically as N increases..

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by towr on Apr 2nd, 2003, 8:12am
Perhaps an interesting puzzle to see what kind of series you get for the number of ways you can distribute the minimum amount of cells for a certain NxN and still have it work..
N
1 - 1
2 - 2
3 - 14
4 - 130
5 - 1615
6 - 23140

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Chronos on Apr 3rd, 2003, 7:27pm

Quote:
 This expands for all square grids with an odd number of cells per side.  For an even one, throw an x in the lower right corner too.
I can do one better than that:  Start the alternation with the upper-left corner empty, and proceed according to your pattern.  First iteration will still give you both those edges, but now extending all the way to the right and bottom.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)num
Post by aero_guy on Apr 3rd, 2003, 10:29pm
Obviously my earlier answer is not as simple as just running the diagonal, but I proposed it as an intersting and easily scalable anwer,  Chronos, your answer is the same as mine.  For yours, we need to but an x in the lower right corner when there is an odd number of cells per side.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Chronos on Apr 6th, 2003, 7:31pm
No, no, I mean that we start with the upper-left corner filled for odd numbers, like you proposed, but leave the upper-left corner empty for even numbers.  The solutions are still qualitatively the same, but this way, we never need that extra corner piece, and we always have the same efficiency as the "fill the diagonal" method.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by aero_guy on Apr 7th, 2003, 12:34am
ahhhhhh, we still haven't approached half of the OP, what about 3+ dim?

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Icarus on Apr 7th, 2003, 5:52pm
No one has proved that N living cells is optimal for an NxN square yet either. If you have fewer than N cells, then you must have at least one row and one column devoid of living cells at the start. These will divide the square into 4 smaller rectangles (if the row or column is on the edge of the square, then it is easy to see that they will never come alive). Each of the rectangles must be seeded with living cells to come to life. This would seem to require duplicates in some rows and columns, thus needing more than N cells, but it is possible for two rectangles to help each other fill in areas neither could do by themselves, so I have not been able to definitely show that N cells are required.

Does anyone have thoughts on this?

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Apr 14th, 2003, 8:17am
First some definitions: define a pattern as a set of live cells; the final state of a pattern as the set of live cells after an infinite number of generations; a stable pattern as a pattern which is its own final state; an empty row as a row (or column) with no live cells; an intersection as the intersection of two empty rows; an enclosing rectangle of a given set of cells as their smallest rectangular superset; division of the grid into reduced rectangles (for a given pattern) as a recursive process whereby a rectangle (intitially the entire grid) is divided into two smaller rectangles, one to each side of an empty row (which lies in neither) so long as any rectangle contains an empty row; and reduced rectangles as the end products of the process of division into reduced rectangles.

Any cells adjacent to a reduced rectangle must therefore be empty (by construction). Also an X*Y reduced rectangle contains at least max(X*Y) live cells (otherwise it would have an empty row and have been divided).

Next a handy lemma: any cells brought to life in the next generation of a subset of a pattern will also be alive in the next generation of the full pattern.
The proof is obvious - adding more cells to a pattern can never cause a cell that would be alive in the next generation not to be.

As a corollary, replacing any pattern with the union of its reduced rectangles will never remove any cells from the final state of the pattern (though it may add some).

Consider a pair of reduced rectangles which share an orthogonally adjacent empty cell. If both reduced rectangles are filled, then the shared empty cell will also be filled, as will their enclosing rectangle. Define a merged rectangle recursively as: 1) any reduced rectangle; 2) the enclosing rectangle of any pair of merged rectangles such that moving two squares orthogonally (or one diagonally) moves from one to the other.

Any pattern replaced with the union of its reduced rectangles will have a final state precisely the union of its merged rectangles. Obviously any cell within a merged rectangle will be live by construction. Any cell not within a merged rectangle must 1) not be within a reduced rectangle and 2) have at most one orthogonal neighbour that lies within a merged rectangle (if it had two, then they would generate a merged rectangle containing it). Since at any time when no such cell is live the next generation must leave it empty, the result follows.

Therefore any pattern whose final state is the entire grid must have the entire grid as one of its merged rectangles.

The number of live cells in the intersection of the initial pattern with a merged rectangle of size X*Y can be found by induction to be at least (X+Y)/2 as follows: each merged rectangle (size X*Y) is either a reduced rectangle, in which case it contains at least max(X,Y) live cells so certainly at least (X+Y)/2; or it is formed from two smaller merged rectangles of size x*y and u*v and contains at least (x+y+u+v)/2 live cells (by induction hypothesis). There are two cases to consider: the pair of merged rectangles are diagonally adjacent, in which case X=x+u, Y=y+v, (X+Y)/2=(x+y+u+v)/2 or the pair of merged rectangles overlap in one direction and are up to one square apart in the other. For the sake of argument, say they overlap in the X,x,u direction, then X<=x+u-1, Y=y+v+1 so (X+Y)/2<=(x+y+u+v)/2. Hence, by induction, a merged rectangle of size X*Y contains at least (X+Y)/2 live cells in the intial pattern.

Since the entire grid must be a merged rectangle, and has size N*N, it must contain at least (N+N)/2=N live cells in the initial pattern. QED

As to the d-dimensional case, my guess is that Nd-1 live cells are needed. Certainly for d=1 this holds true (N0=1)

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Apr 22nd, 2003, 9:01am
For convenience, define f(N,k) as the minimum nuber of live cells required intially for the final state to be a filled k-dimensional hypercube of side length N.

Looking further at 3D: f(2,3)=4 (in alternate cells - easy enough to prove optimality). f(1,3)=1 trivially. f(3,3)<=9 and I haven't managed to come up with any 8 cell arrangements by hand.

I can prove that, for any N, any arrangement that populates the entire cube must have an initial live cell on each edge (if an entire edge starts empty then each cell in it has at most two live neighbours...) and each face of the cube must have at least N cells in an arrangement that would populate a side-N square in the 2D case (each cell in the face has one neighbour not in the face reducing the face to the 2D case at best - a superset of a 2D solution may be required). Both results are examples of a more general rule for the k-dimensional case which I haven't worked out the details of.

f(N,k) may be multiplicative in N - f(n*m,k)<=f(n,k)*f(m,k) since you can treat the side m*n cube as a side m cube with each cell treated as a side n sub-cube. I have no idea whether it is multiplicative (or how to show it if it is) but it would fit my hypothesis that f(N,k)=Nk-1

One of my immediate problems with the k=3 case is that patterns other than cuboids can be stable - unlike the 2D case where every stable pattern is either a rectangle or multiple rectangles at safe distances, and I'm having difficulty visualising the other stable shapes (apart from the simple 4-cell tetrahedron)

For the record, 9-cell solutions to the (3,3) case I've found include:
{((x--)(--x)(-x-))((--x)(-x-)(x--))((-x-)(x--)(--x))}
{((x-x)(-x-)(x--))((---)(--x)(-x-))((--x)(---)(x-x))}
(hopefully my notation is self-explanatory)
and upper bounds for f(N,3):
1  1*
2  4*
3  9
4  16
5  27**
6  36
7  52**
8  64
9  81

*known to be exact value
**almost certainly too high, but since I've been working mostly in my head, I haven't been able to produce reliable results better than this.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by James Fingas on Apr 22nd, 2003, 12:28pm
rmsgrey,

Here is a solution for k=3 dimensions which gives exactly N2 performance:

On the top of the cube, fill in N elements along the diagonal. On the next level down, fill in a shorter diagonal and one element in the corner. On the next level down, fill in a still shorter diagonal and two elements in the corner. Fill in all the levels like this. You'll end up with elements on two planes within the cube. These N2 elements will populate the entire cube. For example, with N=7 (one level at a time shown):

x------
-x-----
--x----
---x---
----x--
-----x-
------x

-x-----
--x----
---x---
----x--
-----x-
------x
x------

--x----
---x---
----x--
-----x-
------x
x------
-x-----

.
.
.

------x
x------
-x-----
--x----
---x---
----x--
-----x-

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Apr 23rd, 2003, 12:45pm
In fact, any cyclic permutation of that solution works... still lacking an optimality proof though...

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by James Fingas on Apr 25th, 2003, 1:34pm
It seems to work for more than 3 dimensions too. I just tried it with N=4, k=4, and N=5, k=4, and it worked.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Aug 19th, 2003, 7:56am
I've been trying to get somewhere on a proof (for 3D), and keep running into problems with trying to track 27 distinct volumes - my most promising approach so far involves considering the locations of holes in plane projections of cubes with N2-1 live cells. I've managed to prove that there must be at least one hole through a cube that intersects with another hole parallel to a different axis, but there are arrangements that don't involve holes parallel to all three axes intersecting at the same cell. Also, since I have difficulty tracking the 26 regions around a given cell (created by slicing the cube along the planes containing the cell faces) I haven't managed to establish a minimum number of live regions needed to fill the cube.

If someone could establish that 9 cells is optimal for a 3*3*3 cube and provide an exhaustive listing, I suspect that would be enough to start working inductively...

Higher dimensions I really can't visualise well enough to work on properly...

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Bitrot on Jul 20th, 2004, 3:56pm
On a side note, I remember reading once that from a random starting position, the probability of starting 'alive' must be at least pi/6 to fill the board more than half the time. But I can't find what this variant of Life called, or this surprising result, so I might be remembering it totally wrong. Help?

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Aryabhatta on Jul 20th, 2004, 5:50pm
Here is an elegant proof of the 2-D case by Peter Winkler.

For the live cells, consider the outer-perimeter. Even after a new cell comes alive, the outer permiter remains the same.

For all the cells to be live the outer perimeter must be 4N which is possible only if there are at-least N live cells initially.

I guess this can be adapted to the 3-D case to look at surface area to prove that the surface area of the live cells is invariant. In which case, we have 6N2 area at the end which means that we must have at least N2 live cells initially.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Jul 21st, 2004, 6:45am
Actually, that seems to solve it for the d-dimensional case - or at least creates a lower bound of Nd-1 live cells in the initial pattern.

A minor quibble - rather than the surface being invariant, it is non-increasing - for instance a 2D checkerboard pattern will drop in area quite drastically in the next generation. This doesn't invalidate the proof of Nd-1 as a lower bound, but does mean there's still a little work to do to prove it sufficient.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Aryabhatta on Jul 21st, 2004, 10:02am

on 07/21/04 at 06:45:51, rmsgrey wrote:
 Actually, that seems to solve it for the d-dimensional case - or at least creates a lower bound of Nd-1 live cells in the initial pattern.A minor quibble - rather than the surface being invariant, it is non-increasing - for instance a 2D checkerboard pattern will drop in area quite drastically in the next generation. This doesn't invalidate the proof of Nd-1 as a lower bound, but does mean there's still a little work to do to prove it sufficient.

Even if we could prove it invariant, we would still have to do the same work to prove it is sufficient.  For instance, a whole row of N live cells in 2-D case does not make the whole grid alive.

You are right that the perimeter in non-increasing, I probably botched up the original proof of Winkler.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Aryabhatta on Jul 21st, 2004, 11:11am

on 07/21/04 at 10:02:13, Aryabhatta wrote:
 For instance, a whole row of N live cells in 2-D case does not make the whole grid alive.

Sorry. Bad example, but you get what I am trying to say.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by JocK on Jul 23rd, 2004, 3:32am
Consider a hypercube grid with coordinates x[subi] = {1, 2, .. , N}. (i = 1, 2, ... d)

Start with all N^(d-1) cells that satisfy x[sub1] + x[sub2] + ... = 0 mod N as live cells.

In the next step all cells that satisfy x[sub1] + x[sub2] + .. =  [pm]1 mod N become alive. Etc.

J8)CK

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Jul 23rd, 2004, 4:07am
That doesn't quite work. For instance, in the 1-D case, 0th generation has cell (N) live, 1st generation has cells (N-1) and (N) live, but not cell (1)...

A similar problem with the proof occurs with higher dimensions - while most cells worth +/-k mod N come to life in the kth generation, a number - in the first generation those on the boundaries - do not. At least as far as 3D, these cells do get picked up eventually, but it's not immediately obvious, and they definitely do not come to life at the time suggested by the proof offered. I suspect the pattern given is the right one, but it still needs a little work to prove it.

[e]formatting[/e]

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Jul 23rd, 2004, 4:13am

on 07/21/04 at 11:11:52, Aryabhatta wrote:
 Sorry. Bad example, but you get what I am trying to say.

A 2*N checkerboard strip is enough for the N*N grid - it has N live cells, no two of which share a side, so has a live-nonlive boundary of 4N, yet will never grow beyond the 2*N strip...

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by JocK on Jul 23rd, 2004, 4:42am

on 07/23/04 at 04:07:54, rmsgrey wrote:
 I suspect the pattern given is the right one, but it still needs a little work to prove it.

You're right. The growth works as indicated for grids with periodic boundary conditions.

To start with N^(d-1) live cells that satisfy X1 + X2 + .. + Xd = 0 mod N (Xi = 1, 2, .. N) also does the job for 'dead' boundaries, but the growth towards a full live lattice is slower: first a (N-1)^d hypercube is filled with live cells, and subsequently the last layers in all d directions become live.

J8)CK

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by JocK on Jan 19th, 2005, 2:53pm

on 03/31/03 at 10:37:58, william wu wrote:
 In a stripped-down version of Conway's game of life, cells are arranged on a square grid. Each cell is either alive or dead. Live cells do not die. Dead cells become alive if two or more of their immediate neighbours are alive.

This 'stripped-down version of the game of life' appears to be known known as 'bootstrap percolation':

http://mathworld.wolfram.com/BootstrapPercolation.html

The question "what random density of life cells do you need to start with so as to reach an 'all cells life' situation?" has an interesting answer (that apparently could not be deducted from computer simulations).

B.t.w.: do we consider 'Erik's puzzle' solved (in all spatial dimensions)? It is on the list of unsolved problems, but for the periodic boundary conditions commonly used in Cellular Automata research (see e.g. the animation shown on the above Mathworld page) the answer is straightforward, isn't it?

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by Aryabhatta on Jan 19th, 2005, 3:40pm

on 01/19/05 at 14:53:31, JocK wrote:
 The question "what random density of life cells do you need to start with so as to reach an 'all cells life' situation?" has an interesting answer (that apparently could not be deducted from computer simulations).

This might not be what you are talking about, but there is a thread already: Erik's Puzzle Probability (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1090881961) started by EigenRay in the medium forum.

Title: Re: "Erik's Puzzle" (Conway's Game of Life)
Post by rmsgrey on Jan 20th, 2005, 8:20am

on 01/19/05 at 14:53:31, JocK wrote:
 B.t.w.: do we consider 'Erik's puzzle' solved (in all spatial dimensions)? It is on the list of unsolved problems, but for the periodic boundary conditions commonly used in Cellular Automata research (see e.g. the animation shown on the above Mathworld page) the answer is straightforward, isn't it?

The problem we're most interested in (and the unsolved one) is the less trivial case where the boundaries never contribute live cells - for dimensions higher than 1, this is equivalent to embedding the working hypercube in a larger, otherwise empty, hypervolume.