### Géza Kós

# Dogs from Planet Mars

(Published in KöMal, 1996/3, pp. 138-144.)

The game to be introduced here was invented by Eward Fradkin. First of all we describe the rules of the game.

Imagine that the world is an infinitely large squared sheet of paper and there are cells living in certain squares. One square can contain one cell at most at a time. We represent the position of the cells by colouring all squares which contain a cell.

Every minute all cells are divided into four descendants who will live in the adjoining four squares (the original cell disappears). If a square happens to contain more than one cell after the division of cells then those cells destroy each other in pairs, and finally 1 or 0 of them will remain in the square. This means that in a fixed generation a square will contain a cell if and only if 1 or 3 of the adjoining squares contained a cell in the previous generation.

*Figure 1*

*Figure 1* represents the first few generations if we start
with one cell.

There is a slightly different way of deriving these positions. Suppose that any number of cells can live in a square; they do not destroy each other. We colour each square that contains an odd number of cells. It is easy to see that in this way we will arrive at the same positions as before.

This reformulation is very useful. If the starting position
consists of more than one cell and we want to see the situation after
*n* generations then we can first calculate the number of
descendants for each starting cell and then we can add up the numbers
in each square.

What happens with the formations when we add up the numbers? Those
squares will be coloured which are coloured for *n* odd number of
starting cells. We can call this the addition of formations. *
Figure 2* illustrates this addition for two starting cells.

*Figure 2*

Another important property of the game is that after
2^{n} generations one starting cell will always have
four descendants. These lie at the distance of 2^{n}
squares from the position of the starting cell, one to the left, one
to the right, one upwards, and one downwards. This can be proved by
induction. When *n*=0, 2^{n}=1 and after 1
generation we do have the required formation by the rule set for the
division of cells. Suppose we have the required formation of four
cells after 2^{n} generations. Now, after another
2^{n} generations these four cells will produce 16
descendants altogether, and it is easy to see that 12 of these will
destroy each other and the remaining 4 will give the required
formation.

*Figure 3*

Let us form a small `picture', e.g. a dog, out of a few cells.
After 2^{n} generations each cell of the dog will have
four descendants as we described above. These descendants will form
four different dogs. If *n* is small these dogs can interfere
with each other and the picture can easily be unrecognisable. However,
if *n* is large enough, then the four dogs do not interfere, they
stand aparr. If *n* is not a power of 2 but is divisible by a
`large enough' power of two (e.g. 12 is divisible by 4) then after
*n* generations we will have more than four dogs in the
picture. (See *Figure 3*.)

### Computer Program I

The simulation of the game on computer raises an interesting problem. The computer cannot simulate an infinitely large sheet of paper, it can only work in a finite rectangle. This means that the cells along the sides of the rectangle will only have three descendants and those at the corners will only have two.

What will the effects of this slight change be?

This applet below illustrates the game in a rectangle of size 25x39.

Examining the generations, we see an interesting phenomenon. Besides the dogs we are used to seeing, their mirror images come into the picture, too: dogs standing upside down or looking left instead of right. It looks as if they had been reflected back from the sides of the rectangle.

The reason for this phenomenon lies in the slight alteration in the rule of division of cells at the sides of the rectangle. They divide into fewer descendants and the descendants of the missing descendants will be missing too. It is very difficult, however, to trace down the effects of missing descendants generation by generation. We need a more general method of determining what will happen.

### The Principle of Reflection

In order to understand what actually happens at the sides of the rectangle, let us first consider a slightly simpler case. Imagine that the world now is only half of the plane bordered by a vertical line. As we have seen, if we change the rules of division of cells along the border-line we will not be able to trace down the consequences. Therefore, we will pretend, instead, that the world is still the whole plane but only half of it is visible to us. Suppose that the cells along the border-line of the visible world divide into four just like any other cells, but one of their descendants (namely the one that would live beyond the border-line) dies immediately for some unknown reason. The reason must be sought in the invisible part of the world. Maybe some cells live there too which we cannot see, but the effects of which we can observe.

Our task is to put cells into the invisible half of the world such
that their descendants destroy those descendants of the cells in the
visible world which would live in the invisible half. In this way we
can simulate that the cells along the border-line have only three
descendants. The task is easy to solve. We take the column in the
invisible half along the border-line, and we put the reflection of our
picture with respect to this column into the invisible world. (See
*Figure 4*.)

*Figure 4*

The position of the cells is always symmetrical to the middle column so cells will always come in pairs into the column and they will destroy each other.

After a few generations the descendants of cells of the invisible dog will appear in the visible world.

As we saw in the first part of the article both dogs produced four `descendants' but we can only see four of the eight descendants. Three descendants of the original and one of the reflected dog are visible to us. So, of the four visible dogs only three originate from the original dog, one (the one looking to the right) has come from the invisible world.

When the world is only a rectangle the situation is more
complicated. The principle of reflection has to be applied in a more
complicated way. Consider the two rows and two columns that border the
rectangle from outside. We need to put cells into the rest of the
plane in such a way that our picture be symmetrical with respect to
all four border-lanes. This can be done as pictured in *Figure
5*.

*Figure 5*

The descendants of different dogs sometimes appear in the rectangle which we can actually see. So, that is where all the different dogs come from.

### Exercises

1.) What happens if the world is not a rectangle but an isosceles right angled triangle (the hypotenuse of which forms a `stair')?

2.) What if the cells divide into nine descendants, one of which remains in the original square and the other eight go to the squares sharing a common vertex with the original square?

3.) Suppose that each cell divides into *n* descendants and
their positions are given by vectors \(\displaystyle nu\)_{1},\(\displaystyle nu\)_{2},...,\(\displaystyle nu\)_{n} originating from the
original square. Prove that after two generations the number of
descendants will still be *n* and their positions will be given
by vectors 2\(\displaystyle nu\)_{1},2\(\displaystyle nu\)_{2},...,2\(\displaystyle nu\)_{n}.

4.) Let the world be a rectangle of size *n*x*k*. Prove
that if *n*+1 and *k*+1 are powers of 2 then whatever
picture we start from, all the cells will die out sooner or later.

5.) What happens if the cells destroy each other not in pairs but in triplets? How does it affect the principle of reflection?

6.) Let the world be a rectangle of size *n*x*k*, and
suppose that whatever picture we start from all the cells die out
sooner or later. Prove that either *n*=*k*=2 or both
*n*+1 and *k*+1 are powers of 2.

### Computer Program II

By the next applet many interesting problems can be considered and
the answers of the exercises in the previous section can be
demonstrated. **We suggest to try the program after solving the
exercises.**

On the right side the rules of division and dsrtoying can be selected.

Clicking on the board, the content of the fields - the initial state - can be set. All fields can be set to contain 0, 1 or 2 cells or a wall.