National Competition

1. If each cell contains one token less than the number of its neighbors, the game cannot even start. On the other hand, if there is one token more, then by the pigeon-hole principle there will always exist at least one cell with sufficient tokens to make the next move. Therefore, the desired quantity is the sum of all numbers of neighbors minus the number of all cells plus 1. If one adds $4n$ cells around the $n^2$ given cells, each original cell has four neighbors and each new cell has contributed one neighbor. We get $k=(4n^2-4n)-n^2+1=3n^2-4n+1$.

2. It is easy to see that an unlimited number of turns must eventually have brought tokens to all cells and that also every pair of neighbors must have exchanged tokens because otherwise tokens would accumulate in unlimited number in one of the inactive cells. But each time, a neighboring pair first exchanges tokens, we can reserve this first token to stay always between these two neighbors. Therefore, the game will certainly end if there are less tokens than neighboring pairs. Conversely, if the number of tokens equals the number of neighboring pairs, we can find a never-ending game in the following way: Color the cells black and white in a checkerboard fashion and assign to each black cell a number of tokens that equals the number of its neighbors. Now we will simply choose all the black cells until all tokens are on the white cells, then repeat with the white cells and then iterate from the start. The desired quantity is therefore the number of neighboring pairs minus 1. Since the number of neighboring pairs is half of the first expression in the computation of part 1, we get $k=2n^2-2n-1$.