KA-0176Coloring arguments
5 points, difficulty 3 of 3Level 11–12about 165sAn 8 by 8 chessboard has two opposite corner squares removed, leaving 62 squares. Each domino covers exactly two squares that share an edge. Can the 62 squares be covered exactly by 31 dominoes?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Colour the board like a real chessboard and look at what each domino must cover.
2The strategy
Every domino covers exactly one black and one white square, whatever its position or orientation.
3The full solution
Opposite corners of a chessboard share a colour, so removing them leaves 32 of one colour and 30 of the other - and 31 dominoes would need 31 of each.
Solution
The reliable way
Colour the board in the usual alternating pattern. Because neighbouring squares always differ in colour, every domino - however placed - covers exactly one square of each colour. So 31 dominoes must cover 31 black and 31 white squares. Now, the two opposite corners of a chessboard are always the SAME colour. Removing them leaves 32 squares of one colour and 30 of the other, which no set of 31 dominoes can match. The covering is therefore impossible. The transferable idea: a colouring turns an impossible search over arrangements into a single counting statement.
The elegant way
Every domino takes one square of each colour, and the mutilated board has 32 of one and 30 of the other.
Why this is on the test: This is the cleanest example of a colouring argument, where proving impossibility is easier than any amount of searching.