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
3
$\begingroup$
probability
combinatorics
-
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