The Hard Problem
This problem is so named because... well... it is hard. So, if this is your first read-through, I recommend skipping it! Ok, now for the problem statement: There are a countably infinite number of mathematicians in a room. Each has a black or white hat placed on his head. Color selection is random. Each mathematician can see the color of everyone else's hat, but not his or her own. At the same moment, with out communicating with each other, all must guess the color of his or her own hat. What strategy could the mathematicians employ to guarantee that only a finite number guess incorrectly? We assume that the mathematicians could talk, prior to having hats placed on their heads, to ensure that they all follow the same strategy.
The Othello Problem
You are in a completely dark room. I dump a bag of 1017 Othello chips on the floor. These chips are black on one side and white on the other. You can feel around for the chips, but you cannot see which side is up because it is dark. I tell you exactly 23 have the black side up. I ask you to divide the chips into two piles (every chip must be in one [and only one] of the piles) such that the two piles have the same number of black chips (they may have different numbers of white chips). How do you do it?
The Liar and the Truth Teller Version 2
First the original: There are two guards and two doors. One goes to heaven, the other hell. One guard always lies, the other always tells the truth. They know which they are. They know where the two doors go. You do not know which guard is which. You may ask one yes or no question. What do you ask to determine which door goes to heaven?
New versions: Same setup, but you don't know how many guards tell the truth and how many lie (they could both be liars!). Another one to try: there is only one guard, and you don't know whether he tells the truth or lies (if you solve this one, you solved the previous one). [These are the only problems on this page that I created - the others I have been asked by friends over the years]
At the UW-Madison candidate's weekend we were telling problems like this and someone posed the problem with three guards, one liar, one truth teller, and one random. In three yes/no questions, figure out which one is which. It turns out, that's not possible. Prove it. However, if there were two doors (one to heaven one to hell), you can figure out which one to take in only 2 questions. How?
The Four Quarters Problem
I have a square cafeteria tray with four quarters on it - one in each corner. Again, we are in a dark room. Your goal is to flip over any coins you want and then ask if they are all heads. If they are then you win. So, you get to flip over coins and ask if they're all heads. If not, I spin the tray randomly, and we repeat the process. Can you ensure that you will eventually win?
The Two Quarters Problem
Don't actually do this - it will ruin it. There are two quarters on a table. One is glued in place, the other is adjacent to it. If you roll the quarter that isn't glued around the one that is glued until it reaches the position it started from, how many degrees will it have rotated by? When I say "roll around" you can pretend the edges of the quarters are like gears. Some people find "how many degrees will it have rotated by" to be ambiguous so here's what I mean: If it starts with the head facing up and moves until the head is facing down, that is 180 degrees. If the head rotates from up to down and all the way around to up again (in the same direction), that is 360 degrees. Once you are convinced you know the answer, try it.
The Duck and the Fox
There is a duck in the middle of a perfectly circular pond (radius 1). There is a fox running around the outside of the pond at speed 1. The duck is injured in a way that it can only take off from land. How slowly can the duck swim in order to still be able to make it to the edge of the pond without the fox meeting it there? The fox can only run around the pond. They are both points. The duck has no constraints on the derivative of its velocity. Here's a hint: the duck can swim slower than 1/pi.
The 7 Hats Problem
You are in a room with 7 (or any other number you choose > 3 so it is interesting) friends. God is going to come in and place a hat on each of your heads. There are 7 (same as the number of people) possible colors for the hats. Each person's hat color is independent of the other peoples'. All the hats could be the same color, all the hats could be different colors, there could be 4 of one color and 3 of another, etc. You can see everyone else's hat but not your own. At the exact same time (no communication after your hats are on) you must guess the color of your hat. If any of you get it right, you all live. If you all get it wrong, you all die. You now have time to come up with a strategy before God comes in to put the hats on you. How do you ensure that you will all live?
The Perfectly Logical Pirates
There are 100 pirates. They have 10,000 gold pieces. These pirates are ranked from most fearsome (1) to least fearsome (100). To divide the gold, the most fearsome pirate comes up with a method (e.g. split it evenly, or I get half and the second most fearsome gets the other half). The pirates then vote on this plan. If 50% or more vote in favor of the plan, then that is how the gold is divided. If >50% vote against the plan, the most fearsome pirate is killed and the next most fearsome comes up with a plan, etc. The pirates are perfectly rational. The pirates are perfectly rational. Yes, I said that twice - it is important. You are the most fearsome pirate. How much gold can you get without being killed? How?
The Mathematicians on an Island
There are 100 mathematicians (including you!) on an island. A booming voice comes down from the sky and says "In an hour, I am going to line you up and place a hat on each of your heads - either black or white. You can see the hat colors of everyone in front of you in line, but you cannot see those behind you nor the one you are wearing. I will start at the back of the line (the person who can see everyone else) and ask your hat colors. If you get your hat color correct, you live. If not, you die. You may only guess black or white. If you communicate in any way, I will kill you all. However, you can hear the guesses of everyone behind you. You have an hour." What scheme should you use to ensure that the most people survive? How many people can you guarantee you'll save? For example, if the back person guesses the more common hat color that he sees and everyone else guesses the same color, at least 50 people will live.
7 Points on the Plane
Place seven (distinct) points on the plane such that regardless of which three are chosen, at least two of them will be exactly one unit apart. As far as I know, there is only one way to do this.
Scales... on Steroids
The original version: There are 9 weights, 8 weight the same amount, 1 weights a different amount. You have a balance that will tell you if the left side weights more than the right. In only two weighings, determine which is the heavy weight.
The weighing problem on steroids: There are 12 weights. You do not know whether it is heavier or lighter than the others. In 3 weighings, figure out which one it is, and whether it is heavier or lighter.
Hanging a Picture
I did not solve this one: the answer was told to me. Is it possible to hang a painting (the kind with a string coming out of the top left, attached to the top right) on the wall using three nails, such that if you remove any one nail the painting will fall, but with all 3 nails in the wall, it will not fall?
The Monks with Red Eyes
There is an island with red and blue eyed monks. There are no reflections, and nobody speaks about eye color. If they find out their eyes are red, they kill themselves at midnight that night. You go to the island and see that at least one has red eyes. You say "At least one of you has red eyes." Does anyone kill themselves? If so, when?
The Three-way Duel
There are three people who want to have a duel. Person A hits 100% of the time, b hits 50% of the time, and c hits 25% of the time. C will shoot first, then B, then A, then C, then B, then A, etc. until only one person is left alive. You are person C. You get to shoot first. What should you do in order to maximize the chance that you will live - assuming A and B are logical and also want to maximize their chances of survival?
You have two lengths of fuse. Each burns for an hour, exactly. They don't burn at a steady rate, so if you cut one in half, you don't know if a half will burn for 1 second or 59 minutes (though the sum of the times of the two halves is one hour). How do you time exactly 45 minutes?
The Hungry Cow
You have a cow in a circular pen (radius 1). You want it to only eat half of the grass in the pen. Assume the cow is a point. You tether the cow to the edge of the pen (circular enclosure). How long should its tether be so that it can eat exactly half the grass?
The Weird Warden Problem
There is a prison with 100 inmates. The warden strikes a deal with them. There is a room with a light in it (controlled by a light switch). Each day, the warden will take a random prisoner to that room. At some point, a prisoner must say "We have all been in the room!" If he is correct, they are all set free. If he is wrong, they all die. The initial state of the light is not known (on or off). You are a prisoner. What plan do you propose in order to ensure that you will gain your freedom? Find any solution that works - don't worry about how long it will take. The prisoners will be taken in randomly: over an infinite amount of time, they will all enter the room an infinite number of times. Bonus: how long will it take for you to be freed? Edit: Talking is allowed ahead of time, but not after the process begins. You can only communicate by turning the light on/off. Also, the process will begin on a random day, so you don't know if you are the first in or not.
The Really Really Big Urn
You have a very big urn, and pebbles numbered with the natural numbers (1, 2, 3...). At time step 1, you put pebbles 1-10 in the urn. At time step 2, you take out pebble 1. At time step 3 you put in 11-20. At time step 4 you take out pebble 2. 5-->put in 21-30. 6-->take out 3, etc. If you did this an infinite number of times, how many pebbles would be left in the urn? I like this problem a lot because even people with a strong math background will tend to get it wrong and defend their position vehemently. Hint: I didn't ask what the limit is as the number of time steps goes to infinity. I asked about if this was done an infinite number of times. Hint: Are there more natural numbers or more even natural numbers?
The Ant on the Rubber Band
Try to think about this one without using math at first... There is a rubber band attached to a wall. The rubber band is one meter long, levitating horizontally away from the wall. When God says "go" it will start stretching so the end moves at 10 meters per second. It stretches infinitely. The stretch is uniform (e.g. if it grows by 4 meters, the center will move by 2 meters). There is an ant starting where the rubber band connects to the wall. It walks at .1 meters per second down the rubber band when God says "Go." So, after God says "Go," will the ant ever reach the end? If so, how long will it take? Now, what if the rubber band doubles in length every second?
The Party Problem
This one came from the Andrew's Leap program at CMU (which was awesome by the way - I highly recommend it). It's still up on their site. I have reproduced it below.
A woman and her husband attended a party with four other couples. As is normal at parties, handshaking took place. Of course, no one shook their own hand or the hand of the person they came with. And not everyone shook everyone else's hand. But when the woman asked the other (9) people present how many different people's hands they had shaken they all gave a different answer. Question (this is NOT a trick!): How many different people's hands did the woman's husband shake?
What is a shape (defined by a mathematical equation) that has infinite surface area, but finite volume?
You work with Jane. You know she has two children. One day you meet one at a boys' camp, and it is a boy. What is the probability that she has two boys?
The Chair Problem
This ones just an argument I had once with some friends. If you (where you are now, at the time you are reading this) hold a chair above your head, and then suddenly remove the effect of gravity from the chair, what will happen? Note: All gravity - not just chair-Earth.
An Odd Trail
Where on the Earth can you walk a mile south, a mile west, and a mile north, and end up exactly where you started? Hint: There are infinite places: find them all!
There are four dogs at the corners of a big square. They start chasing each other - each chasing the one clockwise of it. When they chase each other, they run directly toward their targets. There is no constraints on how quickly they can turn. Where do the dogs meet up? If the square has side length 1, how far does each dog run? The latter question is the nifty one.
Bag o Pebbles
There are two empty bags. You have 50 black and 50 white pebbles. You must put all of the pebbles into the two bags. A coin will then be flipped. If it is heads, you discard bag A. If it is tails, you discard bag B. From the remaining bag, you reach in and randomly select a pebble. If it is white, you live - black you die. How should you put the pebbles in the bag? Does it make a difference?
The Dinosaur Eggs
This one is a modified version of the original from www.lispclub.com. You have two very resilient dinosaur eggs. They will absorb a certain amount of force with no negative consequences, but at some point they will crack. If they don't crack, no damage is incurred. You're on a 100 story building. You have 20 trials (you're allowed at most 20 individual egg drops) and 2 eggs. Is it possible to devise a testing algorithm that guarantees to tell you at exactly what floor the eggs will break?
Drop an egg and it doesn't break -> 19 trials, 2 eggs left
Drop an egg and it does break -> 19 trials, 1 egg left
How few trials do you need? Let this number be k. Using k trials, can you solve a 104 story building? How about 105? 106?