## Magical chameleons

An island contained chameleons of three different colours: red, green and yellow. The chameleons were studied by some biologists and they found that when two chameleons of different colours met they changed their colours to the third one. They found that there were 2000 red chameleons and 3000 green ones on the day they counted them. They didn't get time to count the number of yellow chameleons.

When the biologists returned to the island 2 years later they found that all chameleons were red in colour. They were certain that no chameleons died because they did not find dead remains of any chameleon. What does it say about the number of yellow chameleons on the day the biologists counted the number of red and green chameleons?

[SOLVED]

### 1 comment

#### Joshua Tobin solved this puzzle:

Some notation: I use tuples like (y, r, g) to represent the numbers of chameleons of each colour at any given time. I say "transformation" to mean some group of chameleons changing colour. Then I work backwards in time. So, if we have (y, r, g) chameleons now, before the last transformation we must have had (y − 2x, r + x, g + x) or (y + x, r − 2x, g + x) or (y + x, r + x, g − 2x). I write the first transformation as: (y, r, g) ← (y − 2x, r + x, g + x), for example.

Let d be the number of yellow chameleons when the zoologists first arrived.

So we know that when the zoologists arrived for the second time they observed (0, 5000 + d, 0), and when they arrived the first time they observed (d, 2000, 3000). The question is: what are the possible values of d? I answer this in two parts.

Part 1: d must be a multiple of 3.

Proof: Let's look at each of the operations mod 3. For example, (y, r, g) ← (y − 2x, r + x, g + x). Note that −2x and +x are the same modulo 3. So every transformation just adds the same number to each of the three totals modulo 3. Same for the other two transformations: (y, r, g) ← (y + x, r − 2x, g + x), (y, r, g) ← (y + x, r + x, g − 2x).

So, if y and g are the same at the start, they will be the same at the end (mod 3). We know that we reach (0, 5000 + d, 0) from (d, 2000, 3000), and so d and 3000 must be the same (mod 3). Hence d is 0 (mod 3).

Part 2: If d is any multiple of 3 we can find a sequence of transformations to get (0, 5000 + d, 0) from (d, 2000, 3000).

Proof: Say we have (y, r, g), and r is greater than 4. Then we can get: (y, r, g) ← (y + 2, r − 4, g + 2) ← (y, r − 3, g + 3). This means we can keep taking 3 from g and adding it to r. So we can get (0, 5000 + d, 0) if we start with (0, 2000 + d, 3000).

Similarly we can get: (y, r, g) ← (y + 2, r − 4, g + 2) ← (y + 3, r − 3, g). So we can keep taking 3 from y and adding it to r. If d is a multiple of 3, we can use this to get (0, 2000 + d, 3000) from (d, 2000, 3000).

Putting these two together, we can deduce from the given information that the number of yellow chameleons on the first day is a multiple of 3.

### Credit

This puzzle is based on: