Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Are you allowed a leading $0$? Is $0101$ a possibility? –  Henry Jan 28 '12 at 17:34
    
Ahhh I'm silly. Yes you are, I just edited –  Alka Jan 28 '12 at 17:38
    
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. –  Lopsy Jan 28 '12 at 17:48
    
Oh, hey. oeis.org/A081374 Is this what you're looking for? –  Lopsy Jan 28 '12 at 17:51
    
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! –  Alka Jan 28 '12 at 17:54

2 Answers 2

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

share|improve this answer
    
So then for k=5, we would ned at least 32/5=6.4=7 numbers. Are there 7 numbers that cover all cases? –  Alka Jan 28 '12 at 18:00
1  
@Alka: And as you might expect, here is a place to start. It has a link to a bibliography listing almost 1000 items. –  Brian M. Scott Jan 28 '12 at 18:06

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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