A Solution to Ulam's Problem with Error-correcting Codes
by Justin Montague
Dedicated to the memory of Ivan Niven.
 

Abstract: Suppose two people are playing a guessing game with numbers. One person thinks of a number between 1 and 1,000,000, and the other person must determine the unknown number by asking only yes-or-no questions. Clearly, this game will not prove too difficult for the Questioner. He only needs to halve the set containing the unknown number with each question, e.g., Is the number between 1 and 500,000? Now let us suppose the second person may lie to one of the questions asked him. The problem is to determine a strategy which yields the least number of questions needed to determine the unknown number.
Error-correcting codes - specifically Hamming Codes - will be used to construct such a strategy. The strategy given does not depend on feedback from the Responder and lends itself to quick decoding. While the solution using codes for the most part agrees with answers previously calculated, it sometimes requires one extra question. This discrepancy, however, is outweighed by the simplicity and speed of the solution.

This paper constitutes part of my honors thesis written in spring 1999 at the USNA, advisor Assoc Prof. David Joyner.

Introduction

In his 1976 autobiography Adventures of a Mathematician, Stanislaw Ulam [U] poses the following problem:
Someone thinks of a number between one and one million (which is just less than 220). Another person is allowed to ask up to twenty questions, to which the first person is supposed to answer only yes or no. Obviously, the number can be guessed by asking first: Is the number in the first half-million? and then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally, the number is obtained in less than log2(1000000). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer?

A problem of a similar sort can also be found in Elwyn Berlekamp's 1964 PhD thesis for MIT [B]. Since then, several papers have been published containing solutions to this problem and some of its variations. These solutions, however, were laden with complicated accounting and required feedback in between questions.

This paper approaches Ulam's problem from a different field of mathematics - Coding Theory. In general, we are concerned with transmitting information (which may or may not be erroneous) between two persons. If it is erroneous, we need an efficient method of detection and correction. The late Ivan Niven authored a paper in 1988 [N] that gave a solution to Ulam's Problem using error-correcting codes. While his idea was sound, the paper contained a few errors, and thus the problem remains unsolved. (In [N], the decoding algorithm at the bottom of page 277 and the corresponding argument on page 279 (below Equation 15) are both incorrect.)

Now we describe briefly the contents of this thesis. The solution contained in this paper utilizes Hamming codes along with the necessary corrections to Niven's idea to solve Ulam's problem with one lie. This work is not found in the literature. The strategy is simple, requires no feedback from the other player, and is easily generalized to the case where the number may be chosen from the set 1 to M. Furthermore, some simple examples, a discussion of problem variations, and a comparison to another ``feedback'' solution are included. In section 4, we define a new class of codes called circle codes which have a very simple decoding algorithm, although they are not as efficient as Hamming Codes. In section 8, we give a new result concerning the case of the Pathological Liar (where the number of lies is variable). The remaining sections contain background material. The paper closes with two appendices, one a table of known A(n,d) values, the other a table of Maple calculations comparing our formula for g( M,1) with Pelc's formula for
f( M,1).

Definitions and Notation

For Ulam's game, let Player 1 choose the number from the set of integers 1 to Mand Player 2 ask the questions to deduce the number. Player 1 and Player 2 are sometimes referred to as the Responder and the Questioner, respectively. If Player 2 structures his questions based on previous answers, we say he is using feedback. In this case, let f(M,e) denote the minimum number of ``yes/no'' questions needed to deduce the unknown number if Player 1 can lie at most e times. If feedback is not allowed, then the minimum number of questions is g(M, e). This case is equivalent to saying that all questions are determined before the game begins. Obviously, f(M,e)<= g(M,e).

For a given integer n>0 , a  binary code is a set C of n-tuples of 0's and 1's. The set  C can also be defined as a subset of F2n, the n-dimensional vector space over the integers mod 2. A codeword is an element of  C.

The weight of a vector or n-tuple v , denoted by wt(v), is the number of non-zero components in  v. The  minimum distance of a code C, denoted by d, is the minimum weight of
v- v', where  v, v' in  C.

The  length of a code is the number of binary bits in a codeword. The  dimension of a linear code is the dimension as a vector space over F2 , which is equal to the number of information carrying bits. A code  C of length n and minimum distance d is  perfect  if all the vectors in F2n are contained in spheres of radius  t = [ (d-1)/2] about the codewords of  C. A sphere of radius  t about a codeword would contain all vectors of equal length that differ from the codeword in at most  t places. In other
words, the spheres of radius  t completely cover the space. Perfect codes can detect and correct patterns of  t or fewer errors.

