Odd, even and things that never change
Tonight's idea
Some puzzles ask "can you do it?" and the answer is no, but you cannot prove no by trying. You would be trying forever. You need a different weapon: find something that never changes no matter what move you make. Mathematicians call it an invariant. If the thing you want has a different value of the invariant from where you started, you can never get there. Done, no trying needed.
The simplest invariant is odd-or-even, called parity. Flip a coin twice and it is back how it started. Add two odd numbers and you get an even one.
The famous example is the mutilated chessboard. Cut two opposite corners off a chessboard, leaving 62 squares. Can you cover them exactly with 31 dominoes, each domino covering two neighbouring squares? People try for hours. Then someone notices: every domino covers one black square and one white square, because neighbours always have different colours. Opposite corners are the same colour. So the mutilated board has 32 of one colour and 30 of the other, and 31 dominoes would need 31 and 31. Impossible. The invariant is "black squares covered minus white squares covered", and it is always zero.
Handshakes have a parity secret too. Every handshake involves two hands. So if you add up the number of hands each person shook, the total is twice the number of handshakes, which is even. That means the number of people who shook an odd number of hands is always even.
Watch one: seven cups
Seven cups sit upside down. A move is: pick any two cups and flip them both. Can you get all seven the right way up?
Count the upside-down cups. Start: 7. A move flips two cups. If both were upside down, the count drops by 2. If both were upright, it rises by 2. If one of each, the count stays the same. In every case the count changes by 0 or 2, so it stays odd. The goal, 0 upside-down cups, is even. Impossible.
Now try the same with 8 cups. The count starts even, and 0 is even, so parity does not forbid it. And indeed four moves do it. Parity can prove impossibility, but when it allows something, you still have to find the way.
Your turn
- Seven people are at a party. Can each of them shake hands with exactly three of the others? What about eight people? Explain using the handshake fact.
- Can a 5 by 5 board be covered exactly with dominoes? Give a one-line reason.
- Cut two squares off a chessboard that are different colours (say one corner and the square next to it). Does the colour argument still rule out tiling with 31 dominoes? To get a feel, remove the top-left and top-right squares of a 2 by 4 strip and tile what is left. Harder: can you find a method for any two different-colour squares? Hint: draw a closed route through every square once.
- You write the numbers 1 to 10 on a board. A move is: erase any two numbers \(a\) and \(b\) and write \(a + b\) instead. After 9 moves one number is left. What is it, and why does it not matter which pairs you chose? Now change the move to writing \(a - b\) instead. Could the last number be 0? (Think about parity of the total.)
- Magic. Lay 20 coins on a table, 7 of them heads up. Put on a blindfold. Challenge: split the coins into two piles so that both piles show the same number of heads. You may flip coins over but you cannot feel which side is up. Here is the method: take any 7 coins into a pile and flip every coin in that pile. Explain why it works. (Hint: suppose \(h\) of the 7 coins you grabbed were heads. How many heads are left in the big pile? How many in your pile after flipping?)
Stretch: the chameleons
On an island live 13 red, 15 green and 17 blue chameleons. Whenever two chameleons of different colours meet, they both turn into the third colour. (Red meets green: both become blue.) Can the chameleons ever all be the same colour?
Hint. Look at the differences between the counts, and look at what a meeting does to them. Then look at remainders when you divide by 3. Which of those remainders can never change?
Answers
- Seven people each shaking 3 hands gives a hand-total of \(7 \times 3 = 21\), which is odd, but the total must be twice the number of handshakes. Impossible. Eight people: \(8 \times 3 = 24\), even, and it can be done (sit them in a circle and shake with both neighbours and the person opposite).
- A 5 by 5 board has 25 squares, an odd number, and dominoes cover 2 at a time. Impossible.
- No. With one black and one white removed, the counts are 31 and 31, so the colour argument no longer rules it out. The 2 by 4 strip with its top-left and top-right squares removed tiles with three dominoes: one across the top, two across the bottom. For the full chessboard, here is a method for any two different-colour squares; see the route proof below.
- Adding: the sum of all numbers on the board never changes, so the last number is \(1 + 2 + \cdots + 10 = 55\). Subtracting: replacing \(a, b\) by \(a - b\) changes the sum by \(2b\), an even amount, so the parity of the sum stays odd (it starts at 55). The final number is odd, so it cannot be 0.
- Suppose \(h\) of the 7 coins you grabbed are heads. Then the big pile has \(7 - h\) heads. Your pile has \(h\) heads and \(7 - h\) tails; after flipping it has \(7 - h\) heads. Both piles show \(7 - h\) heads. You never needed to know \(h\).
Stretch. A meeting lowers two counts by 1 and raises the third by 2. The difference between any two counts changes by 0 or by 3, so each difference keeps the same remainder when divided by 3. Start: 15 − 13 = 2, 17 − 15 = 2, 17 − 13 = 4, with remainders 2, 2, 1. If all chameleons were one colour, two of the counts would be 0 and their difference would be 0, remainder 0. No difference ever has remainder 0, so it can never happen.
Optional: a route that becomes dominoes
The left picture is a closed route through all 64 squares (a Hamiltonian cycle), so its colours alternate. Remove one black and one white square: the route breaks into two paths whose ends differ in colour, so each has an even number of squares (or none, if the gaps were neighbours). Pair up consecutive squares along each path: every pair is a domino and no square is missed.