## Archive for the ‘problems and solutions’ Category

### New Problem: Lemming

July 27, 2010

I’m at summer camp now, and my dorm is split between math and physics. I hear a lot of cute math problems. Here’s a recent one that I like. It’s significantly more “mathy” than some of the other cute problems I’ve heard.

This is from Ravi Vakil’s A Mathematical Mosaic: Patterns and Problem Solving

On a remote Norwegian mountain top, there is a huge checkerboard, 1000 squares wide and 1000 squares long, surrounded by steep cliffs to the north, south, east, and west. Each square is marked with an arrow pointing in one of the eight compass directions, so (with the possible exception of some squares on the edges), each square has an arrow pointing to one of its eight nearest neighbors. The arrows on squares sharing an edge differ by at most 45 degrees. A lemming is placed randomly on one of the squares, and it jumps from square to square following the arrows.

Prove that the poor creature will eventually plunge from a cliff to its death.

July 22, 2010

Since someone finally solved the puzzle, it’s time for the solution. Hint: the person who solved it was a computer scientist.

A reminder of the puzzle:

100 people sit in a circle so they can all see each other, but cannot see themselves. Someone walks around putting hats on their heads. He has 100 bins, each with a different color of hats inside, and he chooses a hat from an arbitrary bin for each person. Multiple people can have hats from the same bin, and not every bin must necessarily be used.

After looking at everyone else’s hats, everyone in the circle must guess the color of their own hat. They can confer beforehand about how they will guess, but cannot communicate after the hats are put on their heads. Describe a strategy so that exactly one person will guess their hat color correctly.

Solution:
Each of the 100 colors gets a number, starting with 0 and ending with 99. Now imagine an outside observer who can see the number of every single hat. If he added them all up and announced the sum, everyone would be able to guess their own number by subtracting the sum of the hats they can see from the true sum to find what’s missing.

This works even if the outside observer announces only the last two digits of the sum, because if, for example, you know the last two digits of the sum of all hats are 23 but the last two digits of the sum of the hats you can see is 75, then your hat must be 48.

Now the answer is evident. Since there is no outside observer, one person in the circle assumes the last two digits of the sum of all the hats are 00. The next person assumes the last two digits are 01. The last person around the circle assumes the last two digits are 99. Exactly one person is making the right assumption, so when everyone guesses their own hat based on their assumption, exactly one guess will be correct.

### Hat Puzzle

July 17, 2010

The most recent tricky puzzle I’ve heard:

100 people sit in a circle so they can all see each other, but cannot see themselves. Someone walks around putting hats on their head. He has 100 bins, each with a different color of hats inside, and he chooses a hat from an arbitrary bin for each person. Multiple people can have hats from the same bin, and not every bin must necessarily be used.

After looking at everyone else’s hats, everyone in the circle must guess the color of their own hat. They can confer beforehand about how they will guess, but cannot communicate after the hats are put on their heads. Describe a strategy so that exactly one person will guess their hat color correctly.

### Uniform Circular Motion – Simple and Complex

May 8, 2010

In reply to Matt, here’s a very short way to find the acceleration of an object in uniform circular motion.

Let the object move in the complex plane, so its position is given by

$z = R e^{\imath \omega t}$

Two time derivatives give the acceleration.

$\dot{z} = \imath \omega z$

$\ddot{z} = (\imath \omega)^2 z = - \omega^2 z$

That’s it. The acceleration points opposite the position, towards the center of the circle. The velocity $\dot{z}$ has a factor $\imath$, indicating a 90-degree rotation from the position. Hence the velocity is tangent to the circle.

This post is 80 words long.

May 3, 2010

999*1001 = 999,999

If a family has five children, the probability that at least three are girls is one half. The family must have at least 3 boys or at least 3 girls, but cannot have both. Probabilities are symmetric substituting boys for girls, so the probability is 50%.

You have two glass balls and are in a 100-story building. There’s a window on each floor. When you drop the ball out a window, it may or may not break, depending on how high you are. There’s a certain floor that is the transition from not breaking to breaking, so that if you drop it from that floor or above, it will break, and below that floor, it will not. This floor could be any of the floors from one to one hundred with equal probability. What is the fewest number of drops you need to make to be sure you accurately locate the transition floor?

14. Instead of the question asked, ask how many stories you can explore with $n$ drops. Drop the ball from story $n$ to begin. If it breaks, you need to drop from story 1, then 2, then 3 possibly up to $n-1$, requiring $n$ total drops. If it does not break, now drop it from $n + (n-1)$. This is the right way because if it breaks on the second drop, we’ll still need a maximum of $n$ total drops. Continuing, we see the highest building we can explore with $n$ drops is $n + (n-1) + (n-2) + ... + 1 = n(n+1)/2$. Set this equal to 100 and we get $n = 14$ (on rounding up).

