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 2^{9}, 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?

i loved this blog post! nice job bru.

Dude, you can four-color in your mind?!?

Ha, I was waiting for someone to bring this up =).

When I was writing the post, I thought about it, and almost went with five-coloring, since there’s a pretty straightforward algorithm for five-coloring (used by some register allocators, IIRC).

However, I poked around with four-coloring a bit, and it seems that if you remember a few simple tricks, you can probably four-color most user-generated maps by hand. Obviously, if the guest is knowledgeable and adversarial, you might get into trouble. But then again, these aren’t exactly parlor tricks if your guests are computer scientists.

i don’t think four coloring would be that amazing to people. and actually, i think the others ones people may not be that startling to others (maybe the eulerian cycle one).

two things i’d add to this list:

1. a card trick that involves two people that relies on the fact that (5 choose 4) * 4! > 52. (http://www.apprendre-en-ligne.net/crypto/magie/cardTrick.pdf)

2. zero knowledge proofs: for instance, how a colorblind person can be convinced that two objects are indeed different colors.

Interestingly, a (non-CS) friend just mentioned today that he found four-coloring hard to believe. So I think it’s pretty neat. If you take the claim on its face — “I can draw ANY map at all?” — then I think it comes across as pretty impressive.

The card trick is neat but it requires an accomplice, which makes execution hard.

ZKP is very cool, but I’m not sure how you’d use it in a party setting. One issue is that you have to explain how it works beforehand, and also I don’t know how well a probabilistic “proof” would go over with normal people. How many times would you have to iterate to convince someone? At the moment, it seems more like a cool discussion topic than basis for a parlor trick. Definitely fun to think about, though — we should try to come up with with a good ZKP application that works in a social setting.

Do you think most people would be satisfied with an explanation that “Buffalo buffalo buffalo buffalo.” is a grammatically correct sentence?

I think you could have a whole party based on just that.

k

HI

I made a giant pussy cat out of paper