Pair up with someone whose birthday you do not know. Find out their birthday using binary search, asking whether their birthday is earlier or later in the year than each of your guesses. How many guesses might be required to guarantee you find out their birthday

the best you can do is ask something that splits the search space — the potential birthdays, in this case — in half.

Explanation:

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?