# Turning coins on a chessboard

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?

• Jul 11, 2017 at 18:13

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.

• A simple confirmation of this would be to consider any board of n>2, Alice puts all the coins the same way except a single coin one corner. Such a position would clearly be impossible for Bob to solve Jul 9, 2017 at 18:54
• In addition to this, inverting the strategy entirely - flipping rows that you didn't, not flipping rows that you did, and same for columns - gives the same layout, so there's effectively $2^{2n-1}$ strategies. Jul 10, 2017 at 2:24
• @Dan Uznanski: Yes, good point! Jul 10, 2017 at 7:42
• @DarrenH But that is true even for a 2x2 board. If a coin is up and the other three are down, there's no way to bring all of them in the same direction, is it? Jul 10, 2017 at 10:05
• @BogdanAlexandru Yep, and Dan's comment explains why (in relation to this answer) - $2^{2n-1}$ is less than $2^{n^2}$ for $n=2$. Jul 11, 2017 at 17:46

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.

• (+1) "Try to find something that's invariant" is often a good strategy for problems like this, and the "something" very often involves parity (or more generally, modular arithmetic) Jul 9, 2017 at 21:55
• Of course if $n\ge 3$ is odd, you can look at a two-by-two corner of your board and apply your strategy on the "sub-board ". Jul 10, 2017 at 6:15
• @JeppeStigNielsen, that comment wasn't clear by itself but with Wojowu's answer it is. Jul 10, 2017 at 19:57

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$.

• This is a really nice solution - plus, Bob can win if and only if the starting configuration had rank $1$, since in that case, all the columns are equal either to the first column or its inverse - and he can make them all equal the first column by flipping. Then flipping appropriate rows makes him win. Jul 9, 2017 at 15:53

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.

• This also proves that Alice always wins the harder version where Bob can flip rows and columns even before Alice has finished placing the coins - because she can always complete a 2x2 square with the necessary parity. (Yes, I'd misread the question...) Jul 12, 2017 at 8:24

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 1 $$\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: 2

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. 3

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.

1 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*}

2 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$.
3 Again, I'm confident that a direct combinatorial proof exists (I have one for $d=3$).