Number Guessing

By asking a small number of innocent-sounding questions about an unknown number, it is possible to reconstruct the number with absolute certainty (assuming that the questions are answered correctly). Ball and Coxeter (1987) give a number of sets of questions which can be used.

One of the simplest algorithms uses only three questions to determine an unknown number $n$:

1. Triple $n$ and announce if the result $n'=3n$ is Even or Odd.

2. If you were told that $n'$ is Even, ask the person to reveal the number $n''$ which is half of $n'$. If you were told that $n'$ is Odd, ask the person to reveal the number $n''$ which is half of $n'+1$.

3. Ask the person to reveal the number of times $k$ which 9 divides evenly into $n'''=3n''$.

The original number $n$ is then given by $2k$ if $n'$ was Even, or $2k+1$ if $n'$ was Odd. For $n=2m$ even, $n'=6m$, $n''=3m$, $n'''=9m$, $k=m$, so $2k=2m=n$. For $n=2m+1$ odd, $n'=6m+3$, $n''=3m+2$, $n'''=9m+6$, $k=m$, so $2k+1=2m+1=n$.

Another method asks:

1. Multiply the number $n$ by 5.

2. Add 6 to the product.

3. Multiply the sum by 4.

4. Add 9 to the product.

5. Multiply the sum by 5 and reveal the result $n'$.

The original number is then given by $n=(n'-165)/100$, since the above steps give $n'=5(4(5n+6)+9)=100n+165$.

References

Bachet, C. G. Problèmes plaisans et délectables, 2nd ed. 1624.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 5-20, 1987.

Kraitchik, M. ``To Guess a Selected Number.'' §3.3 in Mathematical Recreations. New York: W. W. Norton, pp. 58-66, 1942.