Finding a needle in twenty questions
Tonight's idea
The game is simple. You think of a whole number from 1 to 100; I ask yes-or-no questions. The slow way is "Is it 1? Is it 2?", up to 100 questions. The fast way is to ask "Is it more than 50?" Whatever the answer, half the numbers are gone. Then "more than 75?" or "more than 25?", and half of what is left is gone. Each question halves the suspects.
How many halvings to get from 100 down to 1? \(100 \to 50 \to 25 \to 13 \to 7 \to 4 \to 2 \to 1\): seven. Another way to see it: each yes-or-no answer is a 1 or a 0, so seven answers in a row make a 7-digit binary number, and seven binary digits can name \(2^7 = 128\) different things, which is more than 100. Six would only cover \(2^6 = 64\), not enough. This is the same idea as the sheet on counting to 31 on one hand: every yes-or-no answer is one bit.
Now the surprising part: the number of questions grows incredibly slowly. A thousand things take ten questions (\(2^{10} = 1024\)). A million take twenty (\(2^{20} \approx 1{,}000{,}000\)), which is why the parlour game Twenty Questions actually works: twenty well-chosen questions can single out one thing from a million. A billion take thirty. Every time the haystack gets a thousand times bigger, the search gets only ten questions longer.
Computers live on this. Looking up a word in a sorted list of a billion words by halving takes about thirty steps; checking each word in turn could take a billion. It is called binary search, and the only requirement is that the list is in order. That is why so much effort goes into sorting things.
Sorting uses the same halving trick (split the pile, sort each half, merge), and it is why a computer can sort a million names in a blink.
Watch one: finding 73
Suspects 1–100. Seven questions, each about the middle of what is left, and it is 73.
Notice each question asks about the middle of what is left. Ask about the middle and you lose half no matter what the answer is. Ask near the edge and a lucky answer loses a lot, but an unlucky one loses almost nothing. Since you cannot control the answer, the middle is the safe choice.
Your turn
- What is the smallest number of yes-or-no questions that is always enough for a number from 1 to 1,000? From 1 to 1,000,000? Explain using powers of 2.
- Someone picks a card from a standard deck of 52. How many yes-or-no questions do you need to be sure of naming it? Design the first two questions so that each one cuts the remaining cards in half (26, then 13).
- Play the game with a family member who picks a number from 1 to 100. Write your questions and their answers, and count. Did you need more than seven? If so, which question was not about the middle?
- A dictionary has 1,000 pages. You open it in the middle, see which half the word is in, and repeat. How many openings before you are on the right page? What if the dictionary had 4,000 pages?
Stretch: nine coins, two weighings
You have nine coins that look identical, but one is slightly lighter. You have a balance scale that compares two piles and tells you which is heavier (or that they are equal). Find the light coin in just two weighings.
Hint: a weighing has three outcomes, not two, so each one can cut the suspects to a third, not a half. \(3 \times 3 = 9\). How many coins could you handle with three weighings?
Answers
- Ten, since \(2^{10} = 1024 \ge 1000\) but \(2^9 = 512\) is too few. Twenty, since \(2^{20} = 1{,}048{,}576\) just covers a million and \(2^{19} = 524{,}288\) does not.
- Six, since \(2^6 = 64 \ge 52\) and \(2^5 = 32\) is not enough. Good first questions split the deck in half: "Is it red?" (26 each) then "Is it a heart?" or "Is it a spade?" depending (13 each). After that, "Is it higher than 7?" and so on.
- Seven suffices if every question splits the remaining range as evenly as possible. Any question that asks about a number far from the middle risks an extra round.
- Ten openings: \(2^{10} = 1024 \ge 1000\). For 4,000 pages, twelve: \(2^{12} = 4096\). Four times the pages cost just two more openings.
Stretch. Split into three piles of three. Weigh pile A against pile B. If they balance, the light coin is in pile C; otherwise it is in the lighter pile. Now you have three suspects. Weigh one against another: if they balance, it is the third; otherwise it is the lighter one. Two weighings. With three weighings you can handle \(3^3 = 27\) coins, and in general \(3^n\) coins in \(n\) weighings, because each weighing has three outcomes. (The famous harder puzzle, twelve coins where you do not know whether the odd one is heavier or lighter, also takes exactly three weighings, but needs a cleverer plan. Look it up once you have done this one.)