A good brainteaser is hard to find

I enjoy a good brainteaser, one that you really have to concentrate on and with enough revelations built in that make the end result a satisfying accomplishment. Here are some of my favorites. I made the answer text white so that you can’t see it unless you highlight (click and drag) over it.

Question: If you place 3 points randomly on the perimeter of a circle, what is the probability that all 3 lie on the same semi-circle?

Answer: 75%. The trick to the circle one is to recognize that any two points on the perimeter of a circle will be on the same semi-circle, even if they are very nearly exactly opposite each other on the circle. The third point is where the action is. Consider a couple of corner cases. If, for example, the first two points fall at the same exact spot, then they can be considered one point. Adding a third point is like considering the two point case, which we know has a 100% probability of forming a semi-circle. Now, suppose the first two points wind up almost exactly across from each other. These two points then define the semi-circle that the third point has to land on. Since a semi-circle is 50% of the circle, the probability of the third point landing in the semi-circle is 50%. What if the first two points wind up a quarter of the perimeter of the circle from each other. Then the third point can fall between the first two, or a quarter of the perimeter on either side of the arc formed by the first two and still form a semi-circle. That’s three quarters of the circle, or 75%. You’re basically done. If you move the first two points from very close together to nearly across from each other on the circle, you should notice that the length of circle the third point can land on decreases linearly from 100% of the circle to 50%. Thus, you can take the average of these two and deduce that the final probability is 75%. Cool, huh?

Question: If you break a stick randomly in 2 places, what’s the probability that the three pieces can form a triangle? (The ends of the sticks must be touching. No extra stick poking out at the corners!)

Answer: 25%. The triangle one is a little trickier, I think. First, you have to recognize that a triangle can be formed if no one side is longer than the sum of the lengths of the other two sides (a + b > c for any assignment of a, b, and c). You are breaking the triangle in 2 places. Consider the corner cases. Let’s say the first break is so close to the left of the edge of the stick, that it’s basically still the same size stick + one tiny piece. You can’t break the stick again near the left edge because the two small pieces will be smaller than the length of the remaining big piece even when added together. You would have to break the stick in a small region just past the middle of the stick, closer to the right side, in order for the length of the tiny piece + the remaining left side piece to be longer than the remaining right side piece. The probability of that happening is nearly 0%. Now suppose the first break is very close to the middle of the stick, but still on the left half of the stick. You can break the stick pretty much anywhere on the remaining right side piece and get a triangle, but you can’t break it on the left side piece or the right side piece will be too big. In this case, the probability that the right side piece gets broken is basically 50%. As with the circle brainteaser, you should be able to convince yourself that the part of the stick that the second break can occur increases linearly as the first break moves from the edge of the stick to the middle. Thus, the final probability is the average of the two corner cases, or 25%. You should note that to aid visualization I’ve been referring to the “left” edge and “right” edge, but because of the stick’s symmetry, the logic holds whether you’re considering the first point with respect to the left edge or the right edge, so this doesn’t change the answer.

