This is a collection of logic puzzles. I did not create most of these puzzles, I only collected them here. I would particularly like to thank Rich Korf for asking me several of these.
First the original: There are two guards and two doors. One door leads to freedom, and the other to death. 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 or which door is which. You may ask one yes or no question. What do you ask to determine which door leads to freedom?
New versions: Same setup, but you do not 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 do not know whether he tells the truth or lies (if you solve this one, then you solved the previous one).
You select five cards from a standard 52 card deck (no jokers) and place them on a table. I enter and look at the cards. I place one in my pocket and place the other four face up in slots marked 1, 2, 3, and 4. I then leave. My accomplice enters, looks at the four cards, and correctly states which card is in my pocket. What strategy could we have used to ensure that my accomplice would always know which card was in my pocket?
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 that 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 chips with the black side up (they may have different numbers of chips with the white side up). How do you do it?
You are in a room with 7 (or any other number greather than 3) friends. Soon, I will place a hat on each of your heads. There are 7 (same as the number of people) possible hat colors. You know the seven possible colors. I may place any number of each color (e.g., there may be multiple of one color and no hats of another color). You will be able to see everyone else's hat, but not your own. At the exact same time (no communication after your hats are on) you will guess the color of your hat. If any of you get it right, you all win. If you all get it wrong, you all lose. You now have time to come up with a strategy before I place the hats. How do you ensure that you win?
You have a framed painting (the kind with a string coming out of the top left and attached to the top right) that you want to hang on the wall using two nails, such that if you remove any one nail the painting will fall, but with both nails in the wall it will not fall. How do you loop the string around the nails?
The original version: There are nine stones. Eight weigh the same amount, and one weighs slightly more than the others. You have a balance that will tell you if the left side weighs more than the right. Using the balance only twice, determine which is the heavy stone.
The balance problem on steroids: There are 12 stones, one of which weights a different amount from the others. You do not know whether it is heavier or lighter than the others. Using the balance three times, figure out which stone is different and whether it is heavier or lighter.
You have a rope that is 150 feet long. You can tie it in different ways and can also cut it. You are on a cliff that is 200 feet tall. 100 feet from the top is a ledge. There are rings to tie the rope to at the top and at the ledge. How can you get down?
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?
There are 100 mathematicians (including you!) in a room. Soon, I will enter and you will all line up such that you can see everyone in front of you, but nobody behind you. I will then place hats on each of yours heads. Each hat may be either black or white. You will not know what color hat you (or anyone behind you in line) is wearing. I will then ask each of you what color hat you are wearing, starting from the back of the line and moving to the front (starting from the person who see's everyone's hat color but his or her own, and ending with the person who sees nobody's hat color). Now, before I enter and place the hats, come up with a strategy to ensure that 75 people live. Can you do even better?
Draw seven (distinct) points on a piece of paper such that regardless of which three are chosen, at least two will be exactly one unit (e.g., inch or centimeter) apart. As far as I know, there is only one way to do this.
An ant is in one corner of a room shaped like a cube. It wants to go to the opposite corner. What is the shortest path that the ant can take, and how long is it?
I place 8 coins on a table in a line with random sides up. You can look at the coins and then flip one coin. You leave and your friend enters. Come up with a strategy so that your friend can determine which coin you flipped.
You have a square cafeteria tray with four quarters on it - one in each corner. Again, we are in a dark room. You do not know which quarters have the heads side up and which have the tails side up. Your goal is to flip over any coins you want and then ask if they are all heads. If they, are then you win. If they are not, then I rotate the tray randomly and we repeat the process. Can you ensure that you will eventually win?
Do not physically 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, that is 360 degrees. Once you are convinced you know the answer, try it.
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. Hint: the duck can swim slower than 1/π.
You have two identical glasses, filled to the same level. One has water in it and the other has wine. You take a teaspoon of the wine, pour it into the water, and mix them up. You then take a teaspoon of the water (with a little wine in it), pour it into the wine and mix it up. Is there more water in the wine, or more wine in the water?
If a car is traveling at 60 miles per hour, what part is stationary? What part is going 120 miles per hour?
Bob flips 850 fair coins. Alice flips 851. What is the probability that Alice gets strictly more heads than Bob?
You're in a boat with a big rock, in a swimming pool. You toss the rock overboard. What happens to the level of the water in the pool?
You are given a round table, and a large number of coins. You alternate with an opponent placing a coin on the table, not overlapping the edge or any other coins. The winner is the last player who can place a coin. You get to decide who goes first. Do you have a winning strategy?
There is a straight line of N foxholes, and one fox. Every night, the fox moves from his current foxhole to the one either immediately to his left, or immediately to his right. Every day, you get to look in one fox hole. Give a strategy to guarantee finding the fox in the fewest number of days.
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?
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 that A and B are logical and also want to maximize their chances of survival? Hint: this would not be here if the answer was completely trivial.
You have two lengths of fuse. Each burns for an hour, exactly. They do not burn at a steady rate, so if you cut one in half, then you do not 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?
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?
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 or she is correct, then all are set free. If he or she is wrong, then all will never be set free. The initial state of the light is not known (on or off). 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 do not know if you are the first in or not. You are a prisoner. What plan do you propose in order to ensure that you will gain your freedom? Find any solution that works - do not 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?
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, etc. If you did this an infinite number of times, how many pebbles would be left in the urn? Hint: The limit as the number of iterations goes to infinity may give a different answer.
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 I say "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, also starting when I say "go". Will the ant ever reach the end of the rubber band? If so, how long will it take? What if the rubber band doubles in length every second?
This one came from the Andrew's Leap program at CMU (which was awesome by the way - I highly recommend it). 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?
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 strategy that guarantees to tell you at exactly what floor the eggs will break?
If after your first trial (dropping an egg off of the balcony on one floor of the building), if the egg does not break, then you have 19 trials remaining and two eggs. If the egg breaks, then you still have 19 trials remaining, but only one 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?
You work with Jane. You know that 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?
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!
What is a shape (defined by a mathematical equation) that has infinite surface area, but finite volume?
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 win - black you lose. How should you put the pebbles in the bag? Does it make a difference?
(This problem is hard. If this is your first look at this page, I recommend skipping it.) There are a countably infinite number of mathematicians in a room. Each has a black or white hat placed on his or her 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 use to guarantee that only a finite number guess incorrectly? The mathematicians may talk before the hats are placed in order to agree on a strategy. You may assume the axiom of choice.