Puzzles

I'm going to collect good (by my criteria) puzzles here and add to the post as needed.

This list is also on my website here, and I have not yet decided which is going to be more up-to-date. For now, I'm just going to try to keep them sync'd.

Last update: Jan 26, 2007.

• Games
  
  
  • 1000 Pirates: Consider 1000 pirates that are all perfectly greedy, heartless, and rational (and aware that the other pirates are the same), ranked by seniority, 1 through 1000. They want to split a horde of treasure, and decide that they will do so by a series of votes. Each time they vote, if 50% or more vote to split the treasure equally, they do so. Otherwise, they kill off the lowest ranking pirate, and repeat the vote. How many pirates die before the treasure is split?
    • Bonus 1: Consider the same pirates, who subseqently gained/lost enough members to number 100. They come across a hoard of 5,000 gold coins. This time, the most senior pirate (the captain) will decide on a way to split the coins (not necessarily equally). All the pirates then vote. If at least 50% agree to the split, they do so. Otherwise, they kill the captain, elect the next most-senior pirate captain, and repeat. You are the captain. How do you split the coins?
    • Bonus 2: Same as Bonus 1, but this time, you need a majority (more than 50%) of the vote to survive. You may assume the pirates to be bloodthirsty if it helps.

  • Poison Wells and Dragons: You are stranded in the middle of a very large lake on an island with a dragon and seven poisoned wells, numbered 1 to 7. Each poison is the antidote to any lower numbered poison (3 is the antidote to both 2 and 1), and you have a couple of hours to get to an antidote after you are poisoned. However, only the dragon can reach well 7, as it is at the top of a tall mountain. The water in the wells looks clean, so you can't tell them apart. The dragon challenges you to a duel: he and you will each bring a glass of water, exchange glasses and drink. Can you survive? Can you kill the dragon? How sure are you of success?

  • Quarter Game: The devil challenges you to a game played on a circular table of unspecified diameter. You and he take turns placing a quarter on the table such that it is completely on the table and does not overlap with any other quarters already played. A player wins if he makes the last legal move. Do you prefer to go second or first?

• Probability & Statistics:
  
  
  • Monty Hall: You are on a gameshow in front of three doors which lead to three rooms. One of the rooms contains a prize, the other two are empty. You may open one door. You choose a door, but do not open it yet. The host, who knows which door hides the prize, opens one of the doors you did not pick, showing that it does not hide the prize. He then gives you the opportunity to switch doors. Should you change your choice?

  • Envelope Choice: You have two envelopes in front of you, each with a non-zero sum of money. One contains twice as much money as the other. You select one of the envelopes, but ponder before opening it. If your envelope has x dollars, there is a 50% chance the other one has x/2 dollars and a 50% chance it has 2x dollars. The expected return of switching therefore is .5(.5x 2x) = 1.25x, which seems like a favorable gamble. Do you switch and why?

  • Children: Your married-with-two-kids co-worker invites you over to dinner. You come over and...
    • a) A son of the coworker answers the door. What is the probability that the other child is a girl?
    • b) The co-worker's firstborn, a son, answers the door. What is the probability that the other (younger) child is a girl?
    • c) Recently, the government has sent all families with two female children to China. Your co-worker (still not in China) answers the door, and says 'my two kids will be down shortly'. What is the probability that he has two boys?
    • d) The (presumably mathematician) co-worker answers the door, and says 'I have two children, at least one of whom is a boy.' What is the probability that both children are boys?

  • Marbles: You are brought two jars, one with 50 white marbles, the other with 50 black marbles. You are allowed to redistribute the marbles however you wish so long as when you are done, every marble must be in one of the two jars. The two jars will then be shaken up, then you will be blindfolded and presented with one of the jars at random. You pick one marble out of the jar given to you. If the marble you pull out is white, you live; if black, you die (sorry). How should you redistribute the marbles?

  • 100 Prisoners: 100 men are on death row. Their names are placed in 100 boxes on a table, one name to a box. The prisoners are led into the room with the boxes, one at a time. Each is allowed to look into up to 50 of the boxes to try to find his own name. If every prisoner is able to find his name, all the prisoners are released. Otherwise, all are executed. The prisoners are not allowed to alter the state of the room or boxes in any way, nor communicate after they enter the room; however, they are given a chance to come up with a strategy in advance. What is their best strategy? Hint: Lbh pna trg nobir guvegl creprag. Ab, ernyyl.

  • Rock Stars: The keeper of the website The Premature Death of Rockstars argues that rock stars live on average 36.9 years, while the rest of us live on average 75.8 years. Is his assesment reasonable given the data?

  • Lazy Hunter: A rabbit starts on an infinite straight path, at a point we'll call 0. Every second, the rabbit randomly jumps either one meter to the right or one meter to the left. A lazy hunter waits for just off the path, one hundred meters to the right of the rabbit's starting position. What is the expected time until the rabbit lands at the 100 meter mark in front of the hunter?