The Hamming Code is a perfect, single error-correcting binary code with minimum weight 3. The Hamming Code has length n and dimension  k, where

n=2r-1 and k=2r- r-1 for positive integers r>= 3.
The parameter r refers to the number of parity check bits on the end of each codeword. Obviously, n- k= r. These parameters generate a family of Hamming Codes, where distinct members are labeled as ( n, k,3)-Hamming codes.

Let A( n, d) denote the size of the largest possible binary code of minimum distance d and length n. If we fix M and e, the two parameters of Ulam's problem, then g(M,e) is the smallest n such that {\it A}(n,2e+1) >=  M. It is a known fact that if a code C is e-error correcting, then | C| <= A(n,2e+1). Finding  A(n,d) for every  n and d is perhaps the central problem in Coding Theory today, and is mostly unsolved (see table in Appendix A).

A Simple Problem

Let us first look at a simpler version of Ulam's game. As before, we havetwo players, and Player 1 must choose a number between 0 and 15, inclusive. Player 2 must discern which number Player 1 picked with a minimum number of
questions, and Player 1 is allowed to lie at most once. To solve this problem - and thus win the game - we will use a code generated by a three-circle Venn Diagram. The diagram should be drawn with regions labeled as in Figure 1.

 
 

From Figure 1, we can see that this code has length 7. The spaces labeled 1 through 4 will contain the information bits. This coincides with the fact that it takes a binary 4-tuple to represent all numbers from 0 to 15. Spaces 5, 6, and 7 will contain the parity check bits. The code generated by this diagram has codewords of the form

b1b2b3b4b5b6b7,
where b _{i} is the number in the i-th space of the diagram. To complete our construction of this code, we define the parity check bits in this way:
b5=b1+b3+b4,
b6=b1+b2+b4,
b7=b1+b2+b3.

Next, Player 1 has to convert his number to binary and encode it as a three-circle codeword. A table containing all 16 codewords is included at the end of this section for reference. Player 2 then asks seven questions of the form, ``Is the i-th bit of your 7-tuple a 1?'' Player 1's answers form the new 7-tuple,

c1c2c3c4c5c6c7

If Player 1 was completely truthful, then the codeword's parity conditions hold. This means that the 7-tuple generated by Player 2's questions will match a 7-tuple from Table 1. At this point, Player 2 just has to decode his 7-tuple to win the game. A single lie, however, will yield a 7-tuple unlike any in Table 1. If this is the case, Player 2 must error-check the received codeword using the three parity check bits. In other words, Player 2 needs to find all existing parity failures in the received codeword. A parity failure occurs when a parity check bit does not agree with its corresponding sum. Once Player 2 determines the position of the erroneous bit, he corrects it by changing its value. Decoding the corrected codeword will yield Player 1's original number.

An example here will help to illustrate what is actually happening. Suppose the answers to Player 2's questions produced the 7-tuple 0111101. Since this codeword is not in Table 1, we may deduce that Player 1 lied in answering one of the questions. Next we notice that the 5th and 7th bits fail their respective parity checks. Since c3 is the only bit common to the parity sums for c5 and c7, it must be the erroneous bit. This means that Player 1 lied to the third question, and his actual number is the 7-tuple 0101101 which decodes to 5.

The algorithm for error-detection and correction is not difficult. The erroneous bit is determined by which check bit - or combination of check bits - fails parity. If a single check bit fails parity, then that check bit is the erroneous bit. If two check bits fail parity, then the erroneous bit is the one common to both parity sums. If all three check bits fail parity, then the erroneous bit is b1 since it is the only one common to all three parity sums. Table 2 shows the correspondence between erroneous bits and sets of parity failures.

It is interesting to note that the code generated by three circles is equivalent to the (7,4,3)-Hamming Code. This means it is perfect, single-error correcting, and has a minimum weight of three.

 
decimal binary codeword
0 0000 0000000
1 0001 0001110
2 0010 0010101
3 0011 0011011
4 0100 0100011
5 0101 0101101
6 0110 0110110
7 0111 0111000
8 1000 1000111
9 1001 1001001
10 1010 1010010
11 1011 1011100
12 1100 1100100
13 1101 1101010
14 1110 1110001
15 1111 1111111 
Table 1
 
 
 
