Given a game board consisting of $n \times n$ square fields, where $n \geq 2$. Fields that are directly horizontally or vertically adjacent to a field are called its neighbors. At the beginning, $k$ game pieces are distributed on the fields, with multiple or no game pieces possibly being on a single field.

In each move, one selects a field that has at least as many game pieces as neighbors and places one of these game pieces on each neighboring field. The game ends when there is no such field to choose from.

(a) Determine the smallest $k$ for which the game does not end for any possible initial arrangement and choice of moves.

(b) Determine the largest $k$ for which the game ends for any possible initial arrangement and choice of moves.

(Theresia Eisenkölbl)
(a) If on each field there is one stone less than the number of neighbors, then there is not even a first move. However, if there is one more stone in the game, it cannot be avoided by the pigeonhole principle that on some field there are enough stones for the next move.

The sought number is thus the sum of all neighbor counts minus the number of all fields plus 1. If one adds $4 n$ fields around the entire arrangement of $n^{2}$ game fields, then each original field has exactly 4 neighbors and each new field has contributed one neighbor.

Thus, $k=\left(4 n^{2}-4 n\right)-n^{2}+1=3 n^{2}-4 n+1$.

(b) It is easy to see that with an unlimited number of moves, the stones must eventually reach every field and thus also be exchanged between every pair of neighboring fields: Otherwise, there would be a permanently inactive field with an active neighbor, which would result in a stone being moved from the active to the inactive field, and over the course of the game, an arbitrarily large number of stones would accumulate in the supposedly inactive field.

However, as soon as a stone moves from a specific field to another for the first time, this stone can be reserved to only move between these two fields. The game thus certainly ends if there are fewer stones than neighbor pairs.

Conversely, if at least as many stones as neighbor pairs are available, one can proceed as follows: The fields can be colored black and white like a chessboard, and on each black field, one can place as many stones as neighbors. It is then seen that it is possible to play indefinitely if the stones are always first transferred from all black to all white fields and then from all white to all black fields.

The sought largest number is thus the number of neighbor pairs minus 1. The number of neighbor pairs is exactly half of the first expression in the calculation for the first part, and we obtain $k=2 n^{2}-2 n-1$.

(Theresia Eisenkölbl)