Cut and Restored Checkerboard

Imagine you have a 4x4 checkerboard (alternating black and white squares).

You cut this board into the 16 individual squares, turn them face down, then shuffle them (all the backs are identical). You re-arrange them back into a 4x4 square and turn them over to reveal their faces again.

What is the probability that, after the shuffle, the board is back into a checkerboard arrangement? (It does not have to the same chirral version of the checkerboard, the top cornder does not need to be same colour as the original; it can be a rotation, as long as it is well-formed.).

Think about turning the squares over one by one. The first square is a gimme, it does not matter what it is, so you have a 100% chance of getting a tile that you need (16/16), then imagine we are walking along each row/column, the first adjacent square needs to be the opposite colour, so there are 8 unpicked opposite tiles from out of 15 unseen (8/15). The next tile reverts to the original color, and there are 7 available out of 14 unseen (7/14), then 7 out of 13 …

The last tile is a gimme too; there is no choice (1/1).

If you look closely at the top, you will see the numbers come in pairs, and the product of the denominators is just 16!

So you need to repeat the process many thousands of time before expecting to get it right.

When I posted this problem to my friends on facebook, many got the correct answer, and there were some different variants in their methods of calculation. Of course, the solution is the same, it just goes to show how there are different ways to skin a cat and a reflection of how different people apply logic in different ways to solve the same problem. Diversity is good.

The most common variant was to chose a color, and make a very similar probability chain, but this time the first term is 8/16 (there are initially eight squares of your selected colour). They then multiplied the entire expansion by two (because there are two possible choices of the first colour).

I think you can quickly see this gives the same answer.

Another friend suggested that all we need to is examine eight tiles. Rather than revealing them sequentially, imagine turning them over every other tile (alternating), testing just the squares we hope will be the same colour. If we turn over these eight, and are successful, the remaining tiles have to all be the opposite colour.

Yet another way was to again work with turning over just eight, and say that you had 16 choices for the first pick, the 7 available for the next (you’ve been allocated a colour after the first turn), then 6, then five …

So, there are 16 × 7 × 6 × 5 × 4 × 3 × 2 × 1 variants of picks that all result in the same colour. These eight tiles could be arranged a total of 8! different ways, resulting in a denominator of 16 × 7! × 8! This is the total possible ways the tiles could be arranged so pulled with the first eight appropriate ones of matching colour. There are a total of 16! possible ways all the tiles could be arranged, to the equation is:

Because of the factorials, the numbers get very big very quickly. If you tried this exercise with a larger checkerboard, which is 8x8, you ar4 going to have a pretty miserable time.