parity failure region(s) error position
none none
A, B, and C 1
B,C 2
A,C 3
A,B 4
A 5
B 6
C 7
More circle codes

Larger circle codes can be generated in the above manner by using Venn-like diagrams with more circles. Suppose we have n circles of diameter 1.5, centered at the n -th roots of unity on the unit circle in the complex plane. Here is how to label the intersecting regions of this Venn-like diagram. Beginning with 1 in the center and spiraling outward counterclockwise, label the (n-1)2+ n intersecting regions as in Figure 1. The n outer regions will serve as check bits for our circle code defined as follows. Write the integers 0,...,2(n-1)2-1 in binary, put the i -th bit in the i-th region, fill in the remaining n outer regions with check digits. These ((n-1)2+n)-tuples are the codewords. This defines our circle code. In fact, a circle code generated by n circles will have a length of (n-1)2+n and dimension of (n-1)2. This can be easily shown.

Theorem: A circle code generated by n circles will have a length of (n-1)2+n and dimension of (n-1)2.

Proof: By the nature of our construction, each circle has one section that is not shared with the others, such as spaces 5, 6, and 7 in Figure 1. For an n-circle diagram, this amounts to n spaces. The inner regions of an n-circle diagram are those that are shared by 2 or more circles. There is only one region shared by all n circles. Due to the geometry of these diagrams, there are always n regions shared among j circles for 2<= j<= n-1. The dimension of an n-circle code is the number of inner regions of the diagram since the inner regions correspond to the information bits of the codeword. Thus, the dimension of an n-circle code is n(n-2)+1=(n-1)2. The length is then the sum of the dimension and the number of parity check regions.

Each parity check bit of an n-circle code equals the mod 2 sum of the values of the inner regions of that specific circle. This is an extension of the parity sum construction of the previous section. The generalized circle code can correct one error since the number of combinations of parity failures is always greater than or equal to the number of bits in a codeword.

Because of its properties, we could consider using the circle code to solve Ulam's problem. However, a single, as yet unmentioned property will prevent us from doing this. This property is the rate of the circle code. The rate,  R, of any code is defined as the ratio of information carrying bits to total bits of a codeword. Thus,

R=k/n.
When compared to the Hamming Code, the circle code has a smaller rate which means it is less efficient. This is readily seen since for an equal number of check bits, the Hamming Code contains more information bits. If we let r=n, then
RHam =(2n-n-1)/(2n-1), whereas Rcircle=((n-1)2)/(n2-n+1).
In fact, the dimension of the Hamming Code is exactly equal to the number of combinations of parity failures given a fixed number of check bits.

This comparison simply reiterates the fact that the Hamming Code is the best single-error correcting code. Accordingly, it will be used to solve Ulam's Problem.

Original Problem

We will now solve Ulam's original problem as stated in the beginning of this paper assuming one lie is allowed. We must first determine how many binary digits are needed to encode all numbers from 0 to 1,000,000. This is equal to the number of binary digits needed to represent 1,000,000. If we let b denote the number of binary digits needed, then

b=1+[ log2(1,000,000)] =20.
Next we must find the Hamming Code with dimension greater than or equal to 20. Using the parameters of the general Hamming Code given earlier, this is the (31,26,3)-Hamming Code. Obviously, the (31,26,3)-Hamming Code has a much larger cardinality than the set {0,1,...,106}. In fact, it is roughly 67 times larger. Therefore, we will concern ourselves with a subcode of the (31,26,3)-Hamming Code consisting only of the codewords representing the numbers 0 through 1,000,000. The reader should note that this subcode is not linear, although this fact has little bearing on the solution.

As a result of the definition, the first six bits of every codeword in our subcode are zeros. Only the last 25 bits of our subcode will carry information needed by Player 2, the first 20 being leftover information bits while the last 5 are parity check bits. In order to determine Player 1's number, Player 2 asks questions of the form, ``Is the {\it i}-th bit of the (31,26,3)-Hamming Code representation of your number a 1?'' for i =7...31. After 25 questions, Player 2 will have a binary 31-tuple whose first 6 bits are zero.

