A little while back we had a dinner party at our house, and the conversation turned to birthdays. One of our guests had a remarkable ability to recall anyone’s birthday if she’d heard it before. She went around the room, reciting all of our birthdays, until she got to one guest whose birthday she hadn’t yet heard. Another guest spontaneously offered to try to guess that birthday, by asking no more than five yes-or-no questions.
I was immediately skeptical, for reasons I’ll explain below, but the general consensus at the party was that this was an exciting challenge that just might work. The guesser concentrated for a while, trying to intuit something about the guessee.
“Is it in October?” he asked? No. One question down, and he began to comprehend the difficulty of his task. He realized he had to go bigger.
“Does it have 30 days?” No. But that was more effective — it eliminated four months at once. Perhaps he was onto something.
But then, Question #3: “Hrm…. Is it in March?” No. At this point it was obvious to everyone that he was doomed. Two questions left and very little to go on.
At this point, I casually mentioned that five questions was far too few but that nine would do the trick. People seemed to be struck by two things: (1) 9 seemed to be an awfully arbitrary number and (2) given how catastrophicallly five questions had failed, there seemed to be no way that nine questions would be enough.
So the game was on. We picked another guest whose birthday hadn’t been mentioned before, and I got to work.
“Is your birthday in the first half of the year?” No.
“Is it in the third quarter of the year?” No.
“Is it between November 15th and December 31st”? Yes.
And so on, each time narrowing the range by half. Everyone quickly appreciated the brutal efficiency of this approach, and on exactly the ninth question, I asked if it was the correct date. A little applause followed, as if I had performed a magic trick.
Of course, this was no trick — it was a binary search, one of the basic tools in a computer scientist’s algorithmic toolbox. If you ask a yes-or-no question, and you have no prior belief that the answer is more likely to be one than the other, the best you can do is ask something that splits the search space — the potential birthdays, in this case — in half.
For this case, you’ll need to split the 365 days in a year in half 9 times to isolate a single day. 365 –> 183 (1) –> 92 (2) –> 41 (3) –> 21 (4) –> 11 (5) –> 6 (6) –> 3 (7) –> 2 (8) –> 1 (9). The easy way to figure this out is to realize that 512, or 29, is the smallest power of 2 greater than 365.
Usually, when people find out that I work with computers, they ask me to fix theirs. They don’t really care about what I actually do; to the average person, programming is opaque. But now I see another avenue for our skills: parlor tricks.
- I’ll guess your birthday with just 9 yes-or-no questions! (binary search)
– I’ll name a number in 2 seconds bigger than anything you can name in 10! (Busy Beaver or any other non-computable function)
– Draw any map you want, however complicated, and give me just four (different) colored crayons. No matter what the map looks like, I’ll fill it in so that no adjacent countries have the same color! (four-color theorem)
– Here’s an easy problem: I’ll give you ten numbers, and I’ll guarantee that some of them, when added together, sum to 100,000. But I’ll bet you can’t figure out which ones in 5 minutes. Only ten numbers in all! (subset sum is NP-Complete)
– You give me a bunch of cities and highways between the cities. I’ll immediately tell you whether it’s possible to start at one city, drive on every highway between every city exactly once, and end up back at the original city! (Eulerian cycle)
– Any others?