Building a Computer: Part I

Posted on December 25, 2013 by mohittiwari

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*10³ + 7*10² + 6*10¹ + 1*10⁰ + 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*2¹¹ + 0*2¹⁰ + 0*2⁹ + 0*2⁸ + 0*2⁷ + 0*2⁶ + 53*2⁵ + 1*2⁴ + 0*2³ + 0*2² + 0*2¹ + 1*2⁰ + 1*2^-1

Continue reading →

More Brainteasers

Posted on December 16, 2013 by mohittiwari

As promised, I’m back to tell you more about myself and tickle your brain! I’m terribly sorry for giving such a short description of my background in my last post. If I had to describe myself in another $\leq 5$ words, I’d write: “Breakdancing, bodybuilding physicist… Ladies: single.”

Problem 1: A thousand balloons numbered 1, 2, … , 1000 are arranged in a circle. Starting with balloon 1, every alternating balloon is popped. So balloon 1 is popped, balloon 3 is popped, balloon 5 is popped, and so on until balloon 999 is popped. But the process does not stop here! We keep going around the circle with the remaining balloons and pop every other one. So next balloon 2 is popped, balloon 4 is skipped, balloon 6 is popped, and so on. This process continues until only one balloon is left remaining; which is the last balloon standing?

A thousand red balloons numbered from 1 to 1000. Starting at the gold star, we pop every other balloon while traveling clockwise. Which is the last balloon remaining?

It is of course easy to solve Problem 1 via brute force, but can you think of a more elegant solution? Do you really need to go around the circle $log(n)$ times? If you get stuck, try working on Problem 2 for a while:

Problem 2: A thousand people stand in single file on a game show. Each person is wearing a hat which is either black or white. Each person can see the hats of all the people in front of them in line but they cannot see their own hat. Starting with the person at the back of the line and progressing forward, the game show host will ask, “What color is your hat?” Each contestant is only permitted to answer “black” or “white.” For each correct answer, the host will donate $1 to charity. If the contestants are allowed to discuss a strategy before they are lined up and given their hats, how much can they guarantee will be donated to charity?

If you managed to solve Problem 2, Problem 3 should be easy.

Problem 3: Now each person is given a hat which is one of $n$ colors, and is allowed to answer the host’s question by giving any of the $n$ colors. How much can the contestants guarantee will be donated to charity?

Problem 4: You are given ten coin-making machines which produce coins weighing 2 grams each. Each coin-maker can produce infinitely many coins. One of the ten machines, however, is defective and produces coins weighing 1 gram each. You are also given a scientific balance (with a numerical output). How many times must you use the balance to determine which machine is defective? What if the weight of the coins produced by the rogue machine is unknown?

I happen to be very good personal friends with Count von Count. One day as we were walking through Splash Castle, the Count told me he had passed his arithmetic class and was throwing a graduation party! Alas, before he could host the get-together, he needed to solve a problem on injective mappings from powersets to subsets of the natural numbers…

Problem 5: The Count has a thousand bottles of apple juice for his party, but one of the bottles contains spoiled juice! This spoiled juice induces tummy aches roughly a day after being consumed, and the Count wants to avoid lawsuits brought on by the innocent patrons of Sesame Place. Luckily, there is just enough time before the party for ten of the Count’s friends to perform exactly one round of taste-testing, during which they can drink from as many bottles as they please. How can the ten friends determine which bottle is both tummy ache- and lawsuit-inducing? You can assume Count’s friends have promised not to sue him if they get sick.

Please let me know what you think of these problems in the comments! Too easy? Too hard? Want more? Tell me so!

The allure of elegance

Posted on September 24, 2012 by mohittiwari

On one of my many short-lived attempts to study for the International Physics Olympiad, I picked up a copy of a well-known textbook by Halliday and Resnick. My high school didn’t offer a course in electricity and magnetism, so I figured I would have to teach myself about the topic if I wanted to solve problems competitively.

I only managed to solve about 3 problems from the book before a friend called me up asking if I wanted to play Frisbee. After that, I don’t think I ever looked at the text again, although for some reason I did bring it to college – maybe to make sure I had enough things gathering dust on my dorm room shelf. That’s not to say it’s a bad book! In fact, I learned quite a bit from the three problems I solved. Here’s one of them: