Solution to Parity Puzzles

See the original puzzles

Puzzle #1: See image

If we color the shape in a checkerboard pattern, then each domino must cover exactly one blue square and one green square. The problem? There are 23 green squares and 25 blue squares. Therefore it's impossible.

Puzzle #2: See Image

Here, we imagine that the entire plane is tiled with a checkerboard pattern like shown in the above image. Each N tetromino covers an odd number of green squares. So an odd number of N tetrominoes covers an odd number of green squares. But each O tetromino covers an even number of green squares. Therefore it's impossible to find a shape that can be tiled by an odd number of N tetrominoes or an odd number of O tetrominoes.

Similar proofs can be constructed for any pair of tetrominoes.  But I leave this as an exercise to the reader.

Reader Secret Squirrel proposed another proof that was a little more complex.  I summarize it here:

1. Each N tetromino is either vertically or horizontally oriented.  So out of an odd number of N tetrominoes there must either be an odd number of vertical tetrominoes or an odd number of horizontal tetrominoes.
2. Let's say that there are an odd number of horizontal N tetrominoes (if not, then rotate the plane 90 degrees).  Consider the number of squares covered in each column, and consider whether this number is odd or even in each column.  Each horizontal N tetromino contributes an "unpaired" square to two columns (and vertical tetrominoes contribute nothing).  It's impossible to pair up all the unpaired squares with an odd number of tetrominoes.
3. If we build a shape with O tetrominoes, each column must have an even number of squares covered.  Therefore, we can't build the same shape with O tetrominoes.

On some reflection, you might see that Secret Squirrel's solution is the same as mine.  Consider this image. If we just consider the horizontally oriented N tetrominoes, then each covers an odd number of green squares.  This is equivalent to step 2 above.  However, we're ignoring the vertical tetrominoes, so we also need to add on a pattern of horizontal stripes.  The horizontal and vertical stripes add up to a checkerboard pattern.

I think this is a case of polished vs unpolished proof.  When you first figure out how to prove a proposition, it's often clunky and difficult.  But from there you can remove the scaffolding and polish it.  But you would never think of the polished proof at first.  When I first formulated a proof, it didn't look much like looks now.

Sometimes this is a problem with math and physics textbooks.  They only present the most polished proofs, leaving it a mystery how anyone ever thought them up.  I sure felt this way all the time in abstract algebra.