A hardware store sells an unusual combination lock that has six numbered buttons 1, 2, 3, 4, 5, 6 on its face along with a RESET button. To open the lock, a subset of these numbers must be pressed. The order in which the numbers is pressed is irrelevant and if the wrong subset is pressed, one may simply press RESET and start over.
Find a sequence of button-presses that is guaranteed to open the lock, provided you try the lock after each button is pressed. Try to come up with as short a sequence as possible.
For example, if the lock had only three buttons, then the following sequence is guaranteed to work, provided we test the lock after each press of a numbered button.
[R] 1 2 3 [R] 2 3 [R] 3 1 The initial R is necessary because we do not know the lock's state when we come across it. The first three passes test the subsets {1}, {1,2}, {1,2,3}; the next two test {2} and {2,3}, and the last two test {3} and {1,3}. Since the empty set can be checked at the beginning, this 10-sequence checks all eight potential combinations.
The question is asking for a short sequence guaranteed to work on a 6-button lock.
Source: John Guilford, Hewlett-Packard.© Copyright 2000 Stan Wagon. Reproduced with permission.