Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific ndigit 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?
closed as offtopic by Ryan Budney, Stefan Kohl, Chris Godsil, Boris Bukh, quid Apr 25 at 13:49This question appears to be offtopic. The users who voted to close gave this specific reason:



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. 


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} (11/N)^K \lt 1$. This holds when $K = N^3\log N$. 


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 

