3
$\begingroup$

Here is a question I came up with and i have been pondering for a while. I could not come up with an adequate solution, so here I am, asking the forum!

Suppose you and I are playing a game. I think of a k-digit binary number, and you have a certain number of guesses to guess what it is. You write all your guesses on a piece of paper, and when you have guessed to your hearts contet, you show me the slip of paper. I tell you if any of your guesses were correct. The catch is, your guess can be 1 digit off and still be considered correct. For example, if k=4 and I am thinking of 1101, you could guess either 1101,1001,1111,1100, or 0101. My question is, what is the least number of guesses you need to write down to make sure you have properly guessed my number?

Now if k=4, then there are always 5 winning numbers out of 16 total numbers, so obviously choosing 12 numbers would always guarantee a win for you. But is there some optimal strategy of guessing so that you always can be sure that you have gotten my number in Fewer attempts? Thanks!

  • 0
    Are you allowed a leading $0$? Is $0101$ a possibility?2012-01-28
  • 0
    Ahhh I'm silly. Yes you are, I just edited2012-01-28
  • 0
    This game reminds me of Hamming error-correcting codes. If $k=2^n-1$, then I can always be sure to get your number in the minimum of $2^{k-n}$ guesses. I don't know the theory for other values of k, though.2012-01-28
  • 0
    Oh, hey. http://oeis.org/A081374 Is this what you're looking for?2012-01-28
  • 0
    Could you explain how to arrive at the answer for the cases of k=4 and k=5 (requiring 5 and 10 guesses)? Just to explain how to arrive at it? Thanks!2012-01-28
  • 0
    Huh - apparently my link isn't the right sequence, because the 4-guess answer below works out. Sorry about that! I'll keep looking.2012-01-28
  • 0
    Ah - here's the right sequence. http://oeis.org/A000983 According to the site, finding minimal codes is hard unless k is one less than a power of two, and has a lot of trial-and-error involved. Heck, the answer for k=10 isn't even known.2012-01-28

2 Answers 2