Your friend puts two balls in a jar. Each ball is either red or green, and your friend chooses the color of each ball with a fair coin flip before putting it in. You come up, open the jar, and without looking can smell that there’s at least one red ball in it (but two red balls smell the same as one). What’s the probability that both balls are red?

There are three ways to explain the fact that you can smell a red ball. The first ball was red and the second green, the first was green and the second red, or both red. All are equally likely. That makes 1/3 chance both are red.

Same as last problem, but this time you reach in and pull out a red ball. What’s the probability that the remaining ball is also red?

Once you can smell are red ball, there are three explanations, as before. Between those three explanations, there are a total of 4 red balls. You pulled one out, and all those red balls were equally likely to be the one you grabbed. 2 of the 4 red balls come from the scenario where both balls are red, so there’s a 50% chance that the next ball pulled will be red.

Suppose that there are two barrels, each containing a number of plastic eggs. In both barrels, some eggs are painted blue and the rest are painted red. In the first barrel, 90% of the eggs contain pearls and 20% of the pearl eggs are painted blue. In the second barrel, 45% of the eggs contain pearls and 60% of the empty eggs are painted red. Would you rather have a blue pearl egg from the first or second barrel?

This was a trick question. They’re the same.

100 prisoners are to be executed, but they are given a chance to save themselves by playing a game. They will all stand in a single file line, so the prisoner in back can see all the other prisoners and the prisoner in front can see no one. The warden will then put a white or black hat on each prisoner’s head, choosing at random as he gets to the prisoner. Then the warden goes to the prisoner at the back of the line (who can see everyone else’s hat, but not his own) and asks him what color his hat is. He can respond only with either “white” or “black”. If he gets it right, he lives. This continues down the line. Each prisoner can hear the responses of all the prisoners who come before him. If the prisoners are allowed to get together and discuss strategy beforehand, how many of the 100 can be saved?

99, with a 50% chance to save the 100th. The first prisoner says “black” if he sees an even number of black hats on the other prisoners’ heads and “white” if he sees an odd number of black hats. He has a 50% chance to live. The next prisoner counts the hats in front and sees if he agrees with what the first prisoner says. If so, his hat is white, if not it’s black. He identifies his hat. The third prisoner does the same, including “seeing” the hat of the guy behind him, who he knows identified his hat color correctly. So on down the line.

There are eight pitchers of wine, one of which is poisoned. You have some lab rats to test the wine on. If a rat drinks any poison wine, it will die some time within the next 24 hours. How many rats do you need to use to design a test that is certain to discover the poisoned bottle in 24 hours?

Each rat is a bit, and distinguishing between eight states requires $log_2(8) = 3$ bits. For example, give the first rat pitchers 1,2,3,4; the second pitchers 1,2,5,6; the third 1,3,5,7.

Prove that there exist numbers x and y that are both irrational, but x^y is rational.

Recall (or prove) that $\sqrt{2}$ is irrational. Consider $\sqrt{2}^{\sqrt{2}}$. Is this rational? If so, we’re done. If it’s irrational, consider
$\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}$
Simplifying algebraically, this is
$\sqrt{2}^2 = 2$
which is rational. So if $\sqrt{2}^{\sqrt{2}}$ is irrational, then we’ve found two irrational numbers that give us a rational. Interestingly we don’t need to know whether $\sqrt{2}^{\sqrt{2}}$ is rational or not to complete the proof.

Suppose you cut a cone out of a sheet of paper. How does the time it takes the cone to fall to the floor when dropped from the ceiling depend on the radius of the cone?

For a reasonable cone made of reasonable paper dropped from a reasonable height, the cone will be at its terminal velocity for most of its fall, so we only need to consider the terminal velocity of the cone.

The weight of the cone scales with the area of the cone, but the wind resistance also scales with the area. The terminal velocity will then remain the same regardless of the radius of the cone. This actually works, btw.

Take a 6*6 chessboard and an 8*8 chessboard. For each, you’re allowed to make one cut through it along the lines between the squares. This will give you four pieces total. How can you make the cuts so those 4 pieces can be rearranged into a 10*10 chessboard? Try the same thing with other Pythagorean triples.

Draw the 10×10 board with the 8×8 superimposed in one corner and the 6×6 in the opposite corner. There’s a 4×4 overlap, which you can cut in half removing half from the 6×6 and half from the 8×8, and they fit in the empty corner of the 10×10.

