There is a lock with the password between 000-999. But we could use only two digits to open the lock. For example, if the password is 123, the lock is open when you try 1*3, or *23, or 12*. questions: a) compose a strategy that the try number of opening the lock is the smallest one under the worst situation b) Prove that your strategy is optimal
password lock problem
-
0Repeats are not allowed? – 2012-01-29
-
2Are you supposed to enter a $*$, or does "$1{\hbox*}3$" mean that you may enter any of the numbers $103$, $113$, $\ldots$, $193$? – 2012-01-29
-
0I would say 100 tests would do it, but sure we need to put a tedious argument behind that. (Added the combinatorial tag - at this moment I can not see why to use the probability tag, why?) – 2012-01-29
-
0This problem gets really interesting if any stream of consecutive correct digits breaks the lock - these sequences have been well-studied without wildcards (I'm blanking on the name, but they're in _The Art Of Computer Programming) , but I've never seen the wildcard version of the problem mentioned. – 2012-01-29
-
2@StevenStadnicki: "[de Bruijn sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence)" – 2012-01-29
-
2I think the discussion, and the answers already given, misinterpret the problem. The way I understand it, if you input 123, that will open the lock if the actual password is any of 023, 123, 223, ..., 923, 103, 113, ..., 193, 120, 121, ..., 129. So one input covers 30 passwords. So you need at least 34 tries in the worst case, but surely you need more since there will be overlap between different tries. – 2012-01-29
-
1Gerry: I see exactly what you mean - and that's also a fascinating question! Note that you actually need more than 34 - each input only covers 28 passwords, because the next number in your second ellipsis is '123' and it also appears in the third ellipsis! The minimum number is at least 36, and as you say it's likely higher; this feels like a coding theory problem. – 2012-01-29
-
1This is the point at which we really need John to come back and clarify his question, but unfortunately I suspect that won't happen - the way the Q is phrased has more the feel of a puzzle being posed than of a question he's legitimately interested in having answered. – 2012-01-29
-
0@Steven, thanks for catching my mistake. And coding theory is exactly right. – 2012-01-30
-
0@GerryMyerson When looking at your interpretation of the problem I think the question needs an overview by OP. – 2012-01-30
4 Answers
Assuming Gerry Myerson's interpretation of the question (see comments to OP), the answer is somewhere between 36 and 64. For 36, see Steven Stadnicki's comment to the OP. For 64:
000 (28) 111 (28) 222 (28) 333 (28) 444 (28)
555 (28) 666 (28) 777 (28) 888 (28) 999 (28)
012 (22) 021 (22) 102 (22) 120 (22) 201 (22)
210 (22) 345 (22) 354 (22) 435 (22) 453 (22)
534 (22) 543 (22) 678 (22) 687 (22) 768 (22)
786 (22) 867 (22) 876 (22) 039 (14) 093 (14)
309 (14) 390 (14) 903 (14) 930 (14) 149 (12)
194 (12) 419 (12) 491 (12) 914 (12) 941 (12)
256 (10) 265 (10) 526 (10) 562 (10) 625 (10)
652 (10) 004 (6) 040 (6) 113 (6) 131 (6)
227 (6) 228 (6) 272 (6) 282 (6) 311 (6)
400 (6) 557 (6) 558 (6) 575 (6) 585 (6)
722 (6) 755 (6) 822 (6) 855 (6)
Three-digit numbers are codes to try. Numbers in parentheses are the number of uncracked passwords that the three-digit code will crack. So, for instance, 491 (12) means that 491 will crack twelve passwords not cracked by earlier numbers in the list (read in the order 000, 111 etc.).
This table was generated by a simple greedy algorithm: at every step, try the code that will crack the greatest number of uncracked passwords. No claim for optimality is made.
Edited to add: I ran the same algorithm for four-digit numbers, and the number of codes required was 570.
Algorithm:
100 tests are sufficient
1. 00*
2. 01*
3. 02*
...
9. 08*
10. 09*
11. 10*
...
90. 89*
91. 90*
...
99. 98*
100. 99*
My guess is that this can not be improved (if we are to be certain about finding the pw).
Edit: It can not be improved, see the comments below.
-
1In fact, it's easy to prove that this cannot be improved (assuming that each password has to be tried discretely). There are 1000 total passwords and each 'wildcarded' digitset can only cover 10 of them, so 100 are clearly necessary. The case where we can try a continuous string of digits and any matching 3-digit combination works (so that, for instance, entering 12*45 would successfully match 128, 254 and 645) is much more interesting (and challenging)... – 2012-01-29
-
0@StevenStadnicki Yes you are right. When one thinks about it: If one change the test method to say 2*1 at some point one would reach a point of "double testing" certain numbers. Hence mixing the methods would not be better and since in the above example 995 is a possibility it is not possible to do better. Thanks! – 2012-01-29
-
3I think this answer is based on a misunderstanding of the question. See my comment on the question. – 2012-01-29
What I think is a strategy like this:
0 1 X (X=0,1...9) - 10 times
2 3 X (X=2,3...9) - 8 times
4 5 X (X=4,5...9) - 6 times
6 7 X (X=6,7,8,9) - 4 times
8 9 X (X=8,9) - 2 times
This strategy could cover all digits combinations, including the duplicated digit password. So the total number is : 10+8+6+4+2=30
But have no idea of proving this is Optimal ?
-
4What if the password were 100? When would it open? – 2012-01-30
-
0This can't possibly be right, because each try can only cover 28 possibilities (see Steven Stadnicki's comments to the OP). So at least 36 tries are needed (because $28 \times 35 < 1000$). – 2012-01-30
Assuming: (1) The lock requires a 3 digit key to open.
(2) Each of three positions can either be a digit (0-9) or an *
(3) The lock is cryptographically secure except for a crib for the 3 digit cipher in that one digit can be replaced by an "*".
(4) Each guess takes the same out effort/time (whatever we're optimizing...)
For 3 digits in the password, then 10^3 guesses would be required.
However the crib using the * reduces the key complexity by one digit. 2 digits is 100 permutations which generates sequence from 00 to 99.
But each sequence has to be tested three times. So 12 gets tested as 12*, 1*2, and *12.
99 digit sequences and 3 different positions for the * in each of the 100 digit permutation makes 300 permutations total.
Therefore 300 is the minimum number of permutations to test to insure opening the lock. In any individual case the expectation would be to try half.
edited wording to remove reference to NP-complete.
edited
Ok, I got so wrapped up in discussion about NP completeness that I blew by TonyK's remark that 100 tries is enough. Obviously that is right. Since the * works in any position, just leave it in the third digit and do permutations of first two. You get the solution AD provided earlier.
-
0You mention NP-complete. I do not think it means what you think it means. – 2012-01-29
-
0Perhaps not. For instance the manufacturer of he lock could have an algorithm which takes the serial number of the lock and calculates the combination. Here to me being NP-Complete just means that if 1*3 doesn't work, then I have no information about the other 299 possibilities. They are all still equally probable. I can try 298 out of the 300 and the odds are still 50/50 which of the last two combinations will work. – 2012-01-30
-
5Sorry, you are not allowed to have your own meaning for terms like "NP-complete", terms that already have a well-established meaning in the community. That way lies chaos, the end of all meaningful communication. – 2012-01-30
-
0Gerry, your point is correct. NP-complete means that the solution space increases non-polynomially which is true in this case. Given that there are 10 possibilities for position in a combination lock using n digits, the possible number of combinations is 10^n which is non-polynomial. The individual combinations don't reveal any information about other permutations so you have to spin through all of them. Hope that clears up any discrepancy. – 2012-01-30
-
3Sorry, that's not even close to what NP-complete means. Please, look it up, using some reputable source. – 2012-01-30
-
0Gerry, help me learn something. He wanted "proof." Would have it been better to "assume" that the problem was NP-complete? Meaning that a deterministic algorithm would have to be used to formulate each possible combination, and that it would take the same amount of time to check each possible combination? The idea was to succinctly preclude something like using serial number to hash combination or listen for tumblers in each digit position. – 2012-01-30
-
0Your answer is wrong (100 tries is obvioulsy enough), and your nonsense about NP-completeness is worse. But we're only allowed one downvote :-/ – 2012-01-30
-
0As far as having to try every combination I guess was overthinkingg problem. See: http://www.metacafe.com/watch/480206/open_any_bike_lock_in_30_seconds_or_less/ So I'd now guess that 30 is enough. – 2012-01-30
-
0Aww Max, you're just trying to wind us up, aren't you? – 2012-01-30
-
0No, I really was trying to be serious. I tried to invoke NP-completeness to "prove" that the solution outlined was "optimal." My thought was that this was an electronic keypad with an "*." So perhaps a design flaw let you type * instead of a digit. – 2012-01-30
-
0@MaxW, why do you persist in using a term you do not understand, after your lack of understanding has been pointed out to you repeatedly? Please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please please go look it up, and don't use it again until you actually understand it. – 2012-01-30
-
0@Gerry: Calm down. Like I said, Max is just trying to wind us up. Rather skilfully, it seems :-) – 2012-01-30
-
0Isn't breaking a secure cryptographic system a NP-complete problem? – 2012-01-31
-
0"Secure" of course being the crux of the matter. A secure system would provide no useful information on a wrong guess. If there was useful feedback them instead of needing exponential time to find key, I might be able to use the feedback to create a polynomial algorithm. So the dial bike lock let's you find the first digit independent of the settings of the rest of the digits. Hence the method to crack the lock is faster than a brute force search. Thus the cracking method is "optimal." – 2012-01-31
-
0@TonyK, I think I will take your advice. – 2012-01-31
-
0I wasn't trying to be cantankerous. It took me a while to recast my thought as "cryptographically secure." I thought that the assumptions about being (1) cryptographically secure and (2) taking same time/effort to check each solution were implicit in saying that the lock problem was NP-complete. Assuming that these assumptions are valid, I would really appreciate anyone explaining why the problem wouldn’t then be NP-complete. – 2012-01-31