Putnam 2014, Problem B-5

In the 75th annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible $n \times n$ matrices with entries in the field $\mathbb{Z}/p\mathbb{Z}$ of integers modulo $p$, where $n$ is a fixed positive integer and $p$ is a fixed prime number. The rules of the game are:
(1) A player cannot choose an element that has been chosen by either player on any previous turn.
(2) A player can only choose an element that commutes with all previously chosen elements.
(3) A player who cannot choose an element on his/her turn loses the game.
Patniss takes the first turn. Which player has a winning strategy? (Your answer may depend on $n$ and $p$.)

Solution:
We show Patniss wins if \(p = 2\) and Keeta wins if \(p > 2\). For a finite group \(G\), let \(Z(S)\) be the centralizer of \(S \subseteq G\). Initially \(S = \emptyset\), \(Z(S) = G\). After each turn, \(S\) increases by one element, and \(Z(S)\) is replaced by a subgroup. If \(Z(S)\) has odd order, it remains odd; if even, it remains even. Thus, an element \(g \in G\) of odd order is a winning first move for Patniss, while an even-order element is winning for Keeta.  
For \(G = \text{GL}_n(\mathbb{Z}/p\mathbb{Z})\): If \(p > 2\), \(Z(S)\) always contains \(-I\) (order 2), so Keeta wins (respond to any \(g\) with \(-g\)). If \(p = 2\), construct an irreducible polynomial \(P(x)\) of degree \(n\) over \(\mathbb{Z}/2\mathbb{Z}\) (e.g., \(x^n + x + 1\) for \(n\) odd). Let \(g\) be the companion matrix of \(P(x)\); then \(\det(g) \neq 0\), so \(g \in G\), and \(Z(\{g\})\) has odd order (since \(g\) is diagonalizable with distinct eigenvalues over \(\overline{\mathbb{Z}/2\mathbb{Z}}\)), so Patniss wins.