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 2q≥2n ((q2) + q + 1). 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 ∈ {0, 1,...,2n - 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.

Optimal comparison strategies in Ulam's searching game with two errors / D. MUNDICI; A. TROMBETTA. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 182:(1997), pp. 217-232. [10.1016/S0304-3975(97)00030-3]

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

MUNDICI, DANIELE;
1997

Abstract

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 2q≥2n ((q2) + q + 1). 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 ∈ {0, 1,...,2n - 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.
1997
182
217
232
D. MUNDICI; A. TROMBETTA
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/214655
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 20
social impact