Friday, May 14, 2010

Astound your friends!

I'll pick a number (an integer, to be specific) between 0 and 255. You can ask me 8 yes-or-no questions, and then you should be able to tell me which number I picked.

Solution below (highlight with your mouse):

First question: "Is the number greater than or equal to 128?"
Second question: "Is the number greater than or equal to either 192 (if question 1's answer was "yes") or 64 (if question 1's answer was "no")?

And so on. Each question give you an opportunity to throw away half of the remaining field. Dividing by two progressively, you start with 256, then 128, 64, 32, 16, 8, 4, 2 and then 1.

Actually, the last question can be "Is the number odd?" since at that point you'll have narrowed the field to two adjacent numbers.

Note also that if you write down the answers with "yes" being a 1 and "no" being a 0, from left to right, you'll have written down the number in binary.

This works for any number range. The number of questions required is the log2 of the size of the range rounded up to the next highest whole number.

Anyone whoever gets the "clock" game on TPiR should be able to nail each prize in about 10 seconds. Start at 1000. If higher, go to 2000. Cut the range in half each guess until you get inside of a $10 range, then just roll through all 10 remaining prices starting at $xx9 and counting down. Let's say a prize is $667. $1000, $500, $750, $650 (not half way, but easier under pressure), $700 (again, a compromise), $675, $660, $670, $669, $668, $667. Boom.

No comments: