8
$\begingroup$

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:

  • You got it right (100%);
  • You got it exactly half right (50%);
  • That you didn't got any of the two above.

Is it possible to find out the number with some formula before the guesses run out? How?

A modification of this easier question.

$\endgroup$
  • 3
    $\begingroup$ What does "N is pair" mean? $\endgroup$ – Rand al'Thor Apr 1 '17 at 17:14
  • 1
    $\begingroup$ @randal'thor I'm guessing it means even. If N were odd, you wouldn't be able get exactly half of the digits right. $\endgroup$ – BaSzAt Apr 1 '17 at 17:27
  • $\begingroup$ I think "pair" is the French for "even" (in the mathematical sense of that word). $\endgroup$ – Gareth McCaughan Apr 3 '17 at 13:15
  • $\begingroup$ Do we need to figure out $N$ too, or would $000\ldots000$ count as guessing the number if the number was $00$? $\endgroup$ – Duncan Apr 4 '17 at 20:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How does your answer add to the essentially identical one already given? You should always look at existing answers before providing one of your own, to ensure you are not just adding a duplicate. (Also, please stop doing this. Rep-baiting by regurgitating others' answers is poor form.) $\endgroup$ – Rubio Apr 5 '17 at 2:31
  • $\begingroup$ "Rep-baiting by regurgitating others' answers is poor form." Are you accusing me of cheating? Stop with these false accusations. $\endgroup$ – Nautilus Apr 5 '17 at 5:35
  • $\begingroup$ Or are you implying I'm too dumb to answer any question without cheating? $\endgroup$ – Nautilus Apr 6 '17 at 9:50
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Incredibly minor optimization, but in the first step can't you skip a guess? You know one enumeration has to be 50%, so if you've guessed 000...000 through to 111...110 then you know that it has to be 111...111 and proceed thusly. Given that 111...111 would be fully correct, its probably even better to skip an earlier one (e.g. 111...101) - you either get it right when you guess 111...111, or you save a guess for the extended logic $\endgroup$ – crcroberts Apr 2 '17 at 22:00
  • $\begingroup$ @crcroberts Actually, you can skip two numbers from the enumeration. 111...111 is completely useless because if it's 50% right then so is 000...000. Then you can skip one more number and later deduce it by elimination. I didn't want to overcomplicate the answer though. $\endgroup$ – BaSzAt Apr 3 '17 at 6:39
  • $\begingroup$ Are we assuming that we know $N$? If so, I don't think this works as the problem implies that $N$ could be any even number from $2$ to $1000$. I suppose the real question is whether you have to figure out the number of digits as well - if the number is $00$ would guessing $000\ldots 0000$ match? $\endgroup$ – Duncan Apr 4 '17 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.