• Sets
  
  
  • Pills: You are on a strict medical regimen that requires you to take exactly one A pill and exactly one B pill at the same time each day. The pills are very expensive. You open the bottle of A pills, and tap one out into your hand. Then you open the bottle of B pills, but tap too hard, and two B pills come out into your hand with the A pill. Problem is, the pills are all exactly identical. How can you satisfy your regimen without wasting any pills?

  • Coin Room: You're wearing a blindfold and thick gloves, in a room with 50 quarters, 20 of which are heads up. You are allowed to move the coins around and/or flip some or all of them, if you wish. Problem is, you can neither see the coins nor feel which side of any of them is up. Find a way to split the coins into two groups, each of which has the same number of heads up coins.

  • Mutilated Chessboard: Consider a standard 8x8 chessboard, and a set of rectangular tiles 1x2 squares in size. You can cover the board with 32 tiles. If you remove one square each from two opposite corners of the board, is it possible to cover every remaining square using 31 tiles?
    • Bonus: Consider a chessboard with two adjacent squares removed at each of two opposite corners (four squares removed altogether in two rectangles - your choice of orientation). Can you cover this chessboard with tiles shaped as tetris Ts: 1x3 with an extra 1x1 attached in the middle?

  • Scales: You have 14 marbles, identical except that one is flawed, either heavier or lighter than the others. You have a scale which will compare weights, but will only let you know heavier than, lighter than, or equal. You are allowed 3 weighings, and your task is to determine which marble is flawed, and whether it is lighter or heavier than the others.
    • a) Prove that the problem is impossible to solve. (1-2 sentences max)
    • b) Prove that the problem is impossible to solve even with 13 marbles.
    • c) Solve the problem with 12 marbles.

  • 1000 Barrels of Wine: A king has 1000 barrels of expensive wine. His guards catch an assassin in the cellar, but only after the assassin poisoned an unknown one of the barrels. The poison is so lethal that any amount of contaminated wine will kill, and it takes a month to take effect. Fortunately, the king has 10 political prisoners he was going to execute anyway. How soon can the king drink his wine again?

• Other
  
  
  • Liar/Truthteller: You die and find yourself before two doors, with a pair of guardian statues situated between them. One door leads to salvation, the other to purgatory (they are not labeled). One of the guardian statues always tells the truth, the other always lies (they, also, are not labeled). You may pose only one question to one statue. What do you ask to determine which door leads to salvation?

  • Secure Medicine: Alice needs to send medicine to Bob, who is on another island. Eve has a boat and a chest that can be locked. Eve is willing to transport objects in the chest, but she is a kleptomaniac and will steal whatever is inside the chest if she has access to it. Both Alice and Bob have a padlock and a key such that their own key only opens their own lock. Neither Alice nor Bob are able to travel. How can Alice send Bob the medicine so that Eve won't steal it?

  • Foresight: There are two envelopes in front of you, A and B, prepared by Buddha. Envelope A contains $1,000. Envelope B contains either $1 million, or nothing. Buddha has predicted which envelope you are going to pick. If he predicted that you pick envelope A, then envelope B contains $1 million. If he predicted that you will pick envelope B, then envelope B is empty. The envelopes were prepared before you entered the room, and Buddha is omniscient. What envelope to you choose and why?

  • The Unexpected Tiger: Princess Jane wants to marry knave Mike. The king, who is renowned for being always right and always truthful, offers the couple a small chance. Mike will open seven doors in order from 1 to 7. Behind one door, the king promises, will be an unexpected tiger, which Mike will have to defeat to win the princess. Mike agrees. Before he opens any doors, he considers that if he opens doors 1 through 6 and they are empty, then the tiger would have to be behind door 7. Yet then the tiger would not be unexpected, so that rules out door 7 (the king always keeps his promises). That leaves only doors 1 through 6. Yet by the same logic, the new last door (6) also can not contain the tiger. Mike quickly eliminates the rest of the doors, and decides that none can hide a tiger. Confidently, he begins to open the doors, and is devoured by the (unexpected) tiger behind door 3. Where did Mike go wrong?

  • Tiger 'Round a Lake: You go fishing in a circular lake of radius R. From the center of the lake, you spot a hungry tiger at the shore. The tiger can't swim, runs N times faster than you can row your boat, but you can run faster than the tiger. If you can get onto the shore away from the tiger, you can escape. The tiger knows this, and is smart enough to optimize his strategy to be waiting for you when you reach the shore. What is your best strategy for getting to shore as far away from the tiger as possible? At what relative values of N and R can you no longer escape?

• Short/Odd (some with real solutions, some not so much)
  
  
  • There are 10 types of people in the world - what are they?

  • You are on a lake in a boat. You take a bowling ball from the boat and throw it into the lake. Does the level of the lake fall, rise, or stay the same?

  • A machinist drills a circular hole, dead center, all the way through a solid metal sphere. The hole is 6 inches long. How much metal remains in the ball? (Ah, but can you prove it?)

  • Parallel train tracks appear to converge in perspective. What angle must they be laid at to appear to be parallel in perspective?

I'm adding this to my memories if you are ever bored and want to while away a few minutes.

Comment if you have any suggestions for the list, though bear in mind my criteria may be different from yours, so I don't guarantee I'll add your puzzle.

Let me know if I've erred in any of the problem statements.

Feel free to post solutions (it's screened) / ask questions (or for hints) / etc.

References: Berkeley riddles; Slashdot Thread; Hard interview questions on E2; Grey Labyrinth; Stanford; Mathematical Puzzles by Peter Winkler, Cut the Knot, problemaday, techinterview.org.