Monday, November 26, 2007

Algebra Puzzles!

As if the word "algebra" wasn't off-putting enough, my first two problems are normally formed using trains, evoking the stereotypical headache-inducing algebra problem ("One train leaves Tulsa going northeast at 60mph, the other..."). I've replaced the trains in an attempt to make the problems more attractive to the few readers I haven't already alienated with this series of posts.

Man in a Tunnel

A man has traveled 1/4 of the way through a tunnel when he notices a giant killer bunny hopping at a constant rate behind him, some distance outside of the tunnel. Whether he continues forward as fast as he can, or turns around and runs as fast as he can, he will exit the tunnel and miss being devoured by the bunny with zero time to spare at either end. How much faster is the mutant bunny than the man?

Supersonic Bee

Two giant killer bunnies, initially separated by a distance of 25 miles, are both hopping at a rate of 100mph, directly towards one another. A supersonic bee begins on one bunny's nose, and flies back and forth between that bunny's nose and the other's at a rate of 800 miles an hour until the bunnies ultimately collide with each other and the bee. At the point of impact, how far will the bee have traveled?

Heaven and Hell

A giant killer bunny dies and finds itself given three unmarked doors to choose from. One leads directly to heaven, one results in a 1-day stay in hell, and one results in a 2-day stay in hell. If the bunny chooses either of the "hell" doors, it will carry out its hell sentence and return to the same three doors, which at that point will have been randomly shuffled, and the bunny gets to choose again. What is the average time it takes a giant killer bunny to get into heaven?

Man in a Tunnel
SOLUTION

I find this problem interesting because it feels as though you're not given enough information to solve it. How fast can he run? How far away is the bunny?

More data would only be helpful insofar as it would make the problem easier to visualize than by using algebraic variables. So let's say it takes the man 1 minute to reach the end of the tunnel through which he entered. At this rate, it would take him 3 minutes to reach the far end of the tunnel, since it's three times as far. Adding the times for these segments together means it would take a total of 4 minutes for this man to run from one end to the other. How long would it take the bunny to cover the same distance? It would take the bunny 1 minute to reach the near end and 3 minutes to reach the far end, so 2 minutes to cover the entire distance of the tunnel. The bunny is twice as fast as the man.

Supersonic Bee
SOLUTION

Solving this problem hinges on realizing how simple it really is. If it actually required adding together all the successively decreasing distances between the bunnies, solving it would not be fun or interesting, and even most nerdy math types wouldn't bother.

All you need to know is speed = distance / time (or distance = speed x time). The bee's speed is 800mph. How long will he be flying? Traveling toward each other at 100mph, the bunnies can each cover 12.5 miles in 1/8 of an hour. So the bee travels at 800mph for 1/8 of an hour: 100 miles.

Heaven and Hell
SOLUTION

Solving this by algebra is more or less straightforward, but it's still very easy to get lost.

Call the answer - the average time it takes a bunny to get into heaven - X. X is the average of three values: the expected times for each door. Door #1 has an expected time of 0. But how can we calculate the others?

If the bunny walks through door #2, it spends 1 day in hell and starts over again. After that 1 day, it can then expect to wait the average time, X. So the total expected time for door #2 is 1 + X. The same reasoning gets you 2 + X for door #3.

Since X is the average of the three values, you need to add those values and divide by 3. Putting all this together you get the equation:

X = ( [0] + [1+X] + [ 2+X] ) /3

Some simple equation manipulation gets you 3X = 3 + 2X and finally X=3. The average time it takes a giant killer bunny to get into heaven is 3 days.

Monday, November 19, 2007

More Puzzles

Back by popular demand no demand whatsoever:

The Monty Hall Problem

Three Doors. One of them is good (it leads to underwear models, funnel cake, etc.) and two are bad (alligators, doctoral theses). You pick one, but before we show you whether the door you picked is good or bad, we generously eliminate one of the bad doors from the other two. Now it's time to make your final decision: Switch to the only remaining door, or stay with your original pick. Should you switch or stay? Does it matter?

Coin Flip Game

You and I flip a coin at the same time, and continue flipping at the same pace until the game is over. You win as soon as you get two heads on consecutive flips. I win as soon as I get a head and a tail, in that order, on consecutive flips. (We tie if both things happen on the same flip.) Who, if anyone, has better odds?


Unlike last week, intuition initially suggests simple and uninteresting answers to both puzzles - "it doesn't matter which door" and "no one has better odds", respectively. Of course, those intuitive answers are not correct.

The Monty Hall Problem
SOLUTION

The intuitive (but wrong) answer, "it doesn't matter", appears to make sense because (1) there are now just as many good doors as bad doors, and (2) you still don't know if your original pick was good or bad. (1) and (2) are both correct assumptions, but the actual answer is that if you switch doors, you'll pick the good door twice as often.

Think of it this way: When you originally picked your door, you had a 1/3 chance of being right. Nothing has changed that fact. When I eliminated a bad door, I was able to do so independent of whether your original pick was good or not. So now there's still a 1/3 chance that your original door is good, and a 2/3 chance that the good door is somewhere else. But "somewhere else" now consists of one option instead of two.

