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
    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

3

An obvious strategy would be to take all binary numbers of even weight. That already narrows it down to 8 numbers. But we can do better:

0000 1001 0111 1110 

This is optimal, since every guess covers 5 possibilities out of 16 in total, so we need at least $\lceil 16/5 \rceil = 4$.

For more on the subject, search for "covering codes" (distinct from the more commonplace error-correcting codes).

  • 1
    @Alka: And as you might expect, [here](http://en.wikipedia.org/wiki/Covering_code) is a place to start. It has a link to a bibliography listing almost 1000 items.2012-01-28
2

For a different way of looking at this,

Looks like you are looking for the minimum dominating set in a hypercube.

According to this survey (published in 1998, so newer results could be there) by Harary, when the number of bits $n$ is of the form $2^m - 1$, the answer you are looking for is $\dfrac{2^n}{n+1}$.

The question is apparently still open when $n$ is not of the form $2^m - 1$.

(See page 279 of the survey and the talk about node-node dominating number: $\alpha_{00}(Q_n)$)

Of course, there might be algorithms to compute it quickly for hypercubes, but for general graphs, this is known to be NP-Hard.