Posted by: dschadewald | January 11, 2009

## Brain Teasers

In the spirit of on-campus recruiting, I figured I would write a post about brain teasers which could potentially come up in an interview.

1.  Suppose you are at an auction and are bidding on a good whose value is X.  The value of X is is a random value uniformly distributed between 0 and 1000.  If you bid X or anything greater than X you can immediately sell the good for 1.5 times what you paid for it.  If X is greater than your bid, you lose out and do not get anything.  What should you bid?

This seems like a tough sort of question, but it is actually pretty easy if you really think about it.  The answer is that you should bid nothing and just expect to break even.  The reason is that if you ever win the good you are more than 50% likely to lose money.  An easy example demonstrates this:  if you bid 100 and you win the good, then the value of the good is therefore uniformly distributed between 0 and 100.  If the good is worth \$66.6 or less though, you are losing money since you can’t sell it for more than you paid for it.  Thus there is a 66.6% chance that you will actually be losing money.  Change 100 to any number you’d like and you will see that you will lose money.

2. Suppose there is a room with 100 light bulbs labelled 1 through 100.  Person 1 walks in the room and turns on every light bulb.  Person 2 walks in the room and flips the switch on every 2nd light bulb (i.e. he turns off all even numbered light bulbs).  Person 3 walks in the room and flips the switch on every 3rd light bulb (turning some on and some off).  This process continues until person 100 goes through and flips the switch on the 100th light bulb.  Which light bulbs will be lit up at the end?

Again this is kind of tricky but not really.  If you think about it, for a light bulb to be turned on, it must be flipped an odd number of times.  To be flipped an odd number of times, it must have an odd number of factors.  The only numbers that have an odd number of factors are the perfect squares (for example 4 has three factors 1,2,4).  Thus light bulbs 1,4,9,16,25,36,49,64,81,100 will be on at the end.

3.  You have 10 machines that produce 10g gold coins.  After a few years though, you discover that one of the machines isn’t working correctly and produces coins that are 10% lighter (i.e. 9 grams).  How do you figure out which machine is producing the light coins with only one weighing?

This one I think is pretty tough.  One good and practical solution is to label each machine from 1 to 10 and have each machine produce the number of coins that it is labeled (ie machine 1 produces 1 gold coin, machine 2 produces 2 etc.).  Then weigh all the coins at once.  The amount that the coins should weigh is 10g*(1+2+3+4+5+6+7+8+9+10)=550g.   However many grams the total is away from 550g will correspond to the dysfunctional machine.  For example if it weighs 545g, then we know that machine 5 is producing the lighter coins.

Well I hope one of you guys gets one of these questions in an interview.  Good luck!