Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new key = f(current key, wrong key). Is there an algorithm (deterministic or not) which can surely find the key in finite time? Also, does this problem has a name?

share|improve this question

closed as off-topic by Ryan Budney, Stefan Kohl, Chris Godsil, Boris Bukh, quid Apr 25 at 13:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ryan Budney, Stefan Kohl, Chris Godsil, Boris Bukh
If this question can be reworded to fit the rules in the help center, please edit the question.

    
Have not thought this through, but I think just testing every possible combination $n^m$ times in succession would work? –  Steven Gubkin Apr 24 at 20:19
1  
Not if f(current key, wrong key) = wrong key + d for an obscure value of d. Gerhard "Prefers Using Liquid Nitrogen Instead" Paseman, 2014.04.24 –  Gerhard Paseman Apr 24 at 20:47
    
This problem is almost the same as the one where you have to find your way out from an unknown labyrinth for which the solution has the same trick as the one in Per's answer. –  domotorp Apr 25 at 4:16
    
Isn't this the basis of PRNG code? –  Carl Witthoft Apr 25 at 12:36

3 Answers 3

There are only a finite number of keys. Hence, there are only a finite number of functions that maps $keys \times keys \to keys$.

You will surely break the lock if you know function, and key. Hence, you can break the lock in finite time, by "trying" all functions and keys.

By this, I mean the following process: We can pretend that we have as many boxes as functions, and we try to break each "virtual" box separately. Now, during the process, we stop breaking boxes where the behaviour differs from the real box. Eventually, we will have a single candidate.

share|improve this answer
7  
I think this works, but could be made a bit more clear/precise. We start with a list of all pairs (function, initial key). We begin by entering the key that would cause the first pair to open. If it does, done. If not, we know the state that the second pair on our list would be in. We enter the key that would cause it to open. If it does, done. If not, we know the state that the third pair would be in, etc. I guess this takes at most $m^n \cdot (m^n)^{m^n \cdot m^n}$ steps. –  usul Apr 24 at 21:37
2  
It should be quite a bit less than that. Trying key a and then key b without getting an unlock potentially eliminates functions which have f(u,a)=b for some u. Although you don't know which functions those are, after about m^(n^2) tries you should have enough information to eliminate a large swath of functions (though much less than 1%). Gerhard "Little Quicker Than Hydra Killing" Paseman, 2014.04.24 –  Gerhard Paseman Apr 24 at 22:22

Let $N=m^n$, the number of possible keys. I will use usul's idea in a comment to show that it can be solved in at most $N^3\log N$ guesses.

Make a variable $s[F,s_0]$ for each possible function $F$ and state $s_0$. The number of variables is initially $N^{1+N^2}$. The value of $s[F,s_0]$ is a state, initially $s_0$, and in general it equals the state we would be in now if the function is $F$, the initial state was $s_0$, and we made the guesses we have made so far. Variables can be erased as we work.

Now we start guessing, but we do it greedily. Namely, at each step we try a state $s$ that is the most common value of the remaining variables. If it works, we are done. If it doesn't work, we can erase all the variables which have value $s$ and update all the others. At each step this eliminates at least the fraction $1/N$ of the variables. So we are definitely finished after $K$ guesses if $ N^{1+N^2} (1-1/N)^K \lt 1$. This holds when $K = N^3\log N$.

share|improve this answer

I see the whole picture as a graph, where each possible combination is a node.

Proposition: this graph is connecteced.

This is because, as there is no restrictions as how to change the combination (how many numbers can be changed at once), every combination can take to any of the other possible ones.

At each time step, there is the right combination. It is also a node on this graph. Imagine that this node is blue.

What happens is that the "blue node" may change at each combination tried.

But, as the problem is deterministic, there must be a path on this graph that reaches the blue node at some point.

"proof": Suppose you are on node 'n1', and the blue node is 'n17'.

In this case, you can solve the problem in two ways:

a. either you guess the correct answer right away

b. you make the wrong guess and the blue node moves. in this case:

b.1. you can go back to 'n1' (what is possible, according to the proposition)

b.2. the answer is again 'n17' (because it is deterministic*)

b.3. repeat b.1. -> b.2. untill you reach 'n17'

* here I am using the fact (?) that the change is deterministic in "both ways"

At each time step, the answer is at a distance of 1 edge (because the graph is connected). In this case, you can start trying to reach the answer at any of the nodes

Nevertheless, I am making some (strong?) assumptions:

i. there is some kind of mechanism to record the keys that were already tried, so not to try them again

ii. there is some kind of mechanism to record one key to be able to go back to it and continue the guessing process

share|improve this answer
    
It might not be connected, I think, but I do not follow your definition. What if $f(x)$ always return the new key 1111...1? Does this still make your graph connected? –  Per Alexandersson Apr 24 at 22:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.