During my senior year in high school, I was fortunate enough to participate in the Intel International Science and Engineering Fair. At the awards banquet I was seated with fourteen others and we each had the choice of ordering either salmon or steak for our respective entrées. I noticed that while taking our fifteen different orders, our waiter did not write anything down. How on Earth was he going to remember what each of us had requested?!
It turns out the answer is intimately related to Problems 2 and 5 in my last post. Did you realize you always save at least 999 people on the game show? Here’s how:
The person at the back of the line will look at all 999 hats in front of him. If the number of black hats is odd, he will shout “Black!” If the number of black hats is even, he will shout “White!” From this information, the second person in line can deduce from the hats in front of him what the color of his own hat is! For example, if Contestant 1 shouts “Black!” and Contestant 2 sees an even number of black hats in front of him, he can deduce that his own hat is black because the total number of black hats Contestant 1 sees is odd. From information given in Contestant 1’s and Contestant 2’s answers, Contestant 3 can determine his hat’s color via a similar parity argument, and so on. At least $999 will be donated to charity.
How about Problem 5? One solution requires knowledge of how to represent numbers in binary. Let’s say you owe your friend $3,761.50, and want to pay him using pennies and dimes, as well as $1, $10, $100, and hypothetical $1,000 bills. How would you pay him using the least number of monetary tokens? The answer to this is easy – we all learned about the hundredths’ place, the tenths’ place, ones’ place, the tens’ place, the hundreds’ place, and so on in elementary school. The digit in the ones’ place tells us how many $1 bills we need to give our friend, the digit in the tens’ place tells us how many $10 bills we need to give our friend, and so on. Written more suggestively,
3,761 = 3*103 + 7*102 + 6*101 + 1*100 + 5*10-1 + 0*10-2
Why does the number 10 appear so significant in the above equation? In the above equation, 10 is called the “base.” In base 10, we write every number as the sum of whole multiples of powers of 10. Notice that none of the bold numbers – the digits – can be greater than or equal to the base (10); they must be between 0 and 9. If one of the bold digits was greater than 9, we could just use a monetary token of higher value to reduce the total number of bills and coins we need to repay our friend. This leads to:
Rule #1: The value of each digit must be less than the base.
Could we use a number other than 10 as our base? Let’s try using 2! I can think of at least one way to write 3,761.50 as the sum of multiples of powers of two:
3,761.50 = 1*211 + 0*210 + 0*29 + 0*28 + 0*27 + 0*26 + 53*25 + 1*24 + 0*23 + 0*22 + 0*21 + 1*20 + 1*2-1