Now Player 2 must error-check his 31-tuple. He does this using the Hamming Check Matrix for the (31,26,3)-Hamming Code. The dot product (where addition is mod 2) of Player 2's possible codeword with each row of the 5x31 check matrix yields a binary 5-tuple. Converting this 5-tuple to decimal yields a number from 0 to 31, which corresponds to the index of the erroneous bit. A zero implies an accurate codeword meaning Player 1 never lied.

Finally, Player 2 corrects the erroneous bit - if necessary - by inserting the opposite binary value. For example, if the erroneous bit is a 1, Player 2 changes it to a 0. Converting the corrected codeword to decimal will yield Player 1's number.

The use of the Hamming Code gave us a solution that does not depend on feedback from Player 1. All 25 questions were constructed before the game actually began, and Player 1's number was determined using a quick and efficient decoding algorithm. Thus, g(M,1)\leq 25 , when M=106 . It will follow from a result in section 7 that, in fact, g(M,1)=25.

Generalized Problem

Generalizing Ulam's original problem gives us the following question.

Question: Player 1 chooses a number between 0 and M-1. Player 2 must determine this number by asking yes or no questions. What is the minimum number of questions needed to correctly determine Player 1's number if he can lie at most e times (e >= 0)?

The solution from the previous section, applied to the set {0,1,2,...,M}, can be used to determine g(M,1) for all M.

As before, we must first calculate how many binary digits are needed to represent every number in the set { 0,1,2,...,M } . Let b denote the number of binary digits needed. Therefore,

b=1+[ log2M].
Let Hr denote the Hamming Code with dimension 2r-r-1 and length 2r-1. Next we choose r as small as possible so that 2r-r-1 >= b. If the dimension of H r is larger than b , we consider the subcode C whose elements are the codewords of H r corresponding to the numbers 0 through M. H r and C have the same number of check bits. The definition of C forces the first 2r-r-1-b bits of each codeword to be zero. We ignore these bits during the question phase of the game.

Player 2 then asks b+r questions of the form, ``Is the i-th bit of the ( 2r-1 , 2r-r-1 ,3)-Hamming Code representation of your number a 1?'', where {\it i}= 2r-r-b , 2r-r-b+1 ,..., 2r-1 . When finished, Player 2 will have a ( 2r-1 )-tuple to error-check using the corresponding Hamming Check Matrix.

If the ( 2r-1 )-tuple has an erroneous bit, Player 2 corrects it by inserting the opposite binary value. Converting the corrected codeword into decimal will yield Player 1's number. Again, no feedback was required, all questions were pre-determined, and an efficient decoding algorithm exists for the code used.

Comparison to Pelc's Solution

In 1987, Andrzej Pelc [P] solved Ulam's original problem with one lie using a rigorous accounting process. The solution was complicated and required feedback from the Responder on every question. Pelc went on to solve the
generalized one-lie problem giving the following conditions for the minimum number of questions (Pelc's paper dealt with the set {1, 2,..., M}).

Theorem:
If M is even, f(M,1)=min {n:M(n+1)<=2n} ,
If M is odd, f(M,1)=min(n:M(n+1)+n-1<= 2n} .
Thus, f(106,1)=25.

Where Pelc deals with the set {1,2,...,M}, we will use the set {0,1,...,M-1}. In either case, Player 1 has an equal number of possibilities to choose from. See Appendix B for the tabular comparison of g(M,1) and f(M,1).

In his paper, Niven [N] states that g(M,1)=f(M,1) or f(M,1)+1 . Though earlier parts of his solution contained errors, this statement and its argument are correct. Therefore we will consider the proof for this statement already done. This is also shown experimentally in the comparison contained in Appendix B.

Case of the Pathological Liar

An n x n Hadamard Matrix H is a matrix of \pm 1's satisfying

H*Ht = n I_{n} .
Hadamard Codes are constructed from Hadamard matrices. ( There are at least three ways to construct a code from a Hadamard matrix. One way is to create a new matrix A (the binary Hadamard matrix) from H by replacing the 1 's in H by 0 's and -1 's in H by 1 's. One Hadamard code is the code C whose codewords are the columns in A along with all their complements. See chapter 2, section 3, of [MS].) Hadamard codes are the best binary codes for correcting large numbers of errors. From a well-known but difficult conjecture, we expect that Hadamard matrices exist for n=1,2 or 4|n . If we assume this conjecture, and if
1/(4+3/e) < e/n < 1/(2+1/e)),
then it is possible to show that (Joyner, unpublished)
g(M,1)<= [ 4e+3-(4/(e+1))M]
In fact, g(M,1) can be calculated explicitly under these conditions. This is a very interesting result. If Player 1 promises to lie more than one-fourth but less than one-half the time to Player 2's questions, then we can determine g(M,e) precisely. It seems we know more about Ulam's problem (and its Coding Theory equivalent) if Player 1 lies many times than if he lies only twice. We credit this result to Dr. Joyner, Plotkin, and Levinshtein [MS, (Theorem 8, Chapter 2, Section 3)].