I think this puzzle is impossible for Pythagorean triples besides multiples of 3-4-5.

### Prediction

May 2, 2010

Here is a physics problem from a book I was reading:

The year is 2100 and the pole vault record stands at 7.5m. Estimate the world record for the 100m sprint at this time.

This question is one of our favourites since it shows the power of physics to make the apparently most unlikely connections. Incidentally, both records would be held by women by this date – see Nature, Jan 2 1992.

The pole vault question is a classic, and a good one. The idea is that in pole vaulting you turn kinetic energy of running into potential energy of being high off the ground. If you know how much potential energy you had at the top of your pole vault, you know how much kinetic energy you had at top speed, and hence how fast you can run. Also, if you are Jacob Bronowski then pole vaulting is what separates man from the animals.

Solving the problem is a nice calculation. The potential energy per unit mass of the vaulter is her height $h$ times gravitational acceleration $g$ (PE = $gh$). The kinetic energy per unit mass is half the square of her velocity (KE = $1/2 v^2$). Setting these equal, we get

$gh = 1/2 v^2$

and solving for $v$

$v = \sqrt{2gh}$,

a result physics 1 students have seen many times when being asked about pennies dropping from the Empire State Building and such. The vaulter’s center of gravity starts out half a meter above the ground and rises to the height of the bar (or possibly just under). For $h = 7m$ and $g = 10m/s^2$ we get

$v = \sqrt{140m^2/s^2} = 12 m/s$

Using this as the speed of a sprinter, we get

$\frac{100m}{12m/s} = 8.3s$

Is this a good prediction? If the pole vault record really does advance to 7.5m, will the 100m time similarly improve?

Let’s do the calculation over using the current world records. If it doesn’t work for them, there’s no reason to believe it’ll start working in the future! The current world pole vault record is 6.14m and g = 9.8m/s^2, so we estimate the 100m record at 9.11s, or about 5% off from Usain Bolt’s record of 9.58s.

That’s pretty good. But would you be so impressed if you had done the same calculation in 1994? Sergey Bubka set the 6.14m pole vault record that year, and it has stood since. But in the same year Leroy Burrell set the 100m world record at 9.85s. Now we have about a 9% error. Still decent.

But hold on. I said this dude Sergey did the pole vaulting and Leroy did the running. Shouldn’t my calculation actually tell me how fast Sergey runs, not Leroy? Bubka was unusually fast for a vaulter, and could perhaps have run 10.1s. Now the error is 11%.

When you run 100m, though, you don’t instantly accelerate to a certain speed and stay there the whole time. You speed up to the 40m mark or so, and after 60m you start to slow down. Further, the run-up to a pole vault is much shorter than 100m, and you run more slowly than your best sprint speed because you’re carrying a giant pole. What the calculation is really going at is your speed right before takeoff. Bubka’s was about 9.9m/s right before planting the pole, compared to about 11m/s estimated with our cute physics problem. Ultimately, the error is more than 10%.

10% error is a lot if you want to make an estimate of the future world record, to place a bet on it, for example. And there’s a worse problem – our error goes the wrong way. Based on physics, we would expect the runner to be inefficient at converting all their kinetic energy to potential energy. Some gets lost in the bending of the pole, which isn’t perfectly elastic, and the vaulter still has some kinetic energy at the top of their flight because they move horizontally.

In general, we know that conversion of energy is not 100% efficient. So for a given speed, the vaulter should not quite make it to the calculated height, or conversely, for a given height, the vaulter should need more than the calculated speed. The authors point this out in their solution, estimating that the energy conversion might be 10% inefficient, so the real 100m time, give a pole vault height, might be 5% faster than predicted by the equations. This is backwards of reality, though. In the real world Sergey has less speed than what we calculated, not more. Evidently Bubka could do work after taking off from the ground, perhaps by pushing down on the pole.

The physics estimate for the 100m dash worked out pretty well, but only by accident. After all, if we believe this calculation, it predicts that Bubka should not have the world record for the pole vault – Usain Bolt should! In fact no one has ever held the world records for both pole vault and 100m (in the modern era, anyway. Maybe Tarzan did it.) We could repeat the calculation with the women’s world records (5.06m and 10.49s by Yelena Isinbayeva and Florence Griffith-Joyner) and again find that the estimated 100m time is too fast (10.0s). Or we could use data from the same person – Bryan Clay, the world’s best decathlete. Clay has run 10.36s and jumped 5.15m. His pole vault predict 9.95s for 100m.

