This is based on Matt Parker's Youtube Video
The card flip game is played by two players.
The first player will place n
(usually four) cards face down in a row and then
flip some of the cards face up.
The second player will now attempt to flip individual cards in order to make all the cards face down. However, the second player cannot see the cards, they can only describe which card to flip. (first on the left, second on the right etc.)
The game ends when all the cards are face down. The players may then swap roles and try to win in the least flips.
What is the minimum number of moves that the second player can make and be certain to win.
There are 2n - 1
initial configurations for the cards.
Each flip can only increase the number of checked configurations by 1. Therefore
the minimum number of flips must be at least 2n - 1
.
If it were smaller, there would be unchecked configurations, and by setting the initial configuration to one of these unchecked configurations the first player could ensure that the second player would not win within the smaller number of moves.
Consider this strategy for flipping cards:
On the nth flip, flip the (k + 1)th card, where k is the number of trailing zeros in the binary representation of n.
Turn | Turn2 | Flip |
---|---|---|
1 | 1 | 1 |
2 | 10 | 2 |
3 | 11 | 1 |
4 | 100 | 3 |
5 | 101 | 1 |
6 | 110 | 2 |
7 | 111 | 1 |
8 | 1000 | 4 |
There is a graph below and some numbers in a spreadsheet.
This strategy will ensure that after 2n - 1
flips, every
cobination of the n cards will have been checked.
The proof of this can be done by induction on n, noticing that if the last card
starts face down then the solution will be found within 2n-1 -
1
moves, and if it starts face up then the 2n-1
th
move will flip the last card (since 2n-1
has n - 1
trailing zeros). We can then find the solution within 2n-1 -
1
more moves, and 2n-1 + 2n-1 - 1 =
2n - 1
.
Therefore the second player can employ this strategy to win within
2n - 1
moves and there is no strategy to win in less
moves, so this is an optimal strategy.
Also this strategy doesn't take the total number of cards on the table into account when deciding which card to flip; in fact if the number of cards is not known by the second player, this strategy will still find the solution eventually!