Solving a Secret List (Inspired by 'Are you the One?')
Let's say there's a list of the numbers $1$ through $N$ in some sequence, unknown to us. This list is the "correct" order. You are able to arrange those numbers in any way, and after each step you are told how many of the items on your list are in the correct position, but not which ones. The goal is to guess the order of the secret list in as few steps as possible. The 2 questions I've been thinking of are these:
- Is there a strategy that guarantees you find the correct order in $M<N!$ steps?
- Given a maximum number of guesses $G<M$, is there a strategy that maximizes your probability of finding the right order in $\leq G$ steps?
So far I haven't been able to make much headway. I though I could do something by keeping a fixed order and rotating it $N-2$ times, which would put every item in all but one spot once without double counting, and the $N-1$st could be deduced given the number of correct spaces would have to add up to $N$.
I don't think it gives useful information though. I imagine in order to find out which positions are correct you'd have to have that spot repeated at least once. Thoughts?
Great question! I have no idea.
What I came up with in the past 10 minutes is the following strategy, that (if my math is correct) guarantees finding the correct move in $O(N^3)$ moves. This answers your first question, but your second still remains.
To start, take any single sequence, and check how many numbers are in the correct spot. Now we keep the first number fixed, and rotate all other numbers in the sequence. We again note how many numbers are in the correct spot. We keep doing this for all the $N-1$ different rotations of all but the first number.
Now there are two possibilities: Either the sum of the correct counts equals $N-2$, or it equals $2N-2$.
In the first case, the first number in our sequence was not correct. That means that $N-2$ of the numbers after the first number reached their correct spot exactly once. The last of the $N-1$ numbers that was rotated was the number that should have been the first number of the hidden sequence, and therefore it didn't reach its correct position in this rotation.
In the second case, the first number was in the correct spot. It was therefore counted $N-1$ times, once after each rotation we did. The other $N-1$ elements of the sequence were all rotated once into the correct spot, so in total we should have $2N-2$ correct counts.
If we are in the second case, we have found the first number, and we can repeat this algorithm for the remaining $N-1$ numbers in the sequence. If we are in the first case, we choose another number to be at the front and repeat this algorithm again, hoping we have now chosen the correct number. Since we have $N$ different possible values for the beginning, so determining this first number should take at most $(N)(N-1)$ guesses: $N$ different starting numbers, and $N-1$ guesses per starting number. Since we have to do this for every length of the sequence we get that the maximum number of guesses necessary for this algorithm equals:
$$\sum_{n=2}^N (n)(n-1) = \sum_{n=2}^N n^2 - n = \frac{N(N+1)(N-1)}{3} \in O(N^3)$$
Example:
If our sequence is four digits long and the correct order would be 2314, we might try putting the 1 on front first. This would lead to the following counts:
$1234 \rightarrow 1$
$1423 \rightarrow 0$
$1342 \rightarrow 1$
Since $1 + 0 + 1 = 2 = N - 2$, we have found that $1$ is not the start of the hidden sequence. Let's now try with 2:
$2134 \rightarrow 2$
$2413 \rightarrow 2$
$2341 \rightarrow 2$
Since $2 + 2 + 2 = 6 = 2N - 2$, we have found that $2$ is indeed the first number of the hidden sequence. We now keep the 2 fixed, and check again for the part of the sequence consisting of the 1, 3 and 4.
We can find the correct listing in $O(N^2)$ moves. For any integer $i=1,\ldots,N$ let $b_i$ denote the integer that is supposed to be in the $i$-th position. Let $c$ denote the number of $i$ such that $a_i=b_i$.
Claim 1: Given 3 distinct integers $i_1,i_2,i_3$ we can determine in $O(1)$ queries precisely which if any of $i_1,i_2,i_3$ is $b_{i_1}$, which if any of $i_1,i_2, i_3$ is $b_{i_2}$, and if any of $i_1, i_2, i_3$ is $b_{i_3}$.
Let us now present our algorithm. We call an integer $i=1,2,\ldots, N$ certain if $b_i$ has been found. We call an integer $i$ uncertain if it is not certain. Let us write the set of integers that are uncertain as $U$. Initially $U=\{1,2,\ldots, N\}$. We now describe our algorithm.
Let $i_1$ be any integer in $U$. We make $i_1$ certain in $O(N)$ moves as follows:
Finding $b_{i_1}$ in $O(N)$ moves.
- For each $i \in U$ there may be an intermediate integer $a_i$ where $a_i$ may or may not be $i$.
- $U' \leftarrow U \setminus \{i_1\}$.
- WHILE $U'$ is nonempty and $i_1$ is still uncertain:
-
Let $i_2$ be another integer in $U'$, and remove from the set $U'$ the integer $i_2$.
-
Then check how $c$ changes when $a_{i_1}$ swaps positions with $a_{i_2}$.
-
If $c$ changes by 2 either way then either $a_{i_1}=b_{i_1}$ and $a_{i_2}=b_{i_2}$, or $a_{i_1}=b_{i_2}$ and $a_{i_2}=b_{i_1}$; either way $b_i$ was found for both $i=i_1$ and $i=i_2$ so remove both $i_1$ and $i_2$ from $U$.
-
If $c$ changes by 1 either way then $|U| \ge 3$ and one of $a_{i_1},a_{i_2}$ is $b_{i_1},b_{i_2}$. Let $i_3$ be a 3rd integer in $U$ and run Claim 1 to find precisely which if any of $a_{i_1},a_{i_2},a_{i_3}$ is $b_{i_1}$, which if any of $a_{i_1},a_{i_2},a_{i_3}$ is $b_{i_2}$, and if any of $a_{i_1},a_{i_2},a_{i_3}$ is $b_{i_3}$. For each $i \in \{i_1,i_2,i_3\}$ such that $b_i$ has not been found, reset $a_i$ to a remaining value of what was before $a_{i_1},a_{i_2},a_{i_3}$.
- Note that 2. take $O(|U|)$ moves. As there is an $i \in U$ such that $b_{i_1}=a_i$, the integer $i_1$ will become certain by the end of the steps 2--4 corresponding to $i$ being removed from $U'$ in step 1. If $i=i_1$ then swapping $a_{i_1}$ with $a_{i_2}$ where $i_2$ is the next smallest integer in $U$, will change $c$ by -1 or -2; if $i \not = i_1$ then $c$ will change by 1 or 2 when $a_{i_1}$ is swapped with $a_i$.