Hosted by The Math Forum


Problem of the Week 901

Efficient Lock-Breaking

_____________________________________________
Spring 2000 Archive || MacPOW Home || Math Forum POWs || Search MacPOW
_____________________________________________

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.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

25 January 2000