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
-
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.
-
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 ?
-
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.
-
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