The method of proof in the mutilated chess problem

Question

The mutilated chess problem is a well-know riddle that can be solved easily with some insight. Namely, one is asked about the possibility of covering a chessboard having two opposite corners cut off with 2x1 dominoes, and the impossibility of such a task is easily demonstrated by the fact that each domino must cover one black square and one white square, while the opposite corners of a chess board are of the same color.

Stated as such, the solution is seen as merely a clever analysis of the statement of the problem.

But what if the problem didn't make any mention of a chessboard at all, and only considered an 8x8 grid with opposite corners removed ? The problem could have been solved in a similar way, except one would've had to have the idea of dividing the squares into two alternating classes first, and then deduce the negative conclusion following the earlier argument.

My question is the following. What are other examples of proofs where a similar pattern of reasoning has been employed, that is where extra structure has been added first to the problem to allow for an easy solution ?

Answer 1

This technique is actually very common in impossibility proofs in numerous puzzles. One tries to define an "invariant" - a quantity that is preserved by moves. Then show that the starting and ending position have different values for the invariant. In the example, the invariant is the difference in the numbers of uncovered white tiles and black tiles. Placing a domino must cover one of each, so the difference between them is unchanged. In the initial position (no dominos) the difference is $2$, while in the end state (entirely covered), it is $0$.

A couple examples involving the Rubik's cube:

Each position of a Rubik's cube represents (among other things) a permutation of its pieces from their solved position. It also represents a permutation of the facets of the cube (the individual color tiles on each piece). Turning a face of the cube is composing the current permutation of the position with a new permutation of just the pieces or facets on that face. Whether of pieces or of facets, these face-turn permutations are both even. Thus the parities of the permutations for the old and new positions have the same partity. Parity of piece positions and parity of facet positions are thus both invariants of the Rubik's cube.

From parity of piece positions, we thus get:

• It is impossible to exchange the locations of two edge pieces while leaving all other pieces unmoved.
• It is impossible to exchange the locations of two corner pieces while leaving all other pieces unmoved.

Either exchange represents an odd permutation of pieces.

From parity of facet positions, we thus get:

• It is impossible to flip an edge piece in place without making other changes.

Such a flip exchanges just the two facets on the edge piece, which is an odd permutation of the facets.

There is one other restriction on possible cube positions: you cannot rotate a single corner while making no other changes. But this is an even permutation of the facets, so a different argument is needed to prove it. The needed invariant is more complex, and somewhat arbitrarily defined (treating some colors differently from others) so I will not reproduce it here.