Searching Games - Two unknowns and a Lie

Advisor: Dr. David Clark

In the paper ‘Solution of Ulam’s Problem on Searching with a Lie’, Andrzej Pelc proves a long standing problem posed by S.M Ulam. The question is stated as “What is the minimal number of yes-no queries needed to find an integer between one and one million.” We investigate a similar game where instead of searching for one non negative integer, we look for two non negative integers. Furthermore we consider when the responder to the queries is allowed to lie at most once. We provide a bound for the responder in online searching games with one lie, and a strategy for the responder in an offline searching game with no lies allowed by the responder. Lastly we look at a future direction for the project in the form of questions left unanswered.