There is a safe that can be opened by entering a secret code consisting of $n$ digits, each of them is $0$ or $1$. Initially, $n$ zeros were entered, and the safe is closed (so, all zeros is not the secret code). In one attempt, you can enter an arbitrary sequence of $n$ digits, each of them is $0$ or $1$. If the entered sequence matches the secret code, the safe will open. If the entered sequence matches the secret code in more positions than the previously entered sequence, you will hear a click. In any other cases the safe will remain locked and there will be no click. Find the smallest number of attempts that is sufficient to open the safe in all cases.
Problem
Source: IOM 2021 #5
Tags: combinatorics
IvoBucata
10.12.2021 18:53
Answer: $n$ The strategy is as follows: Assume that the correct sequence is $x_1x_2\cdots x_n$. On the first attempt we put $100\cdots 0$. If the case clicks, then we know for sure that $x_1=1$, and if it doesn't then $x_1=0$. Now that we know what $x_1$ is for sure, on the second attempt we put $x_1100\cdots 0$. Again, if the case clicks , then $x_2=1$ and otherwise $x_2=0$, so after $2$ moves we already know what $x_1$ and $x_2$ are for sure. Assume that after $k$ moves we know what $x_1$ to $x_k$ are. Then on the $k+1$-st move we put $x_1x_2\cdots x_k100\cdots 0$ and we find out what $x_{k+1}$ is. If the largest index that is $1$ is $j<n$, then after we put $x_1x_2\cdots x_{j-1}100\cdots 0$ the safe would open. Otherwise, on the $n$-th move we put $x_1x_2\cdots x_{n-1}1$ and we open the case. Now I'll show that we need at least $n$ moves to be sure that we open the case. Consider the set of the $2^n-1$ sequences of $n$ digits that are either $0$ or $1$. Define the term remaining sequences at a given time, as the subset of sequences out of those $2^n-1$ that still may turn out to be the secret code. Note that at any attempt, the subset of remaining sequences divides into two parts - the one that have more matches with the current attempt than with the previous one, and the ones that have no more matches with the current attempt than with the previous one. Note that, if the case doesn't click, the remaining sequences that have more matches with the current attempt than with the previous one are no longer part of the subset of remaining sequences, and if the case clicks , then the remaining sequences that have no more matches with the current attempt than with the previous one will no longer be remaining sequences. But note that we can't guarantee whether the case clicks or not, so if we have $x$ remaining sequences at some point, then after one attempt we can't get rid of more than $\lceil x \rceil$ of them. This tells us that if we have $2^n-1$ remaining sequences at the start, after $1$ attempt we can guarantee at least $2^{n-1}-1$, and so on, after $n-1$ moves at least $2^{n-(n-1)}-1 = 1$, thus we need $1$ more attempt to open the case, which makes up for a total of at least $n$.
YIFANK
10.12.2021 20:59
what is IOM?
Jalil_Huseynov
10.12.2021 23:29
International Olympiad of Metropolises
SnowPanda
26.01.2022 20:06
The answer is $n$.
Suppose that the secret code is $a_1a_2\cdots a_n$. For a construction, on step $k$ guess $a_1\cdots a_{k - 1}100\cdots 0$ (we'll show that this finds $a_k$ on step $k$, so it is possible to make this guess). Then changing the digit at spot $k - 1$ from $1$ to $a_{k - 1}$ either adds $0$ or $1$ to the number of matches, while changing the digit at spot $k$ from $0$ to $1$ subtracts $1$ if $a_k = 0$ and adds $1$ if $a_k = 1$. So $a_k = 1$ iff we hear a click, which means after step $k$ we know $a_k$. But if the last $1$ is $a_k$, then our guess at step $k$ was correct, so the safe opens within $n$ turns.
Now we show that $n - 1$ attempts is not sufficient to open the safe. Consider the set of codes compatible with all previous results (so the safe can choose any answer such that this set remains nonempty); at the start, there are $2^n - 1$ such codes. But if we have $m > 1$ such codes before an attempt, then of the $m - 1$ codes other than the one entered, either clicking or not clicking must be compatible with at least half of them. So the safe can choose an answer that results in at least $\tfrac{m - 1}{2}$ compatible codes remaining.
So then after $k$ turns, the safe can ensure that there are at least $2^{n - k} - 1$ compatible codes remaining (none of which have been chosen), which means we don't win in $n - 1$ turns.
IAmTheHazard
17.12.2023 23:05
The answer is $n$. For a construction, let the correct sequence be $d_1\ldots d_n$. On the $k$-th guess put $1$ in the $k$-th position and the known digits $d_1$ through $d_{k-1}$ in their respective positions. This allows us to deduce $d_k$, which will be $1$ iff the case clicks. For a bound: $n=1$ is trivial. For $n \geq 2$ if we only had $n-1$ guesses then it could be the case that our space of possible codes gets divided by at most $2$ in each turn, so after $n-1$ moves we have at least $\tfrac{2^n-1}{2^{n-1}}>1$ possible codes.