

Title: "Erik's Puzzle" (Conway's Game of Life) Post by william wu on Mar 31^{st}, 2003, 10:37am In a strippeddown 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 ddimensional 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 31^{st}, 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 1^{st}, 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 2^{nd}, 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 email 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 2^{nd}, 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 2^{nd}, 2003, 4:24am There are other configuration that will work which also take the same number of cells to start with. for example [hide] [/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 2^{nd}, 2003, 4:40am Yes, i noticed that for the 3x3 case ... but from my envelope scratchwork it seems that such [hide]nondiagonal[/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 2^{nd}, 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 2^{nd}, 2003, 8:08am on 04/02/03 at 04:40:53, william wu wrote:
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 2^{nd}, 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 3^{rd}, 2003, 7:27pm Quote:


Title: Re: "Erik's Puzzle" (Conway's Game of Life)num Post by aero_guy on Apr 3^{rd}, 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 6^{th}, 2003, 7:31pm No, no, I mean that we start with the upperleft corner filled for odd numbers, like you proposed, but leave the upperleft 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 7^{th}, 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 7^{th}, 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 14^{th}, 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+u1, 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 ddimensional case, my guess is that N^{d1} live cells are needed. Certainly for d=1 this holds true (N^{0}=1) 

Title: Re: "Erik's Puzzle" (Conway's Game of Life) Post by rmsgrey on Apr 22^{nd}, 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 kdimensional 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 sideN 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 kdimensional 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 subcube. 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)=N^{k1} 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 4cell tetrahedron) For the record, 9cell solutions to the (3,3) case I've found include: {((x)(x)(x))((x)(x)(x))((x)(x)(x))} {((xx)(x)(x))(()(x)(x))((x)()(xx))} (hopefully my notation is selfexplanatory) 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 22^{nd}, 2003, 12:28pm rmsgrey, Here is a solution for k=3 dimensions which gives exactly N^{2} 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 N^{2} 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 23^{rd}, 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 25^{th}, 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 19^{th}, 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 N^{2}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 20^{th}, 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 20^{th}, 2004, 5:50pm Here is an elegant proof of the 2D case by Peter Winkler. For the live cells, consider the outerperimeter. 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 atleast N live cells initially. I guess this can be adapted to the 3D case to look at surface area to prove that the surface area of the live cells is invariant. In which case, we have 6N^{2} area at the end which means that we must have at least N^{2} live cells initially. 

Title: Re: "Erik's Puzzle" (Conway's Game of Life) Post by rmsgrey on Jul 21^{st}, 2004, 6:45am Actually, that seems to solve it for the ddimensional case  or at least creates a lower bound of N^{d1} live cells in the initial pattern. A minor quibble  rather than the surface being invariant, it is nonincreasing  for instance a 2D checkerboard pattern will drop in area quite drastically in the next generation. This doesn't invalidate the proof of N^{d1} 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 21^{st}, 2004, 10:02am on 07/21/04 at 06:45:51, rmsgrey wrote:
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 2D case does not make the whole grid alive. You are right that the perimeter in nonincreasing, I probably botched up the original proof of Winkler. 

Title: Re: "Erik's Puzzle" (Conway's Game of Life) Post by Aryabhatta on Jul 21^{st}, 2004, 11:11am on 07/21/04 at 10:02:13, Aryabhatta wrote:
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 23^{rd}, 2004, 3:32am Consider a hypercube grid with coordinates x[subi] = {1, 2, .. , N}. (i = 1, 2, ... d) Start with all N^(d1) 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 23^{rd}, 2004, 4:07am That doesn't quite work. For instance, in the 1D case, 0^{th} generation has cell (N) live, 1^{st} generation has cells (N1) 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 k^{th} 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 23^{rd}, 2004, 4:13am on 07/21/04 at 11:11:52, Aryabhatta wrote:
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 livenonlive 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 23^{rd}, 2004, 4:42am on 07/23/04 at 04:07:54, rmsgrey wrote:
You're right. The growth works as indicated for grids with periodic boundary conditions. To start with N^(d1) 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 (N1)^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 19^{th}, 2005, 2:53pm on 03/31/03 at 10:37:58, william wu wrote:
This 'strippeddown 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 19^{th}, 2005, 3:40pm on 01/19/05 at 14:53:31, JocK wrote:
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/cgibin/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 20^{th}, 2005, 8:20am on 01/19/05 at 14:53:31, JocK wrote:
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. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 