I would have thought this was well known, but I have not been able to track down a reference.
Suppose you are trying to guess an $n-$digit binary string. At any point you may guess all or any portion of it (a single specified digit if you like, or any specified collection of digits). Once you have made a guess, you will be told the number, though not the locations, of the correct entries in your guess. There is no penalty for wrong guesses, nor for unguessed positions. Let $a_n$ denote the maximal number of guesses it takes to determine the string under an optimal strategy (optimized, that is, to minimize the worst case). Stating the final result once it is determined does not count as a guess. Thus $a_1=1$ since a single guess determines a single digit string. It is not hard to see that $a_2=2$.
I'm after a description of the optimal strategy, along with the computation of $a_n$. Failing that, I'm interested in upper and lower bounds for $a_n$.
Discussion:
Simple observations: Since we can guess digit by digit, $a_n≤n$. It is also easy to see that $$a_n≤a_{n+1}≤a_n+1$$
Now, $a_3=2$. To see that, it suffices to exhibit a two step guessing strategy for $n=3$: First guess $111$. If the answer is $0$ or $3$ you are done. $1$ and $2$ are effectively the same, so let's say the answer was $1$. Then the string is one of $\{100, 010,001\}$. If you guess $10\_$ the answers will be $\{2,0,1\}$ respectively so the answer will determine the string.
We can use this to improve the upper bound. Working in blocks of length $3$ with a possible remainder we get $$a_{3n+i}≤2n+i\quad \text{for}\quad i\in \{0,1,2\}$$
I have not been able to improve on this bound, nor have I got a useful lower bound. I have no particular reason to imagine that this upper bound is optimal, nor anything to suggest that it can be improved.
The sequence of upper bounds $\{1,2,2,3,4,4,5,6,6\cdots\}$ is A004523 and that link associates the sequence with the optimal strategy for Static Mastermind which is a guessing game with some similarity to the desired game, but it is not obvious to me that the games are equivalent. here is an analysis of Static Mastermind which claims to yield that upper bound, though I have not yet studied it.
Is this game equivalent to Static Mastermind? is this "blocks of length $3$" strategy optimal? More broadly, is this game equivalent to some other, well documented, game?