Question: You have 25 horses and a 5-track racetrack. You want to figure out which are the top 3 fastest horses (ie who is #1, #2, and #3). How many heats do you need to hold in order to figure it out? Assume that the horses races consistently, ie the fastest horse will always beat the 2nd fastest, the 2nd fastest will always beat the 3rd fastest, and so on. There are no stopwatches.

Answer: The answer is 7. Hold 5 races of 5 horses (you probably got at least that far), call them Heats 1-5. Then race the winners from each of those 5 heats, call this Heat 6. The winner of Heat 6 is the fastest horse. But you’re not done yet. It may be the case that the 2nd and 3rd fastest horses were all in the same heat as the fastest horse. So, you have to race the 2nd and 3rd fastest horses from Heat 6 with the 2nd and 3rd fastest horses from the 1st-fastest-horse’s first heat. You also have to include the 2nd fastest horse from the 2nd-place-of-Heat-6’s first heat. Those 5 horses are racing for 2nd and 3rd place in Heat 7.

Question: There are 100 seats on a plane and 100 people. Each person is assigned to a specific seat with a ticket. They board the plane one at a time in a uniformly random order. One guy has lost his ticket and decides just to sit in a random seat. Otherwise, each person sits down in their assigned seat. If someone finds that their seat has been taken by the guy who lost his ticket or someone else, they decide to just sit in another random seat. The question is what is the probability that the last person on the plane will sit in their assigned seat?

Answer: The easiest way to think about this is as a game with two ways to end. If the guy who lost his ticket (or someone forced to sit in a random seat) sits down in the last person in line’s seat, the game is “lost” as the last person will have to sit in a seat other than what’s on his ticket. If the guy who lost his ticket happens to sit in the seat that he actually belongs in just by chance, then the game is “won.” You can consider each person sitting as a round. Each round, only one seat wins the game and only one seat loses the game, all the other seats just continue the game for another round because someone will have to sit randomly. The symmetry of the game continues even until the final case involving just two seats, one winning, one losing. Since every round has an equal probability of the game winning or losing, the probability must be 50%.

Question: Suppose you are waiting at a bus stop. There are two lines that both take you to where you want to go. The buses on one line come every 15 minutes. The buses on the other line come every 30 minutes. You have no idea what the schedules are but know that they are always on schedule. So, it may be the case that the 15-minute bus schedule is 9:01, 9:16, 9:31… and the 30-minute bus schedule is 9:02, 9:32, 10:02… What is the average amount of time that you will have to wait for a bus?

Answer: This one’s kind of mathy. You have to consider a few cases.

First you have to convince yourself that if the 30-min bus comes reliably every 30 mins but you don’t know when, then there’s a 50% chance that it’s coming before 15 mins from now and 50% chance that it is coming after 15 mins from now. If the 30-min bus is not coming for over 15-mins, then the 15-min bus sets a lower bound on how long you have to wait. In this case, you are just waiting for the 15-min bus. On average, you will wait 7.5 mins (the average of 0 if you just made it and 15 mins if you just missed it) for the 15-min bus.

If the 30-min bus is coming before 15 mins from now than you can treat that case as though there were two 15-min buses whose schedules you don’t know. So, the solution = 50%*7.5 (from above) + 50%*(Average of 2, 15-min bus case). So what’s the average of the 2, 15-min bus case? One 15-min bus comes an average of 7.5 mins from now as we discussed. Now, there’s a 50% chance that another 15-min bus comes before 7.5 mins. If it comes after, you’re on the first bus by the time 7.5 mins rolls around on average. If it comes before, then it’s coming anywhere between 0-7.5mins from now, with an average of 3.75 mins. Putting those all together gives you .5*7.5 + .5*(.5*7.5+.5*3.75) = 6.5625 minutes on average. Not bad.

Question: A group of people with assorted eye colors live on an island. They are all perfect logicians — if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
The Guru is allowed to speak once (let’s say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

“I can see someone who has blue eyes.”

Who leaves the island, and on what night?

Answer: As with many of these brainteasers, the easiest way to solve this is to consider a simpler case. Let’s consider the case where there are 2 people with brown eyes and 1 person with blue eyes and the guru. The guru says she sees someone with blue eyes. Remember the islanders are all perfect logicians so think about what they’re thinking. The brown-eyed people each see the one person with blue eyes and think, “I see one person with blue eyes too, but maybe I also have blue eyes.” The blue-eyed person thinks, “I don’t see anyone with blue eyes. I must have blue eyes.” So, the blue-eyed person deduces her eye color and leaves that night. The 2 brown-eyed people stare at each other and have no idea if they also have brown eyes, or if they have red eyes, or green or whatever, because the guru has not told them about any other eye color. They never leave the island!

Now consider the case where there are 2 brown and 2 blue. The blue each see one other blue person and think “Oh, the guru may be talking about that person. I still don’t know what color eyes I have.” So, they stay on the island that night. On the second day, they see that the other blue person has not left. They think to themselves, “ah, they did not leave because the rest of us are not all brown-eyed. I see two brown-eyed people, so the other blue-eyed person must be me.” Both blue-eyed people leave that night and the brown-eyed people have to stay.

Now consider the case with 2 brown and 3 blue. Each blue-eyed sees 2 blue-eyed people. They see no one leaves after the first night. Now, no one leaves after the second night. Since they are perfect logicians, they realize that if there were only two blue-eyed people they would’ve both left on the second night. Since no one left and because they see there are 2 brown-eyed people, each one deduces that they have blue eyes and leaves on the third night. The brown-eyed people have to stay. Notice that the brown-eyed people never leave the island prematurely because they always see one more blue-eyed person than the blue-eyed people see. So, up until the day all the blue-eyed people leave they are thinking they will try to leave, it just happens that they are thinking they will leave a day later.

This logic continues if you keep adding people. With 100 blue and 100 brown, all the blue-eyed people leave on the 100th night. The brown-eyed people have to stay because even though 99 other people have brown eyes, they may have a different eye color.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s