In each case I’ve examined, the pole vault-projected 100m time is too fast for the real 100m time, and consistently around 5% too fast. In that case, maybe the pole vault record in 2100 is a good predictor for the 100m time in 2100, but not because of physics. Those two records just tend to track each other and progress simultaneously (with a fair amount of noise). We could go ahead and observe that the pole vault and 100m records tend to be related by some quadratic equation, and then use that equation to predict the future 100m time given the future pole vault. Toss out the physics, just note that it works and it’s good enough. Good idea or bad?

The problem is that we have no reason to believe that should continue to work, just because it has so far. Just because we can find some pattern in our past data doesn’t mean it will persist. Want an example? We already have one, provided in the original statement of the problem. The authors wrote, “Incidentally, both records would be held by women by this date,” a phrasing that makes them sound certain of it.

I’ve been around track and field for almost a decade. I can tell you, with utter assurance, that men are better at it than women, and they still will be in 2100. Men and women are physiologically different, and compared to an elite man, an elite woman, despite training with comparable intensity and dedication, is nowhere near as good.

So what led the authors to be so confident that women will hold the world records by 2100? The Nature reference is to a fantastically stupid letter titled “Will women soon outrun men?”, which predicted that female marathoners might become as good as male marathoners by 1998. They didn’t.

The discrepancy came up because the authors made a prediction by drawing a curve through the data about the past, and assuming the curve would continue the same way in the future. That was wrong. Women’s track and field, and especially women’s marathoning, is less mature than men’s. The women’s marathon was only added to the Olympics in 1984 (and steeplechasing in 2008). Few women were running marathons before then, and few were training for them seriously the way men do. Now, as more women join track and field and run professionally, the records can drop quickly. Men approached physiological barriers before women, so their improvement has been slower recently. This adds up so that when you draw a line through the times of the last 50 years for women and men, you predict that women will soon be faster.

Lines don’t keep going indefinitely into the future, though, even if you publish them in really fancy journals.

So now let’s go back to predicting the future 100m time based on the pole vault height. If the pole vault height gets 10% better, do you believe the 100m time will get 5% faster as our curve-fitting would likely predict? Unlike the estimates about men’s and women’s performances, it’s worth a close look. The difference is we have a physical model to back it up. We have an idea where it comes from. Those same equations we used at the beginning of the post predict that the pole vault will advance twice as much as the 100m dash.

We can’t predict the 100m time accurately with physics alone, because when we tried we were off by a lot. We can’t predict it accurately with curve-fitting alone, because it’s blind. When we combine them we may have a pretty decent predictor. What do you think?

References:
I got the world records from Peter Larsson’s web page Track and Field all-time Performances Homepage

Bryan Clay’s stats are from Wikipedia: Bryan Clay

The story about Bubka being especially fast is an anecdote I heard from a pole vault coach, who said Bubka was fast enough to be on the Russian national 4x100m team.

For an example of the velocity profile of elite sprinters in a 100m race, see Eriksen et. al. “Velocity Dispersions in a Cluster of Stars: How Fast Could Usain Bolt Have Run?” I think the title is a joke. Based on video analysis of Bolt’s 9.69s 100m world record in the 2008 Beijing Olympics, the authors predicted Bolt could run 9.61 +- .04s or 9.55 +- .04s if he had not started celebrating before finishing, depending on assumptions of their model. Bolt has now run 9.58s.

Bubka’s speed before takeoff is anecdotal from Wikipedia: Sergey Bubka.

The Nature article is not available unless you pay or have access from your university or something like that. It’s here but I haven’t read it because plenty of people have written similar things and they’re all worth your time to avoid.

The book of physics problems is “Physics to a Degree” by Thomas and Raine.

The video clip is from “Lower than Angels”, the first episode of Jakob Bronowski’s documentary “The Ascent of Man”.

### Shaking The Right Way

April 30, 2010

The other day I was working at a job – a real one, like grownups have. I used to think this job was boring. But things aren’t boring; they’re just what they are. People can be bored, but that’s their business. Don’t blame the thing!

I work at a place where they make widgets. One of the pieces for the widgets is a little, flat, plastic rod. There’s an assembly line with a robot that puts the rods in the partially-assembled widgets. But before that, the rods have to be fed into the robot one by one. The rods come from the rod factory in a big pile, though, and the robot can’t reach in a pick one out. We need a way to take the rods from a jumbled mess and feed them one-at-a-time into the robot.

To do that we dump the plastic rods in a bowl about a meter across. There’s a ramp winding up along the edge of it. We vibrate the bowl, and the rods march up the ramp and into the rod-eating widget-making robot. The bowl looks a little like this:

