Flipping cards
A game is played with 16 cards laid out in a row. Each card has a black side and a red side, and initially the face-up sides of the cards alternate black and red with the leftmost card black-side-up. A move consists of taking a consecutive sequence of cards (possibly only containing 1 card) with the leftmost card black-side-up and the rest of the cards red-side-up, and flipping all those cards over. The game ends when a move can no longer be made. What is the maximum possible number of moves that can be made before the game ends?
This problem is from the OMO.
The answer is 43690.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Consider the colors of the cards as binary digits instead, letting the red side be 0 and the black side be 1 . Note that if we read the binary digits on the cards from left to right, the flipping sequence is equivalent to subtracting a power of 2 from the number. Because it is always possible to subtract 1 (take the rightmost black card and all the red cards to its right and flip), we can use up to the number of moves equal to the binary number at the beginning, which is 2 1 5 + 2 1 3 + . . . + 2 1 = 4 3 6 9 0 .