Least Overlap Combinations ``` Name: Daniel Status: other Grade: 12+ Country: United Kingdom Date: Fall 2011 ``` Question: Hello, I have an electric combination lock with buttons, the code is four digits long and uses digits from 0-9. My goal is to open the combination lock with the fewest possible presses of buttons on the lock (this is a physical lock with a telephone-button layout on the front, not a computer programme). The lock does not care if there are incorrect numbers pressed before the correct combination (for example, if the correct code was 1234, the lock would still open if I pressed 56781234). This creates an "overlap" when testing combinations. The example I gave before was as follows, by testing 1234 followed by 1235, meaning that I have pressed 12341235, and the lock would open if the correct combination was any of 1234, 2341, 3412, 4123 or 1235. One method of finding the combination would be for me to press every combination, beginning with 0000, then 0001, 0002, 0003 all the way to 9999. However, this is not very efficient (inefficent meaning that I am having a large amount of "overlapping" when testing combinations). What I am trying to obtain is a method of generating the shortest possible list of digits that I would enter into my lock in order to guarantee unlocking it. My question is, what is the most efficient way (least typing) to cover every combination from 0000 to 9999? Replies: Daniel, I do not have a specific answer for this question...just a comment: I cannot imagine a lock maker who would create a 4 digit lock where you can enter numbers in any order and the lock will open if the correct 4 digit list gets entered, even after entering a lot of incorrect numbers. In my view, a lock with 10,000 possible combinations would be considered quite safe as it would take some time and effort to accomplish opening the lock. The design described in the question describes a lock which in fact would be much less safe, as the combination could unknowingly be landed upon in less than the 10,000 set. I am not sure I understand why a lock maker would provide the illusion of safety with a 10,000 combination lock, and then thwart that safety with what I would call a design flaw. Shrug. Ric Rupnik Click here to return to the Mathematics Archives

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs