wu :: forums « wu :: forums - "Erik's Puzzle" (Conway's Game of Life) » Welcome, Guest. Please Login or Register. Jan 24th, 2022, 11:20am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, Icarus, ThudnBlunder, SMQ, towr, Grimbal, william wu)    "Erik's Puzzle" (Conway's Game of Life) « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: "Erik's Puzzle" (Conway's Game of Life)  (Read 5397 times)
Aryabhatta
Uberpuzzler

Gender:
Posts: 1321
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #25 on: Jul 21st, 2004, 11:11am » Quote Modify

on Jul 21st, 2004, 10:02am, 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.
 IP Logged
JocK
Uberpuzzler

Gender:
Posts: 877
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #26 on: Jul 23rd, 2004, 3:32am » Quote Modify

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.

JCK
 IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #27 on: Jul 23rd, 2004, 4:07am » Quote Modify

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]
 « Last Edit: Jul 23rd, 2004, 4:08am by rmsgrey » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #28 on: Jul 23rd, 2004, 4:13am » Quote Modify

on Jul 21st, 2004, 11:11am, 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...
 IP Logged
JocK
Uberpuzzler

Gender:
Posts: 877
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #29 on: Jul 23rd, 2004, 4:42am » Quote Modify

on Jul 23rd, 2004, 4:07am, 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.

JCK
 IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
JocK
Uberpuzzler

Gender:
Posts: 877
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #30 on: Jan 19th, 2005, 2:53pm » Quote Modify

on Mar 31st, 2003, 10:37am, 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?
 IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
Aryabhatta
Uberpuzzler

Gender:
Posts: 1321
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #31 on: Jan 19th, 2005, 3:40pm » Quote Modify

on Jan 19th, 2005, 2:53pm, 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 started by EigenRay in the medium forum.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: "Erik's Puzzle" (Conway's Game of Life)   « Reply #32 on: Jan 20th, 2005, 8:20am » Quote Modify

on Jan 19th, 2005, 2:53pm, 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.
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »