Puzzling Adventures: Safecracking; March 2003; Scientific American Magazine; by Dennis E. Shasha; 1 Page(s)
Imagine that you are a thief (but a big-hearted, Robin Hood type, of course). You must find the combination of a safe that has 10 switches, each of which can be put in three settings: low, middle or high. There are exactly 310 (59,049) possible combinations of switch settings. Fortunately for you, 38 (6,561) of the combinations will open the safe. The rule for opening the safe is simple: if two of the switches are in the right settings, all you have to do is pull the handle on the safe's door. The other eight switches are irrelevant. But you don't know which two switches are the crucial ones (they need not be adjacent).
Because there are so many opening combinations, choosing one randomly is a good strategy: for every nine tries, you are likely to hit one that will unlock the safe. But you are a very unlucky thief, so you want to devise a foolproof way to open the safe quickly. Can you guarantee unlocking it by trying fewer than 20 combinations of switch settings? And if so, which combinations should you try?