There was a library nearby when I was a kid that had a ramp like this in it. I always wanted to go to that library. I never read any of its books.

This is supposed to be a cut-away view of the side of the bowl. The ramp is on the inside of the bowl, angled up slightly to keep the rods from falling off.

When we turn it on, the bowl starts vibrating fast enough that it’s just a blur (60 Hz seems plausible). And the rods walk their way up the ramp at a very even pace. The rods will go up the ramp whether there are one thousand or just one of them in the bowl (although if there are lots of them some will get pushed off the ramp, fall to the bottom, and start over).

This is really crazy! How do the rods go up the ramp, not down? Things are supposed to go down, generally speaking. It’s pretty freaky to watch a single rod climb right up this long winding ramp as the bowl vibrates. The bowl doesn’t spin. It doesn’t visibly tilt. It works for different sizes of rods and even for a penny (I think. I haven’t found an opportunity to slip one in yet, but I’m pretty sure it’ll work for a penny. Not a marble, though.)

I asked the technician who works with the bowl, and he said he wasn’t sure, but that the rods don’t always go up. The people who make the bowl can make some adjustments to it, and then the rod will go up slower, then stop, then march their way back down as the workers keep adjusting.

I couldn’t figure it out, so I asked my boss, who’s mechanically-minded, and we worked out a theory. In short, it goes like this: the bowl can vibrate in two different ways. It can bob up and down, and it can rotate back and forth. It can move a couple of millimeters in each direction. The bowl makes the rods go up the ramp by doing both of these at the same time, and we can adjust the speed of the rods up the bowl’s ramp by adjusting the phase lag between the two oscillation modes.

Draw a little dot on the side of the bowl. Since a few millimeters (the amplitude of the bowl’s vibrations) is small compared to a meter (the bowl’s diameter), for any given point vibrating the bowl by rotation is the same as shaking back a forth horizontally in the direction tangent to the edge of the bowl. So we’ve got a sine wave motion horizontally.

Close-up of one part of the ramp. The red arrows show the motion of the the red dot, although any other point on the ramp would move the same way.

If the bowl instead bobs up and down, the motion of the dot is like this:

Same as last time, but the bowl bobs up and down.

Now make the bowl rotate and bob simultaneously. There are different ways we could do this. Assuming we give both modes the same frequency (easier to engineer, I’d think), then we can describe the way these modes are combined with a single parameter – the phase lag between them. When the phase lag is zero the bowl moves all the way forward at the same time it’s all the way up, and all the way back at the same time it’s all the way down. The red dot traces out a diagonal line, like this:

Moving forward/backward and up/down in sync.

If the phase lag is 180 degrees, the diagonal line switches directions, like this:

But if the phase lag is 90 degrees, the dot instead traces out a circle. Make it -90 degrees and the circle goes the other direction.

Combining back/forth and up/down just so, we get a circle.

We can also make the circle go the other way, if we want.

This is just right for moving a rod up a ramp. Remember that when something moves in circle, its acceleration points towards the center of the circle. So imagine the ramp shaking this way when it’s at the bottom of the circle. The ramp is accelerating up, pushing into the rod. That means there’s a big normal force on the rod, and a big normal force means more friction. To take advantage of this high friction, the ramp should move forward, pushing the rod ahead in space.

The CCW circle moves forward at the bottom of its loop (green arrow). The ramp is accelerating up (blue arrow), jamming into the rod and carrying it forward along with it.

Now the red dot has reached the high point of the circle. It’s accelerating down. That means it’s falling away from beneath the rod, so the normal force goes down. If the acceleration is high enough, the ramp may even pull away from the bottom of the rod completely (I’m not sure whether it actually does this). Now the friction is low, and the ramp can slide backwards, leaving the rod where it is. The net result is that the rod is further along the ramp at the end of the cycle than at the beginning.

Same circle, but now the ramp is at the top of its motion. The rod will get left behind as the ramp pulls away from underneath.

This really works, even without a fancy industrial bowl. I did it just now. I found the longest hardback book in my room (The Feynman lectures) and an appropriate rod substitute (a Rubik’s Cube), and I easily sent the cube uphill on the tilted book by rotating circularly one direction with my hands, and brought it back down by rotating circularly the other direction.

The book was still pretty short, but I have a longer flat, mobile surface – a white board. I’m a bit too clumsy to shake it in a circle with my hands, though. But I have a bicycle…

I duct taped my white board to the pedal of my bike in an attempt to recreate the circular motion I posited for the ramp. I propped the other end of the white board up against a table,

This didn’t work well. The board was tilting during the cycle because the far end, leaning on the table, wasn’t going up and down the same way as the near end. I tried propping the table up at an angle in hopes of keeping the white board close to flat, but that didn’t help much.

Time to recruit the neighbors. It was 11:20 PM so my neighbors, who are college students, were awake and drunk enough to agree to anything that sounded weird or stupid. With a human at the other end of the white board, I could keep the board pretty much flat, or pretty close to tilted at a constant angle as it went around.

The results were that as long as I kept the white board flat, my Rubik’s Cube would go forward and backward the way I predicted, but I couldn’t get it to climb any significant hill. I tried switching out the cube for a high-friction rock-climbing shoe, but that still didn’t make much progress. I conclude the bowl at my job relies on high-speed, high frequency vibrations, the opposite of my bicycle.

Finally, in order to be a good scientist I needed a more objective test of my theory. I was able to get my conveyor belt to work roughly, but I already knew the result I wanted. Maybe I was subconsciously tipping the book/board the direction that I wanted things to go?

To test this, I called a friend and asked him to replicate my experiment with a book and a penny, without telling him what I expected to happen. He reported the same result! We can indeed make things move forward or backward, even up slight inclines, just by shaking the right way.

### New Problems

March 19, 2010

Here are some nice problems I’ve run across recently. They’re from word of mouth, the internet, and books. Only one of them is a “trick” problem. The problems are pretty much unrelated.

Do these first two as fast as you can:

• 999 * 1001
• A family has five children. What’s the probability that at least three of them are girls?

You have two glass balls and are in a 100-story building. There’s a window on each floor. When you drop the ball out a window, it may or may not break, depending on how high you are. There’s a certain floor that is the transition from not breaking to breaking, so that if you drop it from that floor or above, it will break, and below that floor, it will not. This floor could be any of the floors from one to one hundred with equal probability. What is the fewest number of drops you need to make to be sure you accurately locate the transition floor?

Your friend puts two balls in a jar. Each ball is either red or green, and your friend chooses the color of each ball with a fair coin flip before putting it in. You come up, open the jar, and without looking can smell that there’s at least one red ball in it (but two red balls smell the same as one). What’s the probability that both balls are red?

Same as last problem, but this time you reach in and pull out a red ball. What’s the probability that the remaining ball is also red?

Suppose that there are two barrels, each containing a number of plastic eggs. In both barrels, some eggs are painted blue and the rest are painted red. In the first barrel, 90% of the eggs contain pearls and 20% of the pearl eggs are painted blue. In the second barrel, 45% of the eggs contain pearls and 60% of the empty eggs are painted red. Would you rather have a blue pearl egg from the first or second barrel?

100 prisoners are to be executed, but they are given a chance to save themselves by playing a game. They will all stand in a single file line, so the prisoner in back can see all the other prisoners and the prisoner in front can see no one. The warden will then put a white or black hat on each prisoner’s head, choosing at random as he gets to the prisoner. Then the warden goes to the prisoner at the back of the line (who can see everyone else’s hat, but not his own) and asks him what color his hat is. He can respond only with either “white” or “black”. If he gets it right, he lives. This continues down the line. Each prisoner can hear the responses of all the prisoners who come before him. If the prisoners are allowed to get together and discuss strategy beforehand, how many of the 100 can be saved?

There are eight pitchers of wine, one of which is poisoned. You have some lab rats to test the wine on. If a rat drinks any poison wine, it will die some time within the next 24 hours. How many rats do you need to use to design a test that is certain to discover the poisoned bottle in 24 hours?

Prove that there exist numbers x and y that are both irrational, but x^y is rational.

Suppose you cut a cone out of a sheet of paper. How does the time it takes the cone to fall to the floor when dropped from the ceiling depend on the radius of the cone?

Take a 6*6 chessboard and and 8*8 chessboard. For each, you’re allowed to make one cut through it along the lines between the squares. This will give you four pieces total. How can you make the cuts so those 4 pieces can be rearranged into a 10*10 chessboard? Try the same thing with other Pythagorean triples.

### Flip It One More Time

March 10, 2010

A couple weeks ago I posted about flipping an unfair coin. There, I imagined a coin that came out of a flip the same way it went in 51% of the time. The coin didn’t prefer heads or tails in general, but if it started out heads it was slightly more likely to stay heads, and likewise for tails.

If you flip that coin once, it’s not bad – just a little bit away from fair. If you flip it twice, it’s so close to fair you’d have to flip do tens of thousands of repetitions of double-flips to see they were biased.

But what if instead of 51% chance to land the same way, the coin had 90% chance? Then how many times would you have to flip it to get pretty close to fair?

The trick to this is not to try to calculate all the strings of length six, for example, and see what the probability is for heads on the sixth toss, and then go to seven if six wasn’t good enough. Instead, flip it once, and make the second flip act on the uncertain state.

Here’s what I mean: We’ll write heads as a column vector like this:

$\left( \begin{array}{c} 1 \\ 0 \end{array}\right)$

and tails like this:

$\left( \begin{array}{c} 0 \\ 1 \end{array}\right)$

For an uncertain state, where we haven’t looked at the coin yet, we write:

$\left( \begin{array}{c} P_H \\ P_T \end{array}\right)$.

Flipping is then the symmetric operator that takes us from the certain state to the 90-10 state. This is

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right)$

Flipping a coin that started out heads corresponds to the equation

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right) \left( \begin{array}{c} 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} .9 \\ .1 \end{array}\right)$

To flip twice, act with the operator again.

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array} \right)\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right) \left( \begin{array}{c} 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} .82 \\ .18 \end{array}\right)$

To flip $n$ times, evaluate

$\left( \begin{array}{cc} .9 & .1 \\ .1 & .9 \end{array}\right)^n \left( \begin{array}{c} 1 \\ 0 \end{array}\right)$

Intuitively, one eigenvector of that operator is the 50-50 state. Since the operator is symmetric, if we begin with complete uncertainty, we must still have complete uncertainty after flipping. Evidently, the eigenvalue is one.

The eigenvectors of a symmetric operator on a real vector space are orthogonal1, so the other eigenvector is

$\left( \begin{array}{c} .5 \\ -.5 \end{array}\right)$,

which is not very meaningful by itself, but forms a basis along with the first eigenvector. Its eigenvalue is 0.8.

We can break any heads/tails probability down into a sum of these two eigenvectors. The first eigenvector is the fair state. The second eigenvector is what takes us away from the fair state. When its component is positive, we lean towards heads, and the higher its component the more we lean towards heads. When the component of this second eigenvector is negative, we lean towards tails.

The pure heads state can be written in the eigenbasis by

$\left( \begin{array}{c} 1 \\ 0 \end{array}\right) = \left( \begin{array}{c} .5 \\ .5 \end{array}\right) + \left( \begin{array}{c} .5 \\ -.5 \end{array}\right)$.

Flip $n$ times, and the component of the first eigenvector is unchanged because its eigenvalue is 1, but the second eigenvector’s component dies away exponentially, because it’s multiplied by 0.8 each time. That leaves us with

$\left( \begin{array}{c} .5 + .5*,8^n \\ .5 - .5*.8^n\end{array} \right)$.

If we want to probability for heads to be within $\epsilon$ of 50%, we know

$\epsilon = .8^n$

and so

$n = \ln(\epsilon)/\ln(0.8)$

We’d have to flip 21 times to get down to 51%. We can see that the second eigenvalue, the one that was .8 here, comes from .9 – .1. In general, if the chance to stay what you are is $p$, then this second eigenvalue will be $2 p - 1$. If $p<.5$, then this eigenvalue is negative, and the component of the second eigenvector will switch each flip. We'll go from biased towards heads, to biased towards tails, and back again, flip-flopping with each coin toss.

1 if $A$ and $B$ are two eigenvectors of a symmetric operator $M$ with eigenvalues $\alpha$ and $\beta$, then

$AMB = A\beta B = \beta AB$

by acting with $M$ on the right. Since $M$ is symmetric, it can also act on the left, giving

$AMB = \alpha AB$.

These expressions are the same, so

$\beta AB = \alpha AB$

which implies

$AB = 0$

as long as $\alpha \neq \beta$. If they are equal, we have a two-dimensional eigenspace, and can simply choose two orthogonal vectors inside it using Gram-Schmidt. Either way, once you find the first eigenvector, whatever is perpendicular will be another one.

Also, there may be complex eigenvectors, but there must be an even number of them, so once we found one real eigenvector we knew there was another.

### Flip Worse

February 25, 2010

Here is a story about being wrong. Lots of times. You know, like a new puppy when it’s trying to guess where it’s okay to pee.

A couple days ago I posted about flipping an unfair coin of a special type. This coin does not favor heads or tails. Instead, it favors its previous toss. If it was heads this time, it has a 51% chance to be heads again next time, and likewise for tails.

In the previous post, I said that if you flip and take the best 2-out-of-3, you cut the bias down by a factor of four. That is, if the coin is heads before you flip, it would have only a 50.25% chance (roughly, since this was a first-order calculation) of heads winning two-out-of-three. I posted that solution, but thought I needed a follow up because although I calculated the answer, it still wasn’t clear to me. I thought there ought to be some nice way to visualize it, so I was trying to draw some different sorts of trees that illustrated the flips and their probabilities.

What I found was that my original answer was plain wrong. In addition to the tree, or hopefully with its help, I was curious about what happens when you play 3-of-5, 4-of-7, etc. I hadn’t calculated these yet, but not having an obvious method at hand I figured the fastest way to get started was to find the answer using my computer to simulate coin tosses, then figure out why it worked.

Once I wrote such a simulation, I was shocked to find that it said that when I do best 2-out-of-3, heads won roughly 51% of the time. I thought something must be wrong with the simulation, but I didn’t see anything. So I plugged in the exact expression for the odds of heads winning into the google toolbar (you know google is a fast and easy calculator, right?) and found 51% precisely. Then I wrote my expression down on paper to see why it should work. I factored out a 51%, and saw I had the square of (.51 + .49) looking at me, confirming without long multiplications that the answer should be 51%.

Now I started thinking about the binomial theorem and how I could use induction to prove this was always going to work, but I was distracted by the thoughts of what an idiot I was.

“Oh man,” I thought. “I was an idiot not to check up a little bit on my other calculation before I posted them on the blog.” For a moment I thought the second- and higher-order corrections were somehow canceling things out, but that makes no sense. So I went back to my original post and found the mistake. I had written that if you stay on the same side when flipping with probability $1/2 + \epsilon$ and flip to the other with probability $1/2 - \epsilon$, then the probability of a given sequence of tosses that switches $n$ times and doesn’t switch $m$ times to first order in $\epsilon$ is

$\frac{1}{2^{m+n}} + \frac{m-n}{2^{m+n}}*\epsilon$,

which is wrong. It’s actually

$\frac{1}{2^{m+n}} + \frac{m-n}{2^{m+n-1}}*\epsilon$.

I felt really stupid about this one, because it wasn’t wrong due to a simple calculation error. It was wrong because the first time I did it I just wrote it down based on what I thought it ought to be, and didn’t even bother to do the calculation (which I snidely left “as an exercise to the reader”).

Still, even with this correction, it means that playing 2-out-of-3 should cut the bias in half, not leave it alone the way my simulation and google calculation said.

Still confused, I went back to the simulation, and now saw the error. I was giving tails at 49% chance all the time, not giving the coin a 49% chance to flip as I had thought. So I fixed that, and the program still didn’t seem to work. It still said 51% for 2-out-of-3, and for longer games.

I went back to google toolbar and plugged in the exact expression one more time. There are four ways for heads to win 2-out-of-3, and their probabilities are

$P(HHH) = .51*.51*.51$

$P(HHT) = .51*.51*.49$

$P(HTH) = .51*.49*.49$

$P(THH) = .49*.49*.51$

The sum is $.505002$. Okay, great. That confirms the revised first-order estimate. I just wrote down the probabilities wrong before.

I still had the simulation to take care of, since it was predicting something different than my calculations, but at this point I realized that the entire process was completely useless. There’s in fact a much better way of achieving what I wanted – a more fair coin toss. Just toss the coin twice, and take the second toss.

The first toss is a little unfair. It’s biased by something like 1%. That means that after you flip the coin, it has a little bit of memory of where it was the previous toss. What I mean is, flip the coin a million times. go to some flip in the middle, and see that it’s heads. Was the previous toss heads or tails? You don’t know, but heads is just a little bit more likely than tails for the previous toss. How about two tosses ago? Well, if you remember your father, but just barely, your memory of your grandfather will be even dimmer than that.

Specifically, if coin starts out heads with this 51% bias we’ve been talking about, flip it twice and the second toss has a 50.02% chance of being heads. The third toss is 50.0004%. Flipping two or three times and taking that last toss easier and better; the the stuff about best-2-of-3 is pointless. Still, it bugged me that I wasn’t very clear on my the answer to my original question.

Back to the simulation. Knowing it had to be in there, I finally saw another error. I was only generating one random number for three coin flips. My second and third flips were the same as my first flip every single time I ran the simulation. Fortunately, computers can’t get mad at you. If they could, I’m pretty sure my netbook would be pissed at being asked to use its limited resources to generate several million completely useless random (kind of) numbers. So I fixed the code. Finally the simulation, exact calculation, and approximate calculation converged. It appeared I had the answer.

Does it seem strange that throughout this process of being repeatedly wrong, I was readily willing to turn my back on the answer I had been sure of just a few moments before? Maybe this means I’m sure of things too easily. No, not “maybe”. I’m sure it does.