Card Trick
Known elegant solution due to David Shin:
You may be familiar with the following card trick performed by a magician
and his assisant. A deck is shuffled and the assistant receives 5 random
cards from an N-card deck. The assistant then shows 4 of the 5 cards to
the magician and the magician must then guess the 5th without any chance of
error. Assume the
assistant is only allowed to choose two things: (1) which of the 5 cards to
keep hidden for the magician to guess, and (2) the permutation in which to
reveal the remaining 4 cards. A well-known strategy exists for N = 52
(try coming up with it). Find the largest N where a strategy to perform
the magic trick
exists, and show that there exists a strategy for this N which is simple to
implement (i.e. the magician and assistant could be expected to execute the
strategy efficiently from memory, without the aid of a computer).
Prisoners
Due to David Shin:
There are 4 prisoners in a jail. One day, the warden came up and said to them:
"I have set up a room with two buttons inside. One toggles between red and green as you push it, and the other toggles between black and white. I do not remember which state I last left the buttons in. Each day I will bring one of you 4 prisoners into that room where you will have to push exactly one button. Also, when brought into the room you have the option of claiming that all 4 prisoners have been in the room at least once at some point(s) in time. If your claim is right, I will release you all. Otherwise, I will kill you all."
"I will give you a few minutes before I begin this to discuss a strategy with each other."
What's a strategy the prisoners can come up with to assure that they are never killed and have some non-zero chance of eventually being released (assuming that the prisoner he takes into the room each day is randomly selected). E.g., the strategy of never guessing that all 4 prisoners have been in the room is not valid.
Pirates with Hats
Due to Alexey Radul:
An adversary assigns hat colors (red or green) to n people in any way he
wishes. The n people each must guess the colors of their own hats, and the
goal is to maximize the probability that *all* people make correct
guesses. The only information each person gets once hats are distributed
is the colors of the other n-1 hats they see. All answers must be given
simultaneously, so that guesses cannot be used to influence other guesses.
The hat distribution has already been decided, but the hats have not been
distributed yet. Before the hat distribution, the n people are allowed to speak
with each other to devise a strategy. Give a strategy which guarantees the
maximum probability of success, and prove
that it is the only optimal strategy.
Feel free to email me more riddles if you've got some good ones.