Question 10
On a chessboard $5 \times 9$ 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.
- 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.