Turning coins on a chessboard

Question

Alice and Bob are playing a game on a $n \times n$ chessboard.

Alice puts coins on each square; she may choose to put any one of them heads up or tails up. Then Bob may perform any number of moves, where a move is to turn all coins in a single row or column; his goal is to have all coins heads up.

Could Bob always manage to do it?

Answer 1

No, it's not always possible.

There's never any point to flip a row or column more than once, and the order of the moves doesn't matter.

Thus, there are only $2^n$ row flip strategies, and $2^n$ column flip strategies, yielding at most $(2^n)(2^n) = 2^{2n}$ possible strategies.

But there are $2^{n^2}$ possible positions, hence, when $n^2 > 2n$ (e.g., $n \ge 3$), not all positions can be reached from the the all-heads position. Equivalently, when $n^2 > 2n$, not all positions can reach the all-heads position.

Answer 2

If $n$ is even, then the number of heads never changes parity. So, if you start with an odd number of heads, you'll never finish with all heads.

Answer 3

Another solution using matrices:

Denote by $ A \in \mathbb R ^{n \times n}$ the matrix representing the board, where heads is represented by $-1$ and tails by $1$. Flipping the $i$-th column/row is the same as multiplying the $i$-th column/row in the matrix by $-1$. Such a move does not change the rank of the matrix, as it is the same as multiplying $A$ with a diagonal matrix $\operatorname{diag}(1, \dots, -1, \dots, 1)$ from right/left.

The configuration with all heads up has rank $1$. Thus the only configurations that can possibly be reached are those with rank $1$. Obviously there are configurations with rank $\geq 2$.

Answer 4

Consider any $2\times 2$ square contained in the chessboard. It's easy to see that the number of heads in this square is odd, then it will stay odd after any Bob's move. Hence if $n\geq 2$ and Alice puts exactly one coin heads up, then Bob won't be able to flip all of them heads up.

Answer 5

A more elaborate counting argument.

More generally, let's take a $d$-dimensional checkboard of size $n_1\times\cdots\times n_d$ with the rule that we may flip coins in any hyperplane parallel to a coordinate hyperplane. Initally all coins are heads up. The natural questions to ask are:

Question 1. What are the possiblities for the number of heads-up coins after performing some moves?
Question 2. How many configurations are possible?

Note that, by inverting all hyperplanes in a certain direction, we invert the entire cuboid, so it is equivalent to ask how many tails we can have.

The operations commute and are involutions, so we may suppose no hyperplane is inverted twice, and a resulting configuration is then determined by the inverted hyperplanes. (But may be obtained in $2^{d-1}$ distinct ways; see below.) Say $a_1,\ldots,a_d$ hyperplanes are inverted along each of the directions.

The number of heads-up coins is then $$\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|\text{ even}}}\prod_{k\in S}a_k\prod_{k\notin S}(n_k-a_k)\tag1$$ (the number of coins flipped 0 times, twice, four times, etc...)

This equals ¹ $$\frac12\left(N+\prod(n_k-2a_k)\right)\tag2$$

where $N=n_1\cdots n_d$.

We conclude that:

$H$ heads can be obtained iff $|2H-N|$ can be written as $b_1\cdots b_d$ with each $b_k\in\{0,\ldots,n_k\}$ of the same parity as $n_k$

In particular: ²

If $n_1=\ldots=n_d=n$ is even, then $2^{d-1}\mid H$.

To answer the second question, note that we're considering an action of $(\mathbb Z/2)^{n_1+\cdots+n_d}$ on the coins, and the orbit of each configuration is $2^{n_1+\cdots+n_d}$ divided by the stabilizer of (for example) the initial one.

The order of the stabilizer is the sum of the $\prod\binom{n_k}{a_k}$ over the solutions to $$N=\prod(n_k-2a_k),\qquad a_k\in[0,n_k]$$

Considering the absolute value learns that an even number of $a_k$'s equals $n_k$ and an odd number equals $0$. The binomial coefficients are all $1$, and we get $2^{d-1}$ for the order of the stabilizer:

There are $2^{n_1+\cdots+n_d-d+1}$ possible configurations, out of $2^{n_1\cdots n_d}$ in total. ³

A quick induction shows that $n_1\cdots n_d-(n_1+\cdots+n_d-d+1)\geq0$ with equality iff all but at most one $n_k=1$. So except for the $1\times\cdots\times1\times n$ cuboids, there are always unreacheable configurations.

---

¹ Proof 1: Each term $\prod_{k\notin T}n_k\prod_{k\in T}a_k$ appears in $(1)$ with coefficient $(-1)^{|T\setminus S|}$ for each $S\subset T$ with $|S|$ even. By this, this gives $2^{d-|T|-1}$ for $T\neq\varnothing$, so we get the expansion of $(2)$ (see also second proof).

Proof 2: $$\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|\text{ even}}}\prod_{k\in S}a_k\prod_{k\notin S}(n_k-a_k)=\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|+d\text{ even}}}\prod_{k\notin S}a_k\prod_{k\in S}(n_k-a_k)$$

and

$$\begin{align*}\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|+d\text{ even}}}\prod_{k\notin S}a_k\prod_{k\in S}(n_k-2a_k+a_k) &=\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|+d\text{ even}}}\sum_{T\subset S}\prod_{k\notin S}a_k\prod_{k\in T}(n_k-2a_k)\prod_{k\in S\setminus T}a_k\\ &=\sum_{T\subset\{1,\ldots,d\}}\prod_{k\in T}(n_k-2a_k)\prod_{k\notin T}a_k\cdot\#\{S: T\subset S\subset\{1,\ldots,d\}, |S|+d\text{ even}\}\\ &=\prod(n_k-2a_k)+\sum_{\substack{T\subset\{1,\ldots,d\}\\|T|<d}}\prod_{k\in T}(n_k-2a_k)\prod_{k\notin T}a_k\cdot 2^{d-|T|-1}\\ &=\frac12\prod(n_k-2a_k)+N/2\end{align*}$$

² I believe direct combinatorial proofs of $2^k\mid H$ for all $k<d$ are possible as well, but become less elegant for $k>1$.
³ Again, I'm confident that a direct combinatorial proof exists (I have one for $d=3$).