Five Card Trick

Source(s):

• This is well-known self-working card trick that I first discovered in the text Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh (exercise 2.20, where it is intended to be an example application of Hall’s Theorem).

The Problem

Alice and Bob are mathematicians who perform a trick at a dinner party. Bob leaves the room and a random volunteer shuffles a standard deck of cards.

Alice chooses 5 cards at random. She places 1 of the cards face down on a table and then leaves the other 4 cards face up.

Bob returns to the room. He inspects the 4 face up cards, and in virtually no time he calls out the value of the face down card.

The cards are not marked in any way and this trick is completely mathematical. Naturally Alice and Bob had prepared to perform the trick so they had a plan of what to do. Can you figure out how they did it?

Spoiler

Use the pigeon-hole principle. Note that Alice chooses both the card to be placed face down and the order of the other 4 cards.