OPTIMAL COMPARISON STRATEGIES IN ULAM SEARCHING GAME WITH 2 ERRORS

Suppose x is an n-bit integer. By a comparison question we mean a ques tion of the form ''does x satisfy either condition a less than or equa l to x less than or equal to b or c less than or equal to x less than or equal to d?''. We describe strategies to find x using the smallest possible number q(n) of comparison questions, and allowing up to two o f 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 B erlekamp's inequality 2(q) greater than or equal to 2(n) ((q/2) + q 1). This result would disappear if we only allowed questions of the fo rm ''does x satisfy the condition a less than or equal to x less than or equal to b?''. Since no strategy can find the unknown x is an eleme nt of {0, 1,...,2(n)-1) with less than q(n) questions, our result prov ides extremely simple optimal searching strategies far Ulam's game wit h two lies - the game of Twenty Questions where up to two of the answe rs may be erroneous.