Problems
Welcome back everybody! We hope you had a good break, today we will be exploring a fascinating topic called Conway’s Game of Life, a mathematical game invented by mathematician John Conway in 1970 that shows how simple rules can create surprisingly complex patterns. The game is played on a large grid where every square represents a cell, that can be dead or alive. The game evolves in “turns", which we call generations, or just time, and the rules are as follows:
Birth: if a cell is dead at time \(t\), it will become alive at time \(t+1\) exactly when \(3\) of its \(8\) neighbours are alive (we count diagonal neighbours too, hence \(8\)).
Death: a live cell can die from two ways:
Overcrowding: if an alive cell has \(4\) or more alive neighbours, it will die of overcrowding.
Loneliness: if an alive cell has \(1\) or \(0\) alive neighbours, it will die of loneliness.
Survival: a cell that is alive will remain alive exactly when it has \(2\) or \(3\) alive neighbours.
This game is far too complex to understand all of it in only one session, but if you want to learn more, you should read the Wikipedia article or the freely available online book Conway’s Game of Life, Mathematics and Construction by Johnston and Greene. Many simulators are available online to play the game too.
Show that the following pattern eventually dies completely:
A still life is a non-empty pattern (it starts with at least one alive cell) that never changes. Show that a pattern consisting of a \(2\times 2\) square of alive cells is a still life.
An oscillator is a pattern that returns to its original state after some number of evolutions. Its period is the number of evolutions it needs to return to its initial state. Show that a \(3\times 1\) piece of alive cells is an oscillator, and finds it period.
What is the smallest number of alive cells that a pattern needs to start with in order for the pattern to never die off?
A connected still life is a still life where you can get from any alive cell to any other alive cell by moving through neighbouring alive cells (remember that cells may touch at corners and still count as connected), Find a connected still life of exactly \(10\) alive cells.
Show that for any given even number greater than or equal to \(4\), there is a connected still life with that number of alive cells.
Prove that \(6\) is the maximum possible number of living neighbours a dead cell can have in a still life, and show that this maximum can actually occur.
A spaceship is a pattern that, after a fixed number of generations, looks exactly the same as before, but in a different place. For example, the glider is the pattern shown below: it looks the same every \(4\) generations, and each time it has moved one square diagonally. It turns out this is a speed limit in the game! Show that no pattern can move \(2\) or more squares diagonally after \(4\) generations.
