The Game of Googol
A classic interview puzzle about optimal stopping — cards with unknown numbers are revealed one at a time, and you must guess when the current one is the largest, with a surprisingly simple near-optimal strategy.
In the Game of Googol, someone writes down different numbers (any numbers, however large or small) on slips of paper and turns them face down in random order. You flip them over one at a time. At any point you can stop and declare "this is the largest one" — but once you flip past a slip, you can't go back to it. You win if you correctly stop on the single largest number. What strategy maximizes your odds?
This is the classic secretary problem dressed up with numbers instead of job candidates. The surprising result: you should never guess on any of the first roughly slips (about 37% of them, where ) — just look and pass, using them to learn the scale of numbers involved. After that point, stop on the very first slip that beats every number you've seen so far. This strategy wins about of the time regardless of how large is, which is remarkably high given you're picking blind out of candidates in a single pass.
Worked intuition. With slips, the rule says observe-only through the first slips, then pick the first slip after that which is bigger than all 3 you've already seen. Even though you're committing without ever seeing what's left, this beats naive strategies (like always guessing the first card, which wins only of the time) by a wide margin.
The Game of Googol is the secretary problem in disguise: observe the first of the candidates purely to calibrate, then commit to the first one afterward that beats everything you've seen — a strategy that wins about 37% of the time no matter how many candidates there are.
Related concepts
Practice in interviews
Further reading
- Ferguson, 'Who Solved the Secretary Problem?', Statistical Science (1989)