Skip to main content
1 of 3
shreevatsa
  • 661
  • 1
  • 10
  • 14

BTW, this problem is known as the Ulam(-Renyi) problem or Ulam's searching game, and has an extensive literature (with which I'm not familiar) — the following is a survey as of 2002:

  • Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2q/(q+1), which for n=1000 is indeed 14.

This paper seems to have a "simple solution", but maybe others more familiar with the topic can find better references.

shreevatsa
  • 661
  • 1
  • 10
  • 14