Christos Tzamos
Email:
@mit.edu
tzamos
Phone:
9091739
(617)
Office:
32G630, Stata Center
Web:
christos.me
Google Scholar 
DBLP 
arXiv 
Github

A collection of the hardest puzzles and riddles that I know.
A prison warden is considering liberating one hundred prisoners if they successfully pass the following challenge. In one room in the prison, one hundred boxes are lined up in a row, each containing the name of one prisoner and every prisoner’s name appears exactly once. Each time a prisoner will be taken to the room and asked to open the boxes in any order he wishes until he finds his name. If the prisoner opens more than fifty boxes, all prisoners will immediately be executed, otherwise the game continues. Each time a prisoner succeeds in finding his name in no more than 50 attempts, the room is taken back to its original state and the prisoner is not allowed to return with the other prisoners, so he can’t communicate with them in any way, directly or indirectly. The prisoners have a few moments to decide on a strategy before the game starts. They know that if everyone chooses boxes at random, their chances of survival are almost zero, but there is a strategy giving them a 30% chance of survival, what is it?
A prison warden is considering liberating one hundred prisoners if they successfully pass the following challenge. Every prisoner will be forced to wear a hat without being able to look at its color. The hats are painted out of a selection of 100 different colors but some prisoners may get the same hat colors and some colors may not be used. Every prisoner will be asked to guess his hat color after seeing the hat colors of everyone else. However they are not allowed to communicate in any way and they can’t hear each other’s guesses. In order for the prisoners to win the game, there must be at least one of them that manages to guess his hat color correctly. They know that they will be executed in case they fail to pass the challenge, so the don’t want to risk at all. The prisoners have a few moments to decide on a strategy before the game starts. What strategy succeeds no matter what hat everyone gets?
A prison warden is considering liberating one hundred prisoners if they successfully pass the following challenge. In one room in the prison, there are two switches that are both initially off. Every day, some prisoner will be taken to the room and will be forced to change the state of exactly one of the switches. At any point in time, any prisoner may ask to end the game. If by that time, all prisoners have been in the room at least once, they will all be freed, otherwise they will all get executed. The prisoners have a few moments to decide on a strategy before the game starts but afterwards they will not be allowed to communicate in any way. What is a strategy that someday will allow a prisoner to be sure that the game has ended?
A prison warden is considering liberating two prisoners if they successfully pass the following challenge. The two prisoners will be given a positive integer less than 10^10. Prisoner A will then be taken in a room, where there are 200 boxes each containing a small stone and will be asked to select some boxes and empty them completely. Then Prisoner B will be taken in the same room where he can open any boxes he wishes to see if Prisoner A removed their content. Prisoner B will then have to answer whether the number he received originally is larger, smaller or equal to the number that prisoner A received. The difficulty is that the prisoners are not allowed to open more than 20 boxes altogether, i.e. If prisoner A opened 12 boxes then prisoner B will be allowed to open at most 8 boxes before he is forced to guess. The prisoners have a few moments to decide on a strategy before the game starts but afterwards they will not be allowed to communicate in any way. What is a strategy that will allow prisoner B to answer correctly?
A prison warden is considering liberating 1023 prisoners if they successfully pass the following challenge. The prisoners will be given a black/white hat chosen uniformly at random (and independent of the choices of all others). Each prisoner can see the hat color of all other people, but not his own. Each prisoner is asked if he wishes to guess his own hat color. He can either guess, or abstain. Each prisoner makes his choice without knowledge of what the others are doing. They either win collectively, or lose collectively. They win if everyone who doesn’t abstain guesses his hat color correctly and at least one does not abstain. They lose if everyone abstains, or if at least one prisoner guesses his hat color incorrectly. The prisoners have a few moments to decide on a strategy before the game starts. They know that they can win with probability 50% by just having only one person guess at random, but there is a strategy giving them at least 99.9% chance of survival, what is it?
You have a balance scale and 120 coins, 1 of which is counterfeit. The counterfeit weigh less or more than the other coins. Can you determine the counterfeit in 5 weightings, and tell if it is heavier or lighter?