Some Interesting Puzzles
A two - envelope puzzle
Consider the following game: You are shown two sealed envelopes, each containing a slip of paper on which is written a real number. These numbers are chosen from some distribution that you do not know. You are allowed to open one envelope and look at the number written inside. After that, you must choose one of the envelopes. The objective is to choose the envelope with the larger number. Obviously, choosing randomly will succeed 50% of the time. Can you devise a strategy that guarantees a probability of success that is strictly greater than 50%?
See solution
A two - egg puzzle
Suppose there is a building of height n floors, and that there is a maximum height, h, (in floors) from which an egg can be dropped without breaking. For simplicity, assume this value is constant for all eggs. You have two eggs with which to determine this height h. An egg dropped from height h or below will not break and can be reused, while an egg dropped from a height greater than h will break and cannot be reused. Determine, with proof, a strategy to minimize the maximum possible number of drops used to determine h. What is the minimax number of drops, d as a function of n?
See solution
Simulating Dice
This puzzle was inspired by a sample interview question I saw. The actual question could not be solved with a guarantee to run in fintie time (though this would happen with probability 1), but it got me thinking as to when it could be done.
Determine (with proof) necessary and sufficient conditions on a and b such that if I have a fair a-sided die (ignore whether one could be physically built) that I use use it to simulate a fair b-sided die via a finite process.
As an example, a fair 6-sided die could be used to simulate a fair 8-sided die as follows: Start with the number 1. Roll the 6-sided die. If the result is 4 or more, add 1 to your number, otherwise do nothing. Roll the 6-sided die again. This time if the result is 4 or more, add 2 to your number, otherwise do nothing. Finally, roll the 6-sided die one more time and if the result is 4 or more add 4 to your number, otherwise do nothing. Your number is now the result of a simulated roll of a fair 8-sided die.
See solution