Problem

Source: 2016 Saudi Arabia BMO TST , level 4, III p4

Tags: combinatorics, game, Chessboard



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: $\bullet$ Each frog may be moved one square up, down, left, or right; $\bullet$ If a frog moves up or down on one turn, it must move left or right on the next turn, and vice versa; $\bullet$ 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.