Let $r\geq 1$ be a natural number. I am interested in the following (two-player, impartial, perfect-information) game:

  • The state of the game is an $n\times n$ matrix with coefficients in $\mathbb{F}_2$ (we can imagine it as an $n\times n$ array of coins that can show either tails=$0$ or heads=$1$).

  • A move consists of adding a matrix of rank $\leq r$ to the state...

  • ...with the additional constraint that the state should decrease in the lexicographic order (i.e., among those matrix entries that change, the rightmost one on the bottommost line should change from $1$ to $0$; this constraint guarantees termination in finite time).

  • Whoever reaches the zero matrix wins (i.e., the player who cannot play loses).

I am willing to consider variations on the "decreasing" constraint if they make the analysis simpler.

The case $r=1$ is known: it is a coin-turning game where each player selects a set of lines and a set of columns and turns every coin whose line and column are in the selected sets, with the additional constraint that the coin in the rightmost column and the bottommost line should turn from heads ($1$) to tails ($0$). The Grundy value of the state is the nim sum of the $2^a \bullet 2^b$ where $(a,b)$ ranges over the (line,column) coordinates, counted from $0$, of the coins showing heads ($1$), and $\bullet$ denotes nim multiplication.

The general case is a "move $r$ times" variant of the above game (at least for some "decreasing conditions"). My question is whether it has already appeared in the literature, and if its Grundy function is explicitly computable.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.