Coin Flip Game
SOLUTION

The intuitive answer is that the game is fair, because in any two consecutive flips, we both have a 25% chance of success, right? In reality, my odds of winning on a given flip eventually tend toward 50%, and your odds of winning on a given flip tend toward just over 19%. The mathematics turns out to be surprisingly complicated, involving patterns related to the Fibonacci sequence and the golden ratio. Figure that out on your own if you're so inclined. If you're not, here's a partial explanation of why the game isn't fair.

What are the chances of success on a given round? If your last flip was heads (good news for you), it's 50%. If your last flip was tails (bad news for you), it's 0%. Same for me. This logic holds as far as the second round. But if it's a later round and we're still playing, that means that nobody won on the previous round, and we can deduce a little more:

You didn't win on the previous round, and you needed HH, so your previous two flips could have been HT, TH, or TT. That's: one scenario in which you might win on your next flip, and two in which you can't.

I didn't win on the previous round, and I needed TH, so my previous two flips could have been HH, TH, or TT. That's two scenarios in which I might win on my next flip, and one in which I can't.

When you consider more and more previous flips, it gets increasingly complicated and the odds skew more and more in my (HT) favor. Here is a partial table of the odds of getting the second of two desired flips on a given round.

For example, if we make it to the 6th round of flipping (meaning you haven't yet made two consecutive heads) then there is a 38.4% chance your most recent (5th) flip was heads, and thus a 19.2% chance you'll get your second consecutive head on that 6th flip.

Monday, November 12, 2007

Puzzles

A while ago I came across a website purporting to list Google job interview questions, all of the brain teaser variety. I thought some of them were unlikely to appear in an actual interview as they've been kicking around for quite a while, but it revived in me a fascination with puzzles and brain teasers, and got me thinking about the different types and qualities of puzzles there are. I've decided to make something of a Monday tradition of presenting different puzzles and their solutions, for at least the next several Mondays.

Boy Country

In a country where people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Crazy Guy on a Plane

100 airline passengers are waiting to board a plane. They each hold a ticket to one of the 100 seats on the flight. (It doesn't matter, but imagine the first person has ticket #1, and so on.) The first person in line is crazy, and will select a seat at random, possibly even his own. Every person after him will sit in their own seat if it's available, and pick a random one if it isn't. You are the 100th person. What are your chances of getting your own seat?


These puzzles are both fine examples of what puzzles should be, in my opinion, because they fit three important criteria:
  • The solution is interesting, because it's not what you expected and/or simpler than you expected
  • Finding the solution requires only reasoning ability, not knowledge of higher mathematics
  • It's not "tricky" in the sense that the solver has to make any less-than-obvious assumptions ("you can melt the ice", "turn the sweater inside out", etc.)
Boy Country
SOLUTION


Using simple reasoning and no mathematics at all, you should be able to convince yourself that this birthing strategy does nothing to alter the natural gender ratio of 50/50 (or 51/49, according to some sources). Families have children. Some are girls, some are boys. Some families continue having children, some don't. As more babies are born, some are girls, some are boys. And so on.

If you're not convinced, consider 64 families. On average, 32 firstborns are boys, and 32 firstborns are girls. Some nine months or more later, 32 of those families give birth again: 16 have boys, 16 have girls. Next round: 8 boys, 8 girls, etc. The mathematics gets a little sticky when you get down to that last baby, but by then you have 63 boys and girls each to back up the 50/50 argument, and on a larger scale it's even more convincing.

Crazy Guy on a Plane
SOLUTION


For any problem involving an arbitrarily large number, it's always best to imagine it on a small scale first and see if any predictable patterns emerge. If it's just you and the crazy guy occupying 2 seats in a Cessna, your chances are 50%. Add one more person. Now the crazy guy has three options: his own seat ("good"), yours ("bad"), or the other person's seat. If he picks the other person's, then that other person has two options: the crazy guy's seat ("good") and yours ("bad"). Still 50%. Now consider the 100 person version. Crazy guy has one "good", one "bad" and 98 other options. If he sits in, say, passenger 57's seat, then passengers 2-56 get their own seats, and #57 has one "good", one "bad", and 42 other options. Any way you cut it, the odds will be 50%.

Friday, November 9, 2007

Main Event at Tokyo DisneySea

Yes, that's DisneySea, right across the street from Tokyo Disneyland. Every Disney park features a nightly show that can be seen from a large area of the park. I saw the one in Anaheim in 2005 and was quite impressed, but I'd say this one was as good or better. After a brief introduction by a Japanese-speaking Mickey, the show presented an embodiment of the Spirit of Water, then Fire, followed by something of a mating ritual between the two. In addition to the spectacle, I just appreciate the difference in storytelling style, focusing on harmony in nature, rather than following the kind of "hero vanquishes villain" narrative I'm used to.

Video 1 (1:11)
The Spirit of Fire, a metallic and tentacled seabeast that emits flames from its entire structure.


Video 2 (1:05)
Fire and Water, "flirting".


Video 3 (:54)
The marriage of Fire and Water.