# Covering Codes with Game Theory Application

Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. 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 5-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=5 and I am thinking of 11101, you could guess either 11101, 11100, 11111, 11001, 10101, or 01101. My question is, what is the least number of guesses you need to write down to make absolutely sure you have properly guessed my number with one of your guesses?

Now I have done some research and found that the answer is 7. In other words, you need to guess 7 numbers to make sure you have guessed my number. But I cannot find what these 7 numbers are! As such, I refuse to simply accept this answer. Furthermore, the answer could be 6 (since each number guess covers 6 possibilities, the absolute minimum number of guesses you need is 6 since 6x6=36>32). But obviously 6 is not the answer... is there a logical reason why?

• I like the topic and have though about related questions, but I think you have to make your question a little more focussed and more precise. – Markus Feb 19 '12 at 13:07
• (1) If I understand your post correctly, you found that the answer is 7, but you do not know a proof. How did you find out that the answer is 7? (2) The table by Gerzson Kéri cites Taussky and Todd 1948, but I do not have the access to the paper. (3) I personally think that the “game theory application” in this question is rather confusing; it is just the definition of covering codes stated in an awkward way and does not seem to provide any insight. – Tsuyoshi Ito Feb 19 '12 at 13:24
• You can easily use a computer to verify that 6 is not enough. A naive brute-force approach is fast enough for these values of the parameters. – Jukka Suomela Feb 20 '12 at 1:52
• this problem seems to be connected to the theory of hamming encodings...? – vzn Feb 20 '12 at 16:17

00000
11110
01110
01111
10011
10101
11001

If you consider 7 binary questions, then covering codes with radius one, is 16 number, (and it is the minimum one, because every answer will cover 8, and with 16 number of answers we will reach 16*8=128).

I was pondering the same, when I was 18 years old, in 1999, and I wrote a program with Q-Basic to find the solution, I wrote not in a proper way, but I got the result, The concept of program was simple but for CPU to solve and find the answer was time consuming.

My algorithm was very simple:

1- creating space for all possibilities (128) 2- selecting 16 member of this 128, and consider it as a group. 3- checking all 128 possibilities in this group, 4- if find a code that could not be covered by the selected group, then select another group with 16 member.

5- Repeat it until reach the answer.

when I went to university I research about it, and I found scientists are calling them as covering codes, recently I extent my program in many different algorithms to find the result for different combinations, ( many questions not only Boolean answers, maybe 4 or 5 choices per answer ).

I wrote some program with Matlab too.

Regards (Navid.Chaichi@gmail.com)

• Some covering codes mod 3, including the perfect ternary Golay code, were discovered by amateurs playing "football pools" where 0 means draw, 1 means home win, 2 means away win. – kodlu Mar 22 '16 at 19:05