Game of 20 Questions
You have probably played the ancient game "Twenty Questions." A proposer thinks of an object; you get 20 yes/no questions (e.g. Is it a slide rule?). The proposer wins if you use all 20 questions before determining the object.
Now, with careful questioning, you can identify 1 object out of a million options, as 2^{20} > 1,000,000.
In 1976, mathematician Stanislaw Ulam asked what happens if the proposer was allowed to lie once. Play the game...do you see a good questioning strategy?
The obvious approach is to ask each question twice, requiring 41 questions. But, mathematicians have shown that you should be able to reduce this to 25 questions with "clever" questioning.
And, to extend the lies further...29 questions are needed if the proposer is allowed at most two lies...and 33 questions for at most three lies.
See the pattern: 20, 25, 29, 33.... Oops, maybe I am lying!
