Problem

Source: Canada RepĂȘchage 2019/5 CMOQR

Tags: game, game strategy, winning strategy, combinatorics



Let $(m,n,N)$ be a triple of positive integers. Bruce and Duncan play a game on an m\times n array, where the entries are all initially zeroes. The game has the following rules. $\bullet$ The players alternate turns, with Bruce going first. $\bullet$ On Bruce's turn, he picks a row and either adds $1$ to all of the entries in the row or subtracts $1$ from all the entries in the row. $\bullet$ On Duncan's turn, he picks a column and either adds $1$ to all of the entries in the column or subtracts $1$ from all of the entries in the column. $\bullet$ Bruce wins if at some point there is an entry $x$ with $|x|\ge N$. Find all triples $(m, n,N)$ such that no matter how Duncan plays, Bruce has a winning strategy.