Skip to content

Instantly share code, notes, and snippets.

@chrismilson
Last active April 16, 2020 05:29
Show Gist options
  • Save chrismilson/dc863a936fe8b48478e25a66f0aac101 to your computer and use it in GitHub Desktop.
Save chrismilson/dc863a936fe8b48478e25a66f0aac101 to your computer and use it in GitHub Desktop.
Matt Parker's Card Flip Game

This is based on Matt Parker's Youtube Video

Card Flip Game

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.

Problem

What is the minimum number of moves that the second player can make and be certain to win.

Solution

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-1th 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!

from random import randint
class Card:
"""
Represents a card on the table which is either face up or face down.
"""
def __init__(self, initialState=False):
self._state = initialState
def flip(self):
"""
Flips the card.
"""
self._state = not self._state
def __bool__(self):
"""
The card is truthy if it is face up, and falsy if it is face down.
"""
return self._state
def __str__(self): return 'up' if self._state else 'down'
class FlipCard:
"""
Represents a game of flip card.
"""
def __init__(self, numCards=4):
# At least one, and perhaps more could be face up.
configuration = randint(1, 2**numCards - 1)
self._cards = [Card(bool(configuration >> i & 1)) for i in range(numCards)]
def flip(self, i):
"""
Flips the ith card from the left starting from 0.
"""
self._cards[i].flip()
def __bool__(self):
"""
The game is only truthy when all cards are face down
"""
return all(not card for card in self._cards)
def __str__(self): return ' '.join(map(str, self._cards))
from cards import FlipCard
from math import log2
def flipIndex(t):
"""
Returns the index to flip given the try number.
"""
# t & ~(t - 1) is just t with all **but** the last 1, set to 0.
return int(log2(t & ~(t - 1)))
def playGame(n):
"""
Plays a game of "flip card" with n cards and tries to win within 2^n moves.
"""
game = FlipCard(n)
maxTries = 2**n
tries = 0
while not game and tries < maxTries:
tries += 1
f = flipIndex(tries)
# flip card f
game.flip(f)
if game:
# Solution found!
return True
else:
# Oh dear... Solution not found.
return False
if playGame(4):
print('We Won!')
else:
print('We lost....')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment