Pat has a pentagon, each of whose vertices is coloured either red or blue. Once an hour, Pat recolours the vertices as follows.
* Any vertex whose two neighbours were the same colour for the last hour, becomes blue for the next hour.
* Any vertex whose two neighbours were different colours for the last hour, becomes red for the next hour.
Show that there is at least one vertex which is blue after the first recolouring and remains blue for ever.
Solutions — 3
Solution 1
This problem yields to brute force: there are 32 starting configurations and the result can be verified by checking all cases manually.
Solution 2
We can reduce the number of cases substantially by noting the limited number of feasible cases after the first recolouring and then exploiting the symmetry of pentagons.
Now make one loop around the pentagon in linking alternate vertices, tracing a pentagram. There must be an even number of colour changes, because we return to the first vertex as the loop is complete. Each colour change results in a red colour for the skipped vertex, while each non-change results in a blue.
Therefore, at every step beyond the initial configuration, there must be an even number of red vertices (and an odd number of blue vertices). We enumerate these cases: the red vertex count must be 0, 2 or 4.
If the red vertex count is zero, then the pentagon is all blue which is a stable configuration and the problem is solved in this case.
If the red vertex count is even but non-zero, then there could be two reds. The two reds may be opposite as in the left-most diagram below, or adjacent as in the middle diagram. The last possibility is four reds which is the right-most diagram.
We now notice that the successor to the left diagram is the middle diagram. The successor to the middle diagram is the right diagram, while the successor to the right diagram is the left diagram. So, after the first step, the pentagon is either all blue or establishes the three-cycle shown in the diagrams. For the three-cycle (in the orientation we have shown here), the top vertex is always blue. This completes the solution.
Solution 3
The times used below denote positions on a clock face as shown in the diagram.
We rotate the pentagon such that its initial colouring has a vertical line of reflective symmetry. We can do this as follows:
| Count | Red Positions | Count | Blue positions |
|---|---|---|---|
| 5 | 12:00, 2:24, 4:48, 7:12, 9:36 | 0 | — |
| 4 | 2:24, 4:48, 7:12, 9:36 | 1 | 12:00 |
| 3 | 12:00, 2:24, 9:36 | 2 | 4:48, 7:12 |
| 3 | 12:00, 4:48, 7:12 | 2 | 2:24, 9:36 |
| 2 | 4:48, 7:12 | 3 | 12:00, 2:24, 9:36 |
| 2 | 2:24, 9:36 | 3 | 12:00, 4:48, 7:12 |
| 1 | 12:00 | 4 | 2:24, 4:48, 7:12, 9:36 |
| 0 | — | 5 | 12:00, 2:24, 4:48, 7:12, 9:36 |
There are two rows for the 2:3 and 3:2 splits as the two vertices may be adjacent or opposite.
We note the recolouring operation preserves the axis of symmetry. Finally, as the two vertices at 2:24 and 9:36 are always the same colour, then for any time strictly after the first recolouring, the top vertex is blue.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.