The Game of Life

I've mentioned the mathematician John Conway in three posts to this blog. The first was the Look and Say Sequence on February 10th 2017, the second was the RATS Sequence on September 26th 2020 and the third was the Free Fibonacci Sequences on July 18th 2021.

John Conway: 1937 - 2020
MacTutor Biography

I've known about his Game of Life for quite some time now but had avoided delving into it. However, yesterday I downloaded an iOS app that allows one to play around with it and this kindled an interest to find out more. Here is some information about the game together with its rules taken from Wikipedia:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies, as if by underpopulation.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

Figures 1, 2 and 3 show examples of commonly occurring patterns that occur during the game:

Figure 1: Loaf
Example of a still life

Figure 2: Blinker
Example of an Oscillator

Figure 3: Glider
Example of a Spaceship

The Pulsar is the most common period-3 oscillator as shown in Figure 4.

Figure 4: Pulsar
The most common
Period-3 oscillator

The Wikipedia comments go on to say:

The pulsar is the most common period-3 oscillator. The great majority of naturally occurring oscillators have a period of 2, like the blinker and the toad, but oscillators of all periods are known to exist, and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions. Patterns which evolve for long periods before stabilizing are called Methuselahs, the first-discovered of which was the R-pentomino. Diehard is a pattern that eventually disappears, rather than stabilizing, after 130 generations, which is conjectured to be maximal for starting patterns with seven or fewer cells. Acorn takes 5,206 generations to generate 633 cells, including 13 escaped gliders.

Figure 5: R-Pentomino
The first discovered Methuselah

Of course, I've encountered numerous references to the Game of Life in the OEIS over the years but have uniformly ignored them. OEIS A019473 is one example.

A019473

Number of stable \(n\)-celled patterns ("still lifes") in Conway's Game of Life, up to rotation and reflection.

The initial members of the sequence are: 0, 0, 0, 2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, 3286, 7773, 19044, 45759, 112243 (beginning with \(n\)=1).

Figure 1 shows the Loaf, one of the four 7-celled stable patterns. OEIS A089520 is another such sequence:

A089520

In Conway's Game of Life, the number of steps it takes for an \(n \times n\) square, in which all the cells are in the "on" state, to die out or start to cycle, or -1 if there is no cycle.

The initial members are:

1, 0, 5, 4, 11, 5, 5, 6, 16, 17, 32, 9, 18, 9, 22, 11, 33, 17, 20, 12, 26, 13, 48, 15, 46, 26, 295, 45, 154, 38, 62, 309, 38, 87, 78, 53, 96, 150, 641, 69, 82, 265, 216, 70, 70, 70, 120, 401, 107, 78, 70, 351, 318, 109, 297, 95, 122, -1, -1, 85, 232, 294, 127 (beginning with \(n\)=1).

The 1 x 1 square disappears in one step but the 2 x 2 square (called the Block) is stable and an example of a still life. The 3 x 3 square takes five steps to turn into four blinkers (one of which is shown in Figure 2). The 4 x 4 square takes four steps to disappear and so on. The OEIS comments for this sequence state that:

The -1 terms for \(n\) = 58, 59, 80, 92, 95, 96, 98, 99, 100 correspond to starting \(n \times n \) squares that produce 8 gliders (16 for \(n\) = 99) that go off to infinity, hence never reaching a cycle.

Here is a link to an interesting article in Quanta Magazine about the latest news regarding the Game of Life. Here is an excerpt:

Throughout the 1970s, mathematicians and hobbyists filled in the other short periods and found a smattering of longer ones. Eventually, mathematicians discovered a systematic way to build long-period oscillators. But oscillators with periods between 15 and 43 proved tough to find. “People have been trying to figure out the middle for years,” said Maia Karpovich, a graduate student at the University of Maryland. Filling in the gaps forced researchers to dream up a slew of new techniques that pushed the boundaries of what was thought possible with cellular automata, as mathematicians call evolving grids like Life.

Now Karpovich and six co-authors have announced in a December preprint that they have found the last two missing periods: 19 and 41. With those gaps filled, Life is now known to be “omniperiodic” — name a positive integer, and there exists a pattern that repeats itself after that many steps.

Pentominoes

Today I turned 25900 days old and one of the OEIS entries for this number states:

A248102

Number of tilings of a 5 X 2n rectangle using 2n pentominoes of shapes N, Y.

So 25900 is a member of this sequence, specifically for the case where n=8 and so, when there is a 5 x 16 rectangle (with area 80 square units), it can be tiled with 16 pentominoes (each with an area of 5 square units) in 25900 different ways. The pentominoes must be of type N or Y. Of course, I then had to look up what was meant by a pentomino of type N and type Y. Figure 1 shows the twelve types of free pentominoes, lettered according to the shapes that approximate those letters.

Figure 1: the 12 types of free pentominoes (source)

By free pentominoes, it is meant that chiral versions are not considered distinct. For example, the F pentomino can be lifted out of the plane and turned into its mirror image. If chiral versions are considered distinct, then there are 18 different types. See Figure 2.

Figure 2: The 12 pentominoes can form 18 different shapes,
with 6 of them (the chiral pentominoes) being mirrored. (source)

To quote from Wikipedia:

A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20. 

Figure 3 shows some of the possible configurations:

Figure 3

There are many websites where puzzles of this sort can be solved. Figure 4 is a screenshot of one of these sites. Link

Figure 4: link to website

In the screenshot in Figure 4, the 6 x 10 rectangle is to be tiled. There are 2339 ways in which this can be done. For the 5 x 12 case, there are 1010 ways. For the 4 x 15 case, there are 368 ways and for the 3 x 20 case there are just 2 ways. 

There's a lot more that could be said about pentominoes but I'll go on and make some comments about pentacubes which are polycubes made out of five cubes. There are 29 possible pentacubes of which twelve are flat (corresponding to the twelve pentominoes extruded to a depth of 1 unit). Figure 5 shows one of the non-flat pentacubes:

Figure 5: source 

To quote again from Wikipedia:

A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20.

Figure 6

The diagrams in Figure 6 do require a little scrutiny but the shapes of the various polycubes do reveal themselves. Obviously, the topics of pentominoes and pentacubes form a rich vein of recreational Mathematics and I'm just grazing the surface in this post. There are other puzzles that involve pentacubes. I'll mention one such puzzle and that is the Bedlam Cube, named after its inventor Bruce Bedlam. To quote from Wikipedia:

The puzzle consists of thirteen polycubic pieces: twelve pentacubes and one tetracube. The objective is to assemble these pieces into a 4 x 4 x 4 cube. There are 19,186 distinct ways of doing so, up to rotations and reflections. The Bedlam cube is one unit per side larger than the 3 x 3 x 3 Soma cube, and is much more difficult to solve. See Figures 7 and 8.

Figure 7: an assembled Bedlam Cube

Figure 8: a disassembled Bedlam Cube 

There are many more puzzles and much more to say about polyominoes and polycubes but I'll leave it at that for the moment. Meanwhile, I've not been idle. My trophy cabinet is shown in Figure 9 with my trophy for attaining Level 4 in Pentominoes.

Figure 9