Author 
Topic: "Erik's Puzzle" (Conway's Game of Life) (Read 4983 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


"Erik's Puzzle" (Conway's Game of Life)
« on: Mar 31^{st}, 2003, 10:37am » 
Quote Modify

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.

« Last Edit: Mar 31^{st}, 2003, 10:38am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #1 on: Mar 31^{st}, 2003, 1:48pm » 
Quote Modify

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.

« Last Edit: Mar 31^{st}, 2003, 1:50pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #2 on: Apr 1^{st}, 2003, 1:56pm » 
Quote Modify

William, I think I could prove it was ceil((N+1)/2).


IP Logged 
Doc, I'm addicted to advice! What should I do?



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #3 on: Apr 2^{nd}, 2003, 2:26am » 
Quote Modify

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 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.

« Last Edit: Apr 2^{nd}, 2003, 3:11am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #4 on: Apr 2^{nd}, 2003, 3:53am » 
Quote Modify

david mackay says only n, s, e, and w. he also says there is a neat way to prove it. interesting hint: lyapunov function


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #5 on: Apr 2^{nd}, 2003, 4:24am » 
Quote Modify

There are other configuration that will work which also take the same number of cells to start with. for example 0_0 0__ ___ __0 _0_ or _0_ 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.

« Last Edit: Apr 2^{nd}, 2003, 4:26am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #6 on: Apr 2^{nd}, 2003, 4:40am » 
Quote Modify

Yes, i noticed that for the 3x3 case ... but from my envelope scratchwork it seems that such nondiagonal 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 diagonal.) I think you'd have to put these subsquare structures in too many places.

« Last Edit: Apr 2^{nd}, 2003, 4:42am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



aero_guy
Senior Riddler
Gender:
Posts: 513


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #7 on: Apr 2^{nd}, 2003, 4:57am » 
Quote Modify

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.

« Last Edit: Apr 2^{nd}, 2003, 4:58am by aero_guy » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #8 on: Apr 2^{nd}, 2003, 8:08am » 
Quote Modify

on Apr 2^{nd}, 2003, 4:40am, 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 diagonal 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..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #9 on: Apr 2^{nd}, 2003, 8:12am » 
Quote Modify

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

« Last Edit: Apr 2^{nd}, 2003, 10:53am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Chronos
Full Member
Gender:
Posts: 288


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #10 on: Apr 3^{rd}, 2003, 7:27pm » 
Quote Modify

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 upperleft 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.


IP Logged 



aero_guy
Senior Riddler
Gender:
Posts: 513


Re: "Erik's Puzzle" (Conway's Game of Life)num
« Reply #11 on: Apr 3^{rd}, 2003, 10:29pm » 
Quote Modify

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.


IP Logged 



Chronos
Full Member
Gender:
Posts: 288


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #12 on: Apr 6^{th}, 2003, 7:31pm » 
Quote Modify

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.


IP Logged 



aero_guy
Senior Riddler
Gender:
Posts: 513


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #13 on: Apr 7^{th}, 2003, 12:34am » 
Quote Modify

ahhhhhh, we still haven't approached half of the OP, what about 3+ dim?


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #14 on: Apr 7^{th}, 2003, 5:52pm » 
Quote Modify

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?


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



rmsgrey
Guest


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #15 on: Apr 14^{th}, 2003, 8:17am » 
Quote Modify
Remove

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)


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #16 on: Apr 22^{nd}, 2003, 9:01am » 
Quote Modify

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.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #17 on: Apr 22^{nd}, 2003, 12:28pm » 
Quote Modify

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


IP Logged 
Doc, I'm addicted to advice! What should I do?



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #18 on: Apr 23^{rd}, 2003, 12:45pm » 
Quote Modify

In fact, any cyclic permutation of that solution works... still lacking an optimality proof though...


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #19 on: Apr 25^{th}, 2003, 1:34pm » 
Quote Modify

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.

« Last Edit: Apr 25^{th}, 2003, 1:34pm by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #20 on: Aug 19^{th}, 2003, 7:56am » 
Quote Modify

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...


IP Logged 



Bitrot
Newbie
Posts: 5


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #21 on: Jul 20^{th}, 2004, 3:56pm » 
Quote Modify

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?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #22 on: Jul 20^{th}, 2004, 5:50pm » 
Quote Modify

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.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #23 on: Jul 21^{st}, 2004, 6:45am » 
Quote Modify

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.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #24 on: Jul 21^{st}, 2004, 10:02am » 
Quote Modify

on Jul 21^{st}, 2004, 6:45am, rmsgrey wrote: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. 
 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.


IP Logged 



