The filmmaker Orson Welles once said that the enemy of art was the absence of limitations. Mathematicians like to play with limitations too. Constraining actions can create all kinds of novel situations and beautiful structure.
Let’s imagine some coins that are red on one side and blue on the other. I’m going to give myself the constraint that I can only ever flip over three adjacent coins at a time. That’s a pretty tight constraint; it means I can never flip over one, two, or four coins in a single move. But that, as you’ll see, is where the fun comes in!
So I don’t have to write so many words, I’ll call these flips of three adjacent coins 3-flips .
Definition. A 3-flip is a flip of 3 adjacent coins.
Notice that the middle coin gets flipped over twice in the sequence, once to go to red, and again to go to
Right away I’m curious if it’s possible to ever flip these five coins all to red, if I only ever make these 3-flips. And in fact, it cannot be done.
Puzzle 1.
Convince yourself that it is impossible to change five coins in a line from blue to red using only 3-flips. What about 10 coins in a row?
Note: this puzzle is probably the hardest today, since it can’t be done. Proving things are impossible is almost always harder than proving them possible. After all, if it is possible, you can just do it. If it is impossible, you need to somehow show that no matter what someone does, the thing is still undoable.
Puzzle 2.
Arrange ten coins in a circle. How can you use 3-flips to change all the coins from blue to red?
Solutions
Puzzle 1. This is the subtle one. To prove that it is impossible to change a line of 10 blue coins from blue to red with 3-flips. You’ve probably seen this by playing with them: there’s always one finicky coin that remains blue no matter what you try. But how can we know for sure?
This is where we use what are known as invariants . We’ve used them before, but we have to be clever to find one here. Let’s try this: give each coin a value of 1 or 0, as follows:
Let’s imagine that we left all the coins blank on the red side. When we flip over the coins, we’ll hide a number. That means that if we can flip over all the coins, the total sum of the numbers will be 0, since there won’t be any numbers at all! Right now, the sum of the numbers showing is 7. So we’ve got to change that sum of 7 to 0. Seems easy enough.
But what happens when we flip three adjacent coins? Because of how we’ve set them up, there are either two 1s up, one 1 up, or no 1s up.
Two 1s up —> [3-flip] —> No 1s up
One 1 up —> [3-flip] —> one 1 up
Zero 1s up —> [3-flip] —> two 1s up
This means that each 3-flip changes the total sum of numbers showing by adding or subtracting 2, or leaving the sum unchanged. In particular, none of these moves can change even sums to odd, or vice versa. So can we change the sum of 7 to a sum of 0? Never. It’s impossible to ever flip all the blue sides to red using only 3-flips.
For example, if we looked at just the 5 coins from the original example, [see image below]
they go from a sum of 3, to a sum of 1, to a sum of 1. Each 3-flip respects the parity—that is, the evenness—of the sum.
Try this argument out with 11 coins instead. It can work, but it requires you to relabel the coins slightly. This is often true with these kinds of labeling arguments: there are a lot of ways to label the coins that don’t prove anything, but the right labeling can prove everything. (In fact, I fooled around with lots of labeling arrangements that didn’t do anything before I found this one.)
Puzzle 2.
Moving from a line to a circle prevents our clever numbering argument from working. Here’s one way to solve the puzzle. Let’s number the 10 coins to keep track of them. Notice that in two moves you can flip over coins 1 and 4, and leave the rest unchanged. Repeat for 7 and 10, 3 and 6, 9 and 2, 5 and 8. That’s ten moves, and all the coins are now red!
Research question.
I claim that it’s possible to use 3-flips to change any number of coins in a circle from blue to red. Can you find a general method (or methods) that will work for any number of coins in a circle?
