Everyone face down

Here’s another puzzle from Matt Parker and you kind of have to go there and watch the video, I can’t really summarize it here in only a paragraph.

And my solution:

Start with a really simple version of the game: Two cards, not all face down, and we have to get them all face down. If I use o to mean a face up card and x for face down, then we have three initial possibilities:

ox
xo
oo

Having no information about the setup there’s no particular reason to choose one card over the other, so we can just arbitrarily flip the first card:

xx Winner!
oo
xo

At this point you either win, or you know the second card is face up. So flip that.

(won)
ox
xx Winner!

Now either you win, or you know the first card is now face up, so flip that.

(won)
xx Winner!
(won)

So with two cards initially, not all face down, you need up to three flips.

Now three cards, and I’ll show them like this:

xo x
ox x
oo x

xx o

xo o
ox o
oo o

Let’s suppose for the moment the last card is face down, the first three possibilities. Now we have to get the remaining two cards face down, and we know that takes up to three flips: first card, second card, first card.

But the last card could be face up. If so then we need to flip that card, and if the other two cards are face down — the fourth possibility — then we’re done. Otherwise we again need to get the remaining cards face down, requiring three flips.

Since we don’t know whether the last card is face up or not, we have to try all three of these possibilities. So flip first, second, first; then third; then first, second, first. We need up to seven flips.

Moving on to four cards, by the same reasoning, we need up to seven flips to either win or know that the fourth card is face up, one to flip the fourth card and see if that wins it, and if not, up to seven more flips, for a total of fifteen:

first, second, first; then third; then first, second, first
fourth
first, second, first; then third; then first, second, first

And clearly 31 for five cards, 63 for six cards, and so on: 2^n-1 flips for n card.

But all this might look familiar. Remember the Towers of Hanoi? The optimum strategy for moving four disks is to move them in this order:

first, second, first; then third; then first, second, first
fourth
first, second, first; then third; then first, second, first

That’s right… this game is just the Towers of Hanoi in disguise.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s