## A computer scientist plays Twenty Questions June 12, 2012

Posted by Ezra Resnick in Computer science, Game theory.

“Would you like to play Twenty Questions?”

“Sure, how do we play?”

“I think of a famous person — alive or dead, real or fictional — and you have to guess who it is, in no more than twenty yes-or-no questions.”

“Well… I could use binary search to identify a single letter of the alphabet in 4.7 yes-or-no questions (on average), so nineteen questions should allow me to identify four letters. Why don’t you just tell me the first four letters of your person’s last name, and I’ll guess who it is.”

“Actually, I don’t think I want to play any more.”

“That’s OK — the game is flawed, anyway: it assumes there are no more than 1,048,576 famous people to choose from…”

1. david - June 13, 2012

the trick is to play by the rules, not change them (except by mutual agreement).
good luck,
a

Ezra Resnick - June 13, 2012

The rules weren’t changed: the proposed strategy uses the available questions to identify the first few letters of the target’s name.

2. Yanai - September 17, 2015

But in order to do a binary search, you need to know if a certain character comes before, at, or after the character you’re asking about.
That means you need more than 1 question per step, no?

Ezra Resnick - October 3, 2015

No: You can always divide the remaining letters into two sets and then determine which set the target letter is in with a single question. So after one question you’ve narrowed it down to 13 letters, after two questions you’re down to 6 or 7 letters, etc.