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!