Author |
Topic: "Erik's Puzzle" (Conway's Game of Life) (Read 5670 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
"Erik's Puzzle" (Conway's Game of Life)
« on: Mar 31st, 2003, 10:37am » |
 Quote  Modify
|
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.
|
| « Last Edit: Mar 31st, 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 31st, 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 31st, 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 1st, 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 2nd, 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 e-mail 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 2nd, 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 2nd, 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: 13730
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #5 on: Apr 2nd, 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 2nd, 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 2nd, 2003, 4:40am » |
Quote Modify
|
Yes, i noticed that for the 3x3 case ... but from my envelope scratchwork it seems that such non-diagonal 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 2nd, 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 2nd, 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 2nd, 2003, 4:58am by aero_guy » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #8 on: Apr 2nd, 2003, 8:08am » |
Quote Modify
|
on Apr 2nd, 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: 13730
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #9 on: Apr 2nd, 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 2nd, 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 3rd, 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 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.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)num
« Reply #11 on: Apr 3rd, 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 6th, 2003, 7:31pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #13 on: Apr 7th, 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 7th, 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 14th, 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+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)
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #16 on: Apr 22nd, 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 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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #17 on: Apr 22nd, 2003, 12:28pm » |
Quote Modify
|
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-
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #18 on: Apr 23rd, 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 25th, 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 25th, 2003, 1:34pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #20 on: Aug 19th, 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 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...
|
|
IP Logged |
|
|
|
Bitrot
Newbie
Posts: 5
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #21 on: Jul 20th, 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 20th, 2004, 5:50pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #23 on: Jul 21st, 2004, 6:45am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #24 on: Jul 21st, 2004, 10:02am » |
Quote Modify
|
on Jul 21st, 2004, 6:45am, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print