$n^2$ coins on a board flipping game

combinatoricsdiscrete mathematics

This is something I needed a little help with, I've been stuck on this problem for a while now.

Suppose you have $n^2$ coins on an $n \times n$ grid, $\left( n \gt 0\right)$, each with their heads side up. In each move, you can pick one of the $n$ rows or columns and flip over all of the coins in that row or column. No other move is permitted. You have an unlimited number of moves. You win by reaching a configuration where there is exactly one tail side up coin. Does this apply to all $n$?

I really have no idea how to go about it. I tried for the $2\times 2$ grid and I can say that there is no way to achieve one tail side up for the $2\times 2 $ grid.

Best Answer

You cannot on any board except $n=1$.

First note that the order you do flips does not matter because the effects commute. Doing a flip twice is equivalent to not doing it at all, so all you care about is which rows and columns you have flipped once.

A simple proof is that you cannot succeed for even $n$. You start with an even number of heads and each move flips an even number of coins, so the number of heads must stay even.

On a board with odd $n$ all the coins are equivalent, so we might as well try to have the top left coin be the one that finishes tails. Then if we just look at the $2 \times 2$ piece of the board in the upper left, we have to solve that and the only moves that matter are the top two rows and the left two columns. If we can solve the subboard, we can solve $2 \times 2$, which we cannot.

Related Question