Ulam's searching game with a fixed number of lies
Joel Spencer · Theoretical Computer Science · 1992
Paul tries to find an unknown x from l to n by asking q Yes-No questions. In response Carole may lie up to k times. For k fixed and n, q sufficiently large, necessary and sufficient conditions are given for Paul to win.