Skip to main content
OlympiadHQ

Browse · MathNet

Print

SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Saudi Arabia counting and probability

Problem

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.
Solution
If 32 frogs are placed in an rectangle, they can all move down, right, up, left, down, etc.
00000000
00000000
00000000
00000000
To show that a game with 33 frogs must stop, label the board as shown:
121212121
232323232
121212121
232323232
121212121
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.

Techniques

Invariants / monovariantsColoring schemes, extremal argumentsPigeonhole principleGames / greedy algorithms