Conclusions

Approaching Ulam's problem from the field of Coding Theory yields a solution that is easy to understand and implement. The use of Hamming Codes gives a very efficient algorithm for constructing Player 2's questions, not to mention an efficient method of decoding. Also, we do not require feedback from Player 1 in order to advance the game. This is a definite improvement over Pelc' s solution. Although the Hamming Codes sometime require one more question than Pelc's solution, it is a small sacrifice for our solution's simplicity.

Although Ulam's problem has been solved for one lie, the solution is only a small piece of a larger problem for Coding Theorists. What happens when Player 1 can lie twice? This problem has been solved directly - again by Pelc - but with the same feedback and heavy accounting as before. Coding Theory has no answer. What we do know, thanks to Ray Hill \cite{H}, is that the codes necessary for the solution are not linear. The difficulty of this problem has increased drastically with the addition of only one lie. However, when the number of lies increases suitably along with the length of the code, thanks to Hadamard Codes, one can also solve Ulam's problem. The middle ground remains untouched. Coding Theory has much work ahead of it.

Appendix A

Minimum distance d of best binary (n,k) codes by A. Brouwer \cite{Br}, compiled by Luis Goddyn.

Derived from the tables of aeb@cwi.nl (A. Brouwer) found at
ftp.win.tue.nl:/pub/math/codes/table2.gz
Rows:   n = 1..10   (Brouwer's tables go to n=256)               
Columns: n-k = 0..min(n-1,31)
Legend: n+ means n <= d >= n+1      
n# means n <= d <= n+2
   
                 10  9   8   7   6   5   4   3   2   1   0  n-k/
                 -----------------------------------------    / n
                                                         1      1
                                                     2   1      2
                                                 3   2   1      3
                                             4   2   2   1      4
                                         5   3   2   2   1      5
                                     6   4   3   2   2   1      6
                                 7   4   4   3   2   2   1      7
                             8   5   4   4   2   2   2   1      8
                         9   6   4   4   3   2   2   2   1      9
                    10   6   5   4   4   3   2   2   2   1     10
Appendix B

Maple tables comparing Pelc's formula given above and our formula

g(M,1)= 2+[\log2 (M- 1)]+ [log2 ( 2+[ log2 (M- 1)]+ log2( 1+[log2 (M- 1)]))].
 
M f(M,1) g(M,1)
11 7 7
13 7 7
15 7 7
17 8 9
19 8 9
21 8 9
23 8 9
25 8 9
27 8 9
29 9 9
31 9 9
33 9 9
35 9 10
37 9 10
39 9 10
41 9 10
43 9 10
45 9 10
47 9 10
49 9 10
 
M  f(M,1) g(M,1)
10 7 7
12 7 7
14 7 7
16 7 7
18 8 9
20 8 9
22 8 9
24 8 9
26 8 9
28 8 9
30 9 9
32 9 9
34 9 9
36 9 10
38 9 10
40 9 10
42 9 10
44 9 10
46 9 10
48 9 10
50 9 10
 
References

[B] E. Berlekamp, ``Block coding with noiseless feedback,'' PhD Thesis, Dept EE, MIT, 1964

[Br] M. Grassl's best linear codes site, http://www.codetables.de

[H] R. Hill, ``Searching with lies,'' in Surveys in Combinatorics, ed. by P. Rowlinson, London Math Soc, Lecture Notes Series # 218

[MS] F. MacWilliams and N. Sloane, The theory of Error correcting codes, North-Holland Pub. Co., 1977

[N] I. Niven, ``Coding theory applied to a problem of Ulam,'' Math Mag 61(1988)275-281

[P] A. Pelc, ``Solution to Ulam's problem on searching with a lie,'' J Combin Theory A 44(1987)129-140

[U] S. Ulam, Adventures of a mathematician, Scribner and Sons, New York, 1976 


Typed into html 7-16-99 by wdj. Last updated 1-29-2008.