Heaven or Hell

After you die, you somehow appear in a mystical room with two doors and two keepers inside. One of the doors leads to Heaven and the other door leads to Hell. One of the keepers is always lying and the other keeper is always saying the truth. If you can ask one of the keepers whatever question you want (you don’t know which keeper is lying and which one is truthful), how can you find your way to Heaven?

You can point your finger to one of the two rooms and ask any of the keepers the question “If I ask the other keeper whether this room leads to Heaven, would he say YES?”. If the answer is NO, go through that door, if the answer is YES, go through the other one.

Crashing Light Bulbs

You are living in a 100-floor apartment block. You know that there is one floor in the block, such that if you drop a light bulb from there or anywhere higher, it will crash upon hitting the ground. If you drop a light bulb from any floor underneath it however, the light bulb will remain intact. If you have two light bulbs at your disposal, how many drop attempts do you need such that you can surely find which the floor in question is?

The answer is 14 drops. You can do this by throwing the first bulb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 (notice that the difference decreases always by 1) until it crashes and then start throwing the second bulb from the floors in between. For example, if the first bulb crashes at floor 69, you start throwing the second bulb from floors 61, 62, 63, etc. This way the total number of throws would be always at most 14.

Proving that 14 is optimal is done using the same logic. In order to use at most 13 throws, the first throw should be made from floor 13 or lower. The second throw should be made from floor 13+12 or lower, the third throw should be made from floor 13+12+11 or lower, etc. Continuing with the same argument, we conclude that the 13th drop should be made from floor 13+12+…+2+1=91 or lower. However, if the first light bulb does not crash after the last throw, you will not be able to find out which number among 92-100 is X.

9 balls, 1 defective

You have 9 balls, 8 of which have the same weight. The remaining one is defective and heavier than the rest. You can use a balance scale to compare weights in order to find which is the defective ball. How many measurements do you need so that you will be surely able to do it? What if you have 2000 balls?

First, we put 3 balls on the left side and 3 balls on the right side of the balance scale. If the scale tips to one side, then the defective ball is there. If not, the defective ball is among the remaining 3 balls. Once left with 3 balls only, we put one on each side of the scale. If the scale tips to one side, the defective ball is there. If not, the defective ball is the last remaining one. Clearly we can not find the defective ball with just one measurement, so the answer is 2.

If you had 2000 balls, then you would need 7 measurements. In general, if you have N balls, you would need to make at least log₃(N) tests to find the defective ball. The strategy is the same: keep splitting the group of remaining balls into 3 (as) equal (as possible) subgroups, discarding 2 of these subgroups after a measurement. To see that you need no less than log₃(N) tries, notice that initially there are N possibilities for the defective ball and every measurement can yield 3 outcomes. If every time you get the worst outcome, you will make at least log₃(N) tries.