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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Have not thought this through, but I think just testing every possible combination $n^m$ times in succession would work? $\endgroup$– Steven GubkinCommented Apr 24, 2014 at 20:19
-
1$\begingroup$ 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 $\endgroup$– Gerhard PasemanCommented Apr 24, 2014 at 20:47
-
$\begingroup$ 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. $\endgroup$– domotorpCommented Apr 25, 2014 at 4:16
-
$\begingroup$ Isn't this the basis of PRNG code? $\endgroup$– Carl WitthoftCommented Apr 25, 2014 at 12:36
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Apr 24, 2014 at 20:49
-
7$\begingroup$ 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. $\endgroup$– usulCommented Apr 24, 2014 at 21:37
-
2$\begingroup$ 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 $\endgroup$ Commented Apr 24, 2014 at 22:22
$\begingroup$
$\endgroup$
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$.
answered Apr 25, 2014 at 4:17
$\begingroup$
$\endgroup$
1
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
-
$\begingroup$ 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? $\endgroup$ Commented Apr 24, 2014 at 22:22