Optimal comparison strategies in Ulam's searching game with two errors

✍ Scribed by Daniele Mundici; Alberto Trombetta

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 974 KB
• Volume: 182
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00030-3

✦ Synopsis

Suppose x is an n-bit integer. By a comparison question we mean a question of the form "does x satisfy either condition a <x< b or c<x<d?".

We describe strategies to find x using the smallest possible number q(n) of comparison questions, and allowing up to two of the answers to be erroneous. As proved in this self-contained paper, with the exception of n = 2, q(n) is the smallest number q satisfying Berlekamp's inequality This result would disappear if we only allowed questions of the form "does x satisfy the condition a <x <b?". Since no strategy can find the unknown x E (0, 1, . . ,2" -1) with less than q(n) questions, our result provides extremely simple optimal searching strategies for Ulam's game with two lies -the game of Twenty Questions where up to two of the answers may be erroneous.