On a chessboard squares, the following game is played. Initially, a number of frogs are randomly placed on some of the squares, no square containing more than one frog. A turn consists of moving all of the frogs subject to the following rules:
- Each frog may be moved one square up, down, left, or right;
- If a frog moves up or down on one turn, it must move left or right on the next turn, and vice versa;
- At the end of each turn, no square can contain two or more frogs.
The game stops if it becomes impossible to complete another turn. Prove that if initially 33 frogs are placed on the board, the game must eventually stop. Prove also that it is possible to place 32 frogs on the board so that the game can continue forever.
Saudi Arabian Mathematical Competitions
Solution
If 32 frogs are placed in an rectangle, they can all move down, right, up, left, down, etc.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
To show that a game with 33 frogs must stop, label the board as shown:
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 2 | 3 | 2 | 3 | 2 | 3 | 2 |
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
| 2 | 3 | 2 | 3 | 2 | 3 | 2 | 3 | 2 |
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
Note that a frog on 1 goes to a 3 after two moves, a frog on 2 goes to 1 or 3 immediately, and a frog on 3 goes to a 2 immediately. Thus if frogs start on 1 and , the game stops because there are not enough 3s to accommodate these frogs. Thus we assume , in which case there are at most 16 squares on 1 or 3 at the start, and so at least 17 on 2.
Of these 17, at most 8 can move onto 3 after one move, so at least 9 end up on 1; these frogs will not all be able to move onto 3 two moves later, so the game will stop.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.