<blockquote>
  <p>00000<br>
  11110<br>
  01110<br>
  01111<br>
  10011<br>
  10101<br>
  11001  </p>
</blockquote>

CC BY-SA 3.0
2012-02-20T00:31:15.087Z
2012-02-20T00:36:30.650Z
2012-02-20T00:36:30.650Z
Peter Shor 
<p>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).</p>

<p>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. </p>

<p>My algorithm was very simple:</p>

<p>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. </p>

<p>5- Repeat it until reach the answer. </p>

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

<p>I wrote some program with Matlab too. </p>

<p>Regards
(Navid.Chaichi@gmail.com)</p>

CC BY-SA 3.0
2016-03-22T19:05:51.423Z
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
CC BY-SA 3.0
2012-07-10T09:16:28.573Z
2012-07-10T09:16:28.573Z
Navid Chaichi
<p>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!</p>

<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2012-02-19T13:07:19.073Z
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
CC BY-SA 3.0
2012-02-19T13:24:00.880Z
(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](http://www.sztaki.hu/~keri/codes/index.htm) 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
CC BY-SA 3.0
2012-02-20T01:52:45.417Z
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
CC BY-SA 3.0
2012-02-20T16:17:11.110Z
this problem seems to be connected to the theory of [hamming encodings](http://en.wikipedia.org/wiki/Hamming_code)...?
vzn
<co.combinatorics><it.information-theory><coding-theory>
Covering Codes with Game Theory Application
Alka
# Covering Codes with Game Theory Application

(Asked by: username_0 on 2012-02-19)

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?

**Tags:** co.combinatorics, it.information-theory, coding-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: (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](http://www.sztaki.hu/~keri/codes/index.htm) 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.  
> **username_3**: 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.  
> **username_4**: this problem seems to be connected to the theory of [hamming encodings](http://en.wikipedia.org/wiki/Hamming_code)...?  

---

## 2 answers

### Answer by username_5 on 2012-02-20. Score: 2

> 00000  
> 11110  
> 01110  
> 01111  
> 10011  
> 10101  
> 11001


---

### Answer by username_6 on 2012-07-10. Score: -2

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)

> **Comments:**
> **username_7**: 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.  

---

