There's a N (1 ≤ N ≤ 1 000; N is pair) digit binary number and you have a maximum of 2050 guesses to find out which is it. With each try, you will know one of the following:
Is it possible to find out the number with some formula before the guesses run out? How?
A modification of this easier question.
Start by guessing the following N digit numbers:
0000...00
1000...00
1100...00
1110...00
...
1111...11
One of these guesses must give us a 50% response because
every number in the sequence either increases or decreases the number of good digits by one. Either 0000...00 or 1111...11 has at least half of the digits right, while the other one has at most half of them right, so the sequence goes through the 50% mark somewhere.
If we have a 50% guess, all we have to do is
test every digit for whether its correctness is equivalent to that of the next one (both of them are right or both of them are wrong). We can do this by flipping the bits in adjacent pairs in the 50% guess. For example, if our initial 50% guess was 1111000000, we start by guessing 0011000000. If we get a 50% response again, we know that exactly one of the first two digits was right in 1111000000. If we don't, then either both were right or both were wrong. Next we guess 1001000000. Then 1100000000. Then 1110100000. And so on, all the way to 1111000011.
After this, there are only 2 possible values for the hidden number:
One is when we set the first digit to 1 and set all the other digits according to the relations we established in the previous N-1 steps. The other one is when the first digit is 0 (the complement of the previous number).
This was $(N+1)+(N-1)+2\le2002$ guesses in total.
Let's consider the worst case scenario - N=1000. The leading digit is of course 1. It can be done in 2 or 3 steps:
1. Start out by guessing 11...1. If you get all or none of it right, you win. If you get half the digits right, that means there are 500 zeroes and ones each. Otherwise, constantly turn the rightmost 1 into 0 until you get one of the three results. Every time you do that, the number of the correct digits increase or decrease by 1. If there should be more 0s than 1s, you start out getting less than half of the digits right and eventually end up with an equal number of correct and wrong digits (if you were to keep going, you'd have ended up with MORE than 500 correct places). The same outcome also happens if there are more 1s. Stop when you reach a number giving you a 50-50 result. Takes at most 999 moves.
2. If reversing the leading digit is allowed, reverse it along with one from a different place every time. In the next move, go back to the number obtained at the end of Step 1. Rinse and repeat. If you're still getting a 50-50 result, that means there was a wrong digit in the arbitrarily chosen place before the reversal. Otherwise, it was right. In this case, it takes 999 moves at most.
If the leading digit can't be reversed, then reverse the digits in two distinct places of this number at first. If you're still getting a 50-50 result, that means both of the chosen places can't be correct or wrong at the same time. Otherwise, both are either correct or wrong. Now keep choosing one of the two as a constant along with a different one of the rest every time. Go to Step 3. Takes 998 moves.
3. Take the constant from Step 2 as correct and make a guess accordingly. It's either a perfect guess or completely wrong. If the latter is the case, just reverse it. Takes at most 2 moves.
Which means this only takes 1999 moves (even 1998 if the leading digit can be reversed), so it's perfectly doable.
