The Password Guessing Game

Honest game: 20 questions (since 2^20 = 1,048,576 ≥ 1,000,000). With 1 possible lie: 25 questions using Ulam's adaptive liar-game strategy. The extra 5 questions detect and correct the lie's effect on the binary search.

The honest game is classic binary search. Each question splits the remaining range in half. The liar game is harder — you must track not just the range but also how many lies have potentially been used, since a liar can mislead you once. Step 1: Honest game: After each question 'Is n > X?', the answer halves the candidates. After k questions, you can distinguish 2^k numbers. Need 2^k ≥ 1,000,000. Smallest k: 2^19 = 524,288 (too small), 2^20 = 1,048,576 (sufficient). Answer: 20 questions. Step 2: Strategy: first ask 'Is n > 500,000?' → narrows to [1,500000] or [500001,1000000]. Repeat binary search within the surviving half. Step 3: Liar game intuition: after a lie, you cannot trust one of your answers. You need to ask enough redundant questions to detect whether a lie occurred and correct its effect. Step 4: State in liar game: (range_size, lies_remaining). State (n,0) requires ceil(log₂(n)) questions (no lies possible). State (n,1) requires more — you need to handle the case where the answer might be wrong. Step 5: Berlekamp's result: with 1 possible lie and n candidates, you need at most ceil(log₂(n)) + ceil(log₂(log₂(n))) + O(1) questions. For n=1,000,000: 20 + ceil(log₂(20)) + correction ≈ 20 + 5 = 25 questions. Step 6: The exact answer for 1 lie and 1,000,000 numbers: 25 questions suffice with an optimal adaptive strategy. Key Insight: The liar game beautifully illustrates the cost of unreliable information. Each possible lie introduces an extra layer of uncertainty that requires additional questions to resolve. The logarithm of the range size gives the base cost; the number of allowed lies adds roughly a logarithm of that cost again — a doubly-logarithmic penalty for dishonesty.