0
    a. Alice thinks up an array of N binary numbers
    b. Bob guesses an array of N binary numbers
    c. Alice responds only with ONE number, 
       which is the number of binary numbers in the correct position

An alternative to this problem is that Bob is allowed to include ? or non binary numbers in his guess as he will know they can't possibly be right. Which may (or may not) resolve this game faster.

Another alternative, is that you have prior probability estimates for each binary digit. (An interesting specific case, as for example you can get distribution estimates with each guess, right?)

There are some papers on random oracles which is similar to this, but I haven't found anything specific or useful. Trying to prove an optimal alg for solving this problem. Ulam's problem looks close, but couldn't find anything close enough.

Here's sort of something, http://www.geometer.org/mathcircles/bitmaster.pdf

But no references and terminology / formalization is a little weak.

Blaze
  • 125
  • "Binary number" means a number (any number) written in binary notation. $1001011$ is a single binary number. Your description is unclear, but I'm guessing you actually mean an $N$-bit number, not an array of $N$ binary numbers. A bit ("binary digit") is either $0$ or $1$. If you actually mean an array of $N$ binary numbers, then calling them "binary" is pointless. They are just numbers, and it doesn't matter how you choose to write them down. – Paul Sinclair Jan 01 '22 at 22:10
  • See the linked paper for an example. It's pretty good – Blaze Jan 07 '22 at 09:08
  • See the points I made about your terminology being unclear in my comment. If you can't be bothered to clarify what you mean, don't expect others to spend time guessing. – Paul Sinclair Jan 07 '22 at 13:01

0 Answers0