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

-
Are you supposed to enter a $*$, or does "$1{\hbox*}3$" mean that you may enter any of the numbers $103$, $113$, $\ldots$, $193$? – Christian Blatter Jan 29 '12 at 18:43
@StevenStadnicki: "de Bruijn sequence" – Ilmari Karonen Jan 29 '12 at 22:33
I 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. – Gerry Myerson Jan 29 '12 at 22:57
Gerry: 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. – Steven Stadnicki Jan 29 '12 at 23:27
This 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. – Steven Stadnicki Jan 29 '12 at 23:28

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.

-
In 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)... – Steven Stadnicki Jan 29 '12 at 21:13
@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! – AD. Jan 29 '12 at 21:25
I think this answer is based on a misunderstanding of the question. See my comment on the question. – Gerry Myerson Jan 29 '12 at 22:57

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 ?

-
What if the password were 100? When would it open? – DSM Jan 30 '12 at 2:26
This 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$). – TonyK Jan 30 '12 at 18:54

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.

-
You mention NP-complete. I do not think it means what you think it means. – Gerry Myerson Jan 29 '12 at 23:00
Perhaps 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. – MaxW Jan 30 '12 at 0:38
Sorry, 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. – Gerry Myerson Jan 30 '12 at 2:00
Gerry, 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. – MaxW Jan 30 '12 at 4:12
Sorry, that's not even close to what NP-complete means. Please, look it up, using some reputable source. – Gerry Myerson Jan 30 '12 at 5:09