password lock problem 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
 A: 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.
A: 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. 
A: 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 ?
