39
$\begingroup$

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?

$\endgroup$
69
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ 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 $\endgroup$ – Darren H Jul 9 '17 at 18:54
  • 3
    $\begingroup$ 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. $\endgroup$ – Dan Uznanski Jul 10 '17 at 2:24
  • $\begingroup$ @Dan Uznanski: Yes, good point! $\endgroup$ – quasi Jul 10 '17 at 7:42
  • $\begingroup$ @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? $\endgroup$ – Bogdan Alexandru Jul 10 '17 at 10:05
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brilliand Jul 11 '17 at 17:46
60
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ (+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) $\endgroup$ – Silverfish Jul 9 '17 at 21:55
  • 17
    $\begingroup$ 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 ". $\endgroup$ – Jeppe Stig Nielsen Jul 10 '17 at 6:15
  • $\begingroup$ @JeppeStigNielsen, that comment wasn't clear by itself but with Wojowu's answer it is. $\endgroup$ – Wildcard Jul 10 '17 at 19:57
30
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Jul 9 '17 at 15:53
25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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...) $\endgroup$ – Julia Hayward Jul 12 '17 at 8:24
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.