An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?

Sheila and He-Man are twins; Sheila is the OLDER twin. Assume they were born immediately after each other, an infinitesimally small - but nonzero - amount of time apart. During one year in the course of their lives, Sheila celebrates her birthday two days AFTER He-Man does. How is this possible?

10/28/2002 3:58AM Bonus: What is the maximum amount of time by which Sheila and He-Man can be apart in their birthday celebrations during the same year? I think it's more than two days.

Note: For both Sheila and He-Man, these birthday celebrations happen on the actual birthday date -- it cannot be a celebration that occurs at a date earlier or later than the actual birthday date for whatever reasons of convenience. Also, the solution has nothing to do with the theory of relativity or any other over complicated nonsense like that.

100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?

Note 1: (1/8/2003 3:51PM Update) What is meant by optimal? If your solution is optimal, it means you can prove that no other algorithm can produce a lower average running time. This is usually very hard to do though, and I would be surprised if anyone ever sends me such a proof. So the best we can do in the meantime is try to beat the best average running time we know of. The number to beat so far is around 3500 days. So BEFORE YOU E-MAIL ME YOUR SOLUTION, check its average time to see if beats the 4000 day ballpark. If you get a number around 27-28 years, then you've found the solution most people who solve the puzzle come up with. However, it's not optimal.

Note 2: (1/8/2003 3:49PM Update) How to compute average running time? The preferred method is to do a probabilistic analysis using pencil and paper. But if you haven't learned about stuff like that, a much simpler way is to just program your solution and run it maybe 100 times, recording how many days elapsed in each invocation. Afterwards you should have an array of 100 numbers. Now take the average of all them, and you'll have an empirical average which is close to the theoretical one.

Note 3: (11/7/2002 7:35AM Update) The problem statement used to say "The prisoners are allowed to get together one night to discuss a plan." In the forum, quite a few people mentioned the clever solution of simply having the planning meeting in the central living room, and then asserting that everyone has been there on the first day of the random selection process. To assure that this problem is not so easily defeated, I have stipulated that the meeting happen in the courtyard.

Note 4: Does anyone know where this riddle originated? I got it from a friend who got it from another friend who doesn't know where it comes from. E-mail me at wwu at ocf.berkeley.edu.

Note 5: (1/1/2003 1:25AM Update) Edited to add that the cells are soundproof and windowless.

Note 6: (1/21/2003 1:03AM Update) Edited to clarify that chosen prisoners are turned to their cells at the end of the day.

Note 7: (2/6/2003 11:27PM Update) Edited to clarify that the meeting must happen before the whole ordeal begins.

Using all five of the pieces shown below, make a new square.

Note: Click here and print out the image. Then cut out the pieces and play with them on your desk.

this is a magic trick performed by two magicians, A and B, with one regular, shuffled deck of 52 cards. A asks a member of the audience to randomly select 5 cards out of a deck. the audience member -- who we will refer to as C from here on -- then hands the 5 cards back to magician A. after looking at the 5 cards, A picks one of the 5 cards and gives it back to C. A then arranges the other four cards in some way, and gives those 4 cards face down, in a neat pile, to B. B looks at these 4 cards and then determines what card is in C's hand (the missing 5th card). how is this trick done?

Note 1: There's no secretive message communication in the solution, like encoded speech or ninja hand signals or ESP or whatever ... the only communication between the two magicians is in the logic of the 4 cards transferred from A to B. Think of these magicians as mathematicians.

Note 2: After you've figured this one out, try 5 CARD MAGIC TRICK REDUX for the next level of difficulty.

Note 3: This magic trick is originally credited to magician and mathematician Fitch Cheney.

you're a cyborg in a pistol duel with two other cyborgs. you have been programmed to fire pistols with an accuracy of 33%. the other two cyborgs shoot with accuracies of 100% and 50%, respectively. the rules of the duel are one shot per-cyborg per-round. the shooting order is from worst shooter to best shooter. thus, you go first, the 50% guy goes second, and the 100% guy goes third; repeat. if a cyborg dies, we just skip his or her turn, obviously. what should you shoot at in round 1 to maximize your chances of survival over time?

a corporate business man has two cubes on his office desk. every day he arranges both cubes so that the front faces show the current day of the month. what numbers are on the faces of the cubes to allow this?

Note: You can't represent the day "7" with a single cube with a side that says 7 on it. You have to use both cubes all the time. So the 7th day would be "07". I also should note that this is a really sly problem. Almost unfair.

Big Hint: The answer is a very common question.

A traveler, on his way to a certain village A, reaches a road junction, where he can turn left or right. He knows that only one of the two roads leads to village A, but unfortunately, he does not know which one. Fortunately, he sees two twin-brothers standing at the road junction, and he decides to ask them for directions. The traveler knows that one of the two brothers always tells the truth and the other one always lies. Unfortunately, he does not know which one always tells the truth and which one always lies. How can the traveler find out the way to village A by asking just one question to one of the two brothers?

Note 1: Much harder than the more commonly known FORK IN THE ROAD I. Yes, they are different problems. It's worth noting that a solution to FORK IN THE ROAD II will work equally well on FORK IN THE ROAD I; however, not necessarily the converse.

Note 2: Actually, there's yet another solution which solves both I and II equally well, and it is not that difficult to come up with.

you have two eggs. you need to figure out how high an egg can fall from a 100 story building before it breaks. the eggs might break from the first floor, or might even survive a drop from the 100th floor -- you have no a priori information. what is the largest number of egg drops you would ever have to do to find the right floor? (i.e. what's the most efficient way to drop the eggs and determine an answer?) you are allowed to break both eggs, as long as you identify the correct floor afterwards.

after you've solved the above problem, generalize. define the "break floor" as the lowest floor in a building from which an egg would break if dropped. given an n story building and a supply of d eggs, find the strategy which minimizes (in the worst case) the number of experimental drops required to determine the break floor.

Note: Interestingly, the solution is similar to a commercial algorithm used for stress-testing the reliability of TCP/IP networks. Got this from Spring 2002 CS170, taught by Dr. Satish Rao.

Local Berkeley professors Dr. Demmel and Dr. Shewchuk bump into each other on Telegraph Ave. They haven't seen each other since Vietnam.

How old are the daughters?

10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can't see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone's head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either "black" or "white". If what he says matches the color of the hat he's wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy ... this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

After you have solved the above problem, generalize. There are N prisoners and K different colors of hats. What's the optimal plan?

Hint: if there are N prisoners, you can save N-1 lives, guaranteed!

Four ghostly galleons – call them E, F, G and H, – sail on a ghostly sea so foggy that visibility is nearly zero. Each pursues its course steadily, changing neither its speed nor heading. G collides with H amidships; but since they are ghostly galleons they pass through each other with no damage nor change in course. As they part, H’s captain hears G’s say “Damnation! That’s our third collision this night!” A little while later, F runs into H amidships with the same effect (none) and H’s captain hears the same outburst from F’s. What can H’s captain do to avoid a third collision and yet reach his original destination, whatever it may be, and why will doing that succeed?

Problem Source: Dr. William Kahan, Math H110 (honors linear algebra), UC Berkeley

You have 3,000 bananas and a camel which can carry at most 1,000 bananas at a time. The camel eats a banana before moving a unit. You want to transport the bananas 1,000 units. What is the maximum number of uneaten bananas that you can move 1,000 units?

Problem source: 11th Grade Honors Precalculus, Dr. James J. Hogan High School

You are wearing a blindfold and thick gloves. An infinite number of quarters are laid out before you on a table of infinite area. Someone tells you that 20 of these quarters are tails and the rest are heads. He says that if you can split the quarters into 2 piles where the number of tails quarters is the same in both piles, then you win all of the quarters. You are allowed to move the quarters and to flip them over, but you can never tell what state a quarter is currently in (the blindfold prevents you from seeing, and the gloves prevent you from feeling which side is heads or tails). How do you partition the quarters so that you can win them all?

Hint 1: Your algorithm should run in under 30 seconds.

Hint 2: If an infinite number of quarters confuses you, try 100.

Three men go to a cheap motel, and the desk clerk charges them a sum of $30.00 for the night. The three of them split the cost ten dollars each. Later the manager comes over and tells the desk clerk that he overcharged the men, since the actual cost should have been $25.00. The manager gives the bellboy $5.00 and tells him to give it to the men. The bellboy, however, decides to cheat the men and pockets $2.00, giving each of the men only one dollar.

Now each man has paid $9.00 to stay for the night, and 3 x $9.00 = $27.00. The bellboy has pocketed $2.00. But $27.00 + $2.00 = $29.00. Where is the missing $1.00? WTF?

Was it really impossible for Achilles to win the race? Explain.

Note: Story adapted from Douglas Hofstaeder's awesome book, Godel, Escher, Bach.

We know that the derivative of x² with respect to x is 2x. However, what if we rewrite x² as the sum of x x's, and then take the derivative:

This argument shows that the derivative of x² with respect to x is actually x. So what's going on here?

Note: Most people with some math experience can show that some part of the argument is erroneous. As in simply, something doesn't follow. However, a full solution will explain why this argument attacks something that lies at the very heart of calculus itself, and that is what really explains why it's erroneous.

Forum thread: (spoilers) Click here

You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

Note: For those not familiar with factorial, n! = n*(n-1)*(n-2) ... 2*1. So for example, 3! = 3*2*1 = 6.

"October 2, 2001" in MMDDYYYY format is a palindrome (a string that reads the same forwards as it does backwards). Pretty cool, check it out: 10/02/2001 --> 10022001. When was the last date before October 2, 2001 that is also a palindrome?

You have an infinite cache of cigarettes. What is the maximum number of cigarettes you can place on a table so that every cigarette touches every other cigarette? (You can't bend the cigarettes.) Rigorously prove that your number is optimal.

Note 1: You can't just do a star configuration, like an asterisk. Remember that a cigarette has a thickness, and can't be treated as a line of infinitesimally small width. Thus, in an asterisk configuration of six cigarettes, there will be a hexagonal hole in the middle, and any cigarette would not be touching the cigarette opposite to it. Also, you can't just make an octagonal ring of cigarettes, because then each cigarette would only be touching the cigarettes directly to the right and left of it -- the question wants every cigarette to touch each other directly, not just be somehow indirectly connected to every other cigarette.

Note 2: Check out cigarettes.shtml for my analysis so far (spoiler warning: contains solution configurations for 6 and 7 cigarettes), and this bulletin board thread for what some others have thought about this problem.

Note 3: Now that you have constructed an optimal configuration and proven it's optimality, generalize. Suppose you have an infinite cache of cylindrical widgets of height h and radius r. Derive a closed-form formula that calculates the number of widgets in the max clique configuration. And send the formula to me please =) I believe this can be done because this problem is referenced in this following Calvin University math assignment.

Note 4: 3/9/2003 6:01AM A forum member informs that the great Martin Gardner solved the problem in one of his books; I have yet to check this out.

You have two 3-bit sensors, A and B, that measure the same thing, whatever it is -- temperature of the room, radioactivity levels, whatever. Both sensors are hooked up to the same CPU, which takes in the sensor readings. You know that the sensors are designed so that their readings can be off by at most one bit. We claim that if B knows that A has sent the CPU a 3-bit sequence, then B only needs to send 2 bits, and the CPU will be able to reconstruct B's 3-bit measurement, thereby conserving bandwidth. How is this so?

Hint: See the maximum minimum Hamming distance riddle for some powerful ideas.

Note: This riddle is actually related to some signal processing research I'm doing at UC Berkeley. Credit to Dr. Kannan Ramchandran, my research professor.

alice sends different partial messages to a bunch of different receivers. by partial, we mean that one message by itself doesn't convey any meaningful information. let us denote the set of receivers as R. the messages are designed such that if any n receivers get together, they can somehow pool their partial messages together to get a meaningful message -- alice's intended message. however, if any n-1 or less receivers get together, they can't reconstruct anything meaningful whatsoever. n < |R|. what kind of messages are being sent by alice, and what mathematical function do the receivers apply on their pooled partial data to determine the intended message?

Note: If you solved this riddle about 30 years ago, you could've published a paper on it and earned a Ph.D. Unfortunately, someone's already done that. His full name is not very well known, but the initial of his last name is peppered across cyberspace.

Consider a finite sequence of distinct integers. A subsequence is a sequence formed by deleting some items from the original sequence without disturbing their relative ordering. A subsequence is called monotone if it is either increasing (each term is larger than the one before it) or decreasing (each term is smaller than the one before it). For example, if the sequence is 4, 6, 3, 5, 7, 1, 2, 9, 8, 10, then 4, 6, 8, 10 is a monotone (increasing) subsequence of length 4 and 6, 5, 2 is a monotone (decreasing) subsequence of length 3.

a) Find a sequence of 9 distinct integers that has no monotone subsequence of length 4.

b) Show that every such sequence of length 10 has a monotone subsequence of length 4.

c) Generalize. How long must the sequence be to guarantee a monotone subsequence of length n?

I am thinking of an integer n with 0 <= n <= 15. To figure out what number I'm thinking of, you can ask me 7 yes-or-no questions -- questions that can only be answered with either "yes" or "no". The questions must be independent of each other, their answers, and the order in which they are answered. (So you can't ask a question like, "if the answer to the previous question was "yes", then is n larger than 10, otherwise is n even?") When you ask me your seven questions, I am allowed to LIE about at most one of the answers. What seven questions can you ask to determine n?

Was Alice's speed the mean, median, or neither?

Note: Assume that any car on the road drives at a constant nonzero speed of s miles per hour, where s is a positive inte- ger. And suppose that for each s, the cars driving at speed s are spaced uniformly, with d(s) cars per mile, d(s) being an integer. And because each mile looks the same as any other by the uniformity hypothesis, we can take mean and median to refer to the set of cars in a fixed one-mile segment, the half-open interval [M, M+1), at some instant.

In an LCD display some numbers, when viewed upside-down, are images of other numbers. For example, 1995 becomes 5661. The fifth number that can be read upside down is 8, and the 15th is 21, which is 12 when viewed upside-down. What is the millionth number that is meaningful upside-down?

A certain hotel room lock is opened by scanning a key card. In theory, one enters the room by inserting and removing the key card once. In practice, however, the key card is ambiguously labeled, so that either of two orientations might be the correct orientation of the card. In theory, of course, one could just try one orientation, and if it didn't work try the other. In practice, however, the card reader sometimes fails, so that after trying each orientation once, one may still not have gained access to the room.

A few more details:

(a) Either of the two orientations is equally likely to be cor- rect.

(b) The success rate of a correctly oriented card is p with 0 < p < 1.

(c) Failure on either side of the card is indistinguishable, so it does not give any information about whether the orientation of the card was correct.

(d) An attempted scan takes 1 second to succeed or fail; reversing the orientation also takes 1 second.

The last property means that in 3 seconds one could try one orientation 3 times or each orientation once (using the middle second to flip it over). In either case, of course, one might still be standing in the hall and need to decide what to do next.

So what attempt strategy would you use to enter the room? Why?

Feel free to consider fixed values of p (p = .5 or p = .9, for example) as special cases. What if p is fixed but unknown?

Help Bob out with a strategy that will win. Note that the cards all have face value with the following exceptions: Ace=1, Jack = 11, Queen = 12, and King = 13.

Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips?

There are two envelopes in front of you each with a non-zero sum of money. You are informed one has twice as much money as the other. You are then allowed to select either envelope and keep the money inside. After you select one and before opening it you are given the option to change your mind and switch to the other one? You think to yourself that 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, you compute, is .5[.5x + 2x]=1.25x which seems like a favorable gamble. Do you switch and why? Assume you are neither risk averse nor risk prone, in other words you will take any good gamble and avoid any bad one.

You are trapped in a small phone booth shaped room. In the middle of each side of the room there is a hole. In each hole there is a push button that can be in either an off or on setting. You can't see in the holes but you can reach your hands in them and push the buttons. You can't tell by feel whether they are in the on or off position. You may stick your hands in any two holes at the same time and push neither, either, or both of the buttons as you please. Nothing will happen until you remove both hands from the holes. You succeed if you get all the buttons into the same position, after which time you will immediately be released from the room. Unless you escape, after removing your hands the room will spin around, disorienting you so you can't tell which side is which. How can you escape?

Now generalize. You are in a room with N sides, each side having a hole with a push button. What is the minimum number of hands you need to escape the trap room?

Note: Regarding the original setup with N = 4, the fewest possible turns that I know of is seven.

Four heat-seeking missiles are initially placed at the corners of a square with side length s. Each missile flies at a constant speed toward the missile on its left. Describe the path each missile takes until it collides with the rest in the square's center. What is this path's length?

Generalize to n missiles on a regular n-gon.

A cubic piece of cheese has been subdivided into 27 subcubes (so that it looks like a Rubik's Cube). A mouse starts to eat a corner subcube. After eating any given subcube it goes on to another adjacent subcube. Is it possible for the mouse to eat all 27 subcubes and finish with the center cube?

The figure below is a square composed of 21 smaller squares. Each of the 21 smaller squares has a side of integer length and all 21 are different sizes. Find any solution for the size of the 21 smaller squares.

Of three men, one man always tells the truth, one always tells lies, and one answers yes or no randomly. Each man knows which man is who. You may ask three yes/no question to determine who is who. If you ask the same question to more than one person you must count it as question used for each person whom you ask. What three questions should you ask?

Create the number 24 using only these numbers once each: 3, 3, 7, 7. You may use only the following functions: +, -, *, /. This is not a trick question; for example, the answer does not involve a number system other than base 10 and does not allow for decimal points.

The religious keeper of the web page The Premature Death of Rockstars argues that rock stars do not live as long as the general population. He states that the average age at death of rock stars is 36.9 and 75.8 for the general population. What is wrong with this use of these statistics? This is an illustrated example of lying with statistics.

Thirteen pirates put their treasure in a safe. They decide that the safe should be able to be opened if any majority of pirates agree but not be able to be opened if any minority agree. The pirates don't trust each other so they consult a locksmith. The locksmith puts a specific number of locks on the safe such that every lock must be opened to open the safe. Then he distributes keys to the pirates such that every pirate has some but not all of the keys. Any given lock can have multiple keys but any given key can only open one lock. What is the least number of locks required?

You have 12 identical-looking balls. One of these balls has a different weight from all the others. You also have a two-pan balance for comparing weights. Using the balance in the smallest number of times possible, determine which ball has the unique weight, and also determine whether it is heavier or lighter than the others.

I am thinking of a number between 1 and 100. You can guess a number and I will tell you if it is high or low. If you get it right on the first guess I will pay you $5, on the second guess $4, and so on. If you get it right on the sixth guess I will pay you nothing, on the seventh guess you owe me $1, on the eight you owe me $2, and so forth (5 4 3 2 1 0 1 2 3 4 5 4 3 2 1 0 1 2 ...)

Q1) Should you play the game with me?

Q2) [Slightly harder and more math] What is your expected return?

Note: From interview with Gates/Ballmer about 8-12 years ago. Used to test "the way you think about problems".

You have n bitstrings, each of length k. Define the Hamming distance between two bitstrings as the number of bits on which the strings differ (e.g. the Hamming distance between 0000 and 1100 is 2). Assume the strings have been chosen such that the Hamming distance between *any* two strings is maximized. In other words (but perhaps more confusing words), the minimum Hamming distance of the set has been maximized. Write down a closed form formula which computes the maximum minimum Hamming distance for any given n and k.

Note 1: Here is the notion of Hamming space, summarized in a useful picture:

This is the Hamming space for k=3. Start at a vertex. Change one bit to cross one edge. Change two bits to cross two edges. Change three bits to cross three edges. Note the important difference between Hamming space and the everyday notion of numeric distance. Whereas we would normally say that 100 (4 in binary) and 000 (0 in binary) are 4 units apart, in Hamming space, they are only one unit apart, and very close.

Note 2: This is a problem that my research partner and I came across while studying error correcting codes. There must exist a closed-form formula, but we have been unable to derive it or find it. For a second, it seemed like we had it, but then it was wrong. It most likely involves mods and floors and ceilings.

Forum thread: click here

The professor for class Logic 315 says on Friday: "We're going to have a surprise quiz next week, but I'm not telling you what day... if you can figure out what day it will be on, I'll cancel the quiz."

The students get together and decide that the quiz can't be on Friday, as if the quiz doesn't happen by Thursday, it'll be obvious the quiz is on Friday. Similarly, the quiz can't be on Thursday, because we know it won't be on Friday, and if the quiz doesn't happen by Wednesday, it'll be obvious it's on Thursday (because it can't be on Friday). Same thing for Wednesday, Tuesday and Monday. So it can't be on ANY day, so there's no quiz next week!"

They tell the professor, who smiles and says, "Well, nice to see you're thinking about it."

On Tuesday, the professor gives the quiz, totally unexpected!

What's the flaw in the students' thinking?

Note: (Update 1/28/2003 2:40AM) There are many possible solutions, but I have included the >=P symbol because supposedly the math community has not agreed on an official explanation. I don't fully understand why this is so.

Forum thread: click here

Three players enter a room and a red or blue hat is placed on each person's head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own.

No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly.

The same game can be played with any number of players. The general problem is to find a strategy for the group that maximizes its chances of winning the prize.

Hint: See the maximum minimum Hamming distance riddle for some powerful ideas.

a corporate business man has three cubes on his office desk. every month, he arranges the cubes so that the front faces show the current month's three letter abbreviation (e.g. JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC }. what letters are on the faces of each cube?

Note 1: This might be insanely difficult. Just remember to be creative. Special thanks to Bruce Preston for sending this to me, along with a wonderful GIF of his solution!

Note 2: Although the month abbreviations I have typed above are all capitalized, you may have to be more flexible with your fonts to construct a working solution.

There are three omniscient gods sitting in a chamber: Past, Present and Future. They are all truthful, but with the following caveat: Present answers the question currently being asked, Past answers the last question asked in their chamber, and Future answers the next question which will be asked in their chamber. Despite their manipulation of which question to answer, each still answers immediately as if answering the question currently being asked.

Furthermore, the gods answer in a language in which "yes" and "no" are replaced by "da" and "ya", but you do not know which is which. You only know that their answers are consistent amongst themselves.

With three questions, determine which god is which.

Note 1: (standard) Because of possible time conflicts, you must determine your questions ahead of time, rather than based on previous answers. You are, however, allowed to choose who you ask each of your three questions to dynamically, and scoping is also dynamic (e.g. the pronoun "you" in a question will always refer to the person you choose to ask the question to, not a predetermined person). No self-referential questions (e.g. "is this question true iff ..."). No time related questions (e.g., "if the answer to my second question was 'no', then... otherwise ...") are permissible, as this could lead to paradoxes within the space-time continuum). Finally, note that if you ask Past your first question or Future your last question, the answer will give you no additional information because you do not know what the last or next questions are!

Note 2: (specific) Because of possible time conflicts, you must determine your questions ahead of time, rather than based on previous answers. However, you are still allowed to choose who you ask each of your three questions to dynamically. Scoping is also dynamic; e.g. the pronoun "you" in a question will always refer to the person to whom you are currently asking a question, not a predetermined person). No time related questions (e.g., "if the answer to my second question was 'no', then X otherwise Y") are permissible, as this could lead to paradoxes within the space-time continuum). Finally, note that if you ask Past your first question or Future you last question, the answer will give you no additional information because you do not know what the last or next questions are!!

Note 3: This awesome riddle was actually designed by the contributor, Eric Yeh! E-mail him feedback: click here

You can start flipping a coin, and at any time claim a prize in cents equal to the fraction of flips that came up heads. So, if you stop playing after getting 4 heads in 5 flips, you earn 80 cents. How much is the game worth?

I have a distribution over the Reals which you do not know. I choose two numbers from it, and write them inside envelopes. You are given one of the envelopes, and allowed to see the number inside it. Then, you are given the option to switch envelopes once. After you settle on an envelope, you win the amount inside your envelope, and you pay the amount inside the other envelope. Can you win money playing this game, with a strategy independent of my distribution?

Create the number 24 using only these numbers once each: 2, 3, 10, 10. You may use only the following functions: +, -, *, /. This is not a trick question; for example, the answer does not involve a number system other than base 10 and does not allow for decimal points.

Create the number 24 using only these numbers once each: 1, 3, 4, 6. You may use only the following functions: +, -, *, /. This is not a trick question; for example, the answer does not involve a number system other than base 10 and does not allow for decimal points.

An enemy submarine is somewhere on the number line (consider only integers for this problem). It is moving at some rate (again, integral units per minute). You know neither its position nor its velocity.

You can launch a torpedo each minute at any integer on the number line. If the the submarine is there, you hit it and it sinks. You have all the time and torpedoes you want. You must sink this enemy sub - devise a strategy that is guaranteed to eventually hit the enemy sub.

willywutang is lonely and needs a wife. So he flips through a phone book and plans to date exactly N women at random, none of whom he knows anything about beforehand. To expedite the process, after going on just one date with a woman, he must immediately decide whether or not she is "the one"; this decision is irreversible. Devise an algorithm willy should use to maximize his chances of choosing the best woman in the set. Convince willy that your algorithm is optimal.

A thousand wires hang on a very high tower, so high that you cannot see what tip belongs with what bottom. This is something you are interested in knowing. You have a battery and a light bulb which will light up if two wires connect it to the battery with appropriate polarity (i.e. the battery and bulb each have two contact points, and one of each is + and the other side is -). Wires may be tied together to form longer wires, and you can see the bulb light up even if you are on the opposite side of the tower. Since the tower is so high, you want to minimize the number of times you have to climb up and/or down the staircase, regardless of how much you have to do while you are at the top or bottom. What is the minimum number of traversals required?

You have a checkerboard which extends infinitely in all four directions. One half-plane is covered with checkers on all the black squares. You can jump pieces using normal checker jumps, but must remove the pieces that are jumped. How many rows into the uncovered half-plane can you get a checker?

Repeat the problem where all squares are covered, and jumps are vertical and horizontal instead of diagonal as in standard checkers.

In complex analysis, an entire function is defined as a function which is infinitely differentiable at every point in C (for example: constants, polynomials, e^x, etc.). Picard's Theorem says that every nonconstant entire function f misses at most one point (i.e. f(C) = C or C-{x0}). For example, every nonconstant polynomial hits every point, and e^x misses only 0.

Now consider the function f(x) = e^(e^x). Since e^x is entire, f is also entire by the chain rule. But it misses 0 since the base e^y misses 0, and it misses 1 since the top e^x misses 0 so that e^(e^x) misses e^0 = 1. But by Picard's Theorem there can be only one missing point, so the two missing points must be the same. Therefore, 0 = 1.

Alice and Bob are going to play a game, with the following rules:

• Alice picks a probability p, 0 <= p < 0.5
• Bob takes any finite number of counters B.
• Alice takes any finite number of counters A.

These happen in sequence, so Bob chooses B knowing p, and Alice chooses A knowing p and B.

A series of rounds are then played. Each round, either Bob gives Alice a counter (probability p) or Alice gives Bob a counter (probability 1-p). The game terminates when one player is out of counters, and that player is the loser.

Whom does this game favor? Analyze and discuss probabilities.

A duck is in a circular pond with a menacing cat outside. The cat runs four times as fast as the duck can swim, but cannot enter the water. Can the duck get to the perimeter of the pond without the cat being on top of him?

A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.)

Someone claims to have invented a Universal Truth Machine (UTM), a machine that takes a proposition as input, and returns "true", "false", or "undecidable" as output. Example:

Devise a true proposition that the UTM will claim to be false, thereby disproving the inventor's claim.

Note: Revised 8/8/2002 4:39PM.

( From Raymond Smullyan's book What is the Name of This Book? )

In WitNoTB?, Smullyan introduces his Knights, Knaves, and Normals. Knights always tell the truth, Knaves always lie, and Normals can do either. In the subchapter titled "How to Marry a King's Daughter", Smullyan tells the story of a king who wants his daughter to marry a nice normal Normal, not one of those goody-goody Knights or devious scoundrel Knaves. Smullyan asks the following questions (easy puzzles):

• How can you make a true statement that will convince the King you are a Normal?
• How can you make a false statement that will convince the King you are a Normal?
• How can you make a statement that will convince the King you are a Normal, but he won't know whether it's true or false?

Then Smullyan tells the story of a different King, one who is not so kindly disposed towards Normals. In fact, he sees them as wishy-washy girly-men, unreliable and untrustworthy. A Knight will always be true, and a Knave is wholly reliable as long as you remember to believe the exact opposite of what he says, while a Normal will deceive you when you least expect it. He wants his daughter to marry anyone but a Normal. Smullyan asks: how many statements must you make to convince the King?

Smullyan's answer was: no statements you make can ever convince the King you are no Normal. Since a Normal can say anything, any statement you make could be made by a Normal. There is no way to prove your abnormality to the King.

Smullyan was wrong! There is a subtle flaw in his argument, and in fact it is quite possible for a non-Normal to prove it. So the puzzle for you is (harder puzzles):

• How can you, in one statement, convince the King you are a Knight?
• How can you, in one statement, convince the King you are a Knave?
• How can you, in one statement, convince the King you are not a Normal, but leave him unable to deduce whether you are a Knight or a Knave?

Note: Problem presentation by Jonathan Haas.

At a movie theater, the manager announces that they will give a free ticket to the first person in line whose birthday is the same as someone who has already bought a ticket. You have the option of getting in line at any time. Assuming that you don't know anyone else's birthday, that birthdays are distributed randomly throughout the year, etc., what position in line gives you the greatest chance of being the first duplicate birthday?

A particle is travelling from point A to point B. These two points are separated by distance D. Assume that the initial velocity of the particle is zero. Given that the particle never increases its acceleration along its journey, and given that the particle arrives at point B with speed V, what is the longest time that the particle can take to arrive at B?

There are three omniscient gods sitting in a chamber: GibberKnight, GibberKnave, and GibberKnexus, the gods of the knights, knaves, and knexuses of Gibberland. Knights always answer the truth, knaves always lie, and knexuses always answer the XOR of what the knight and knave would answer.

Unfortunately, the language spoken in Gibberland is so unintelligible that not only do you not know which words correspond to "yes" and "no", but you don't even know what the two words that represent them are! All you know is that there is only one word for each.

With only three questions, determine which god is which.

Note 1: What follows are standard rules that are generally assumed unless otherwise noted. The gods only answer yes/no questions. Each god answers in the single word of their language as appropriate to the question; i.e. each god always gives one of only two possible responses, one affirmative and one negative (e.g. they would always answer "Yes" rather than "That would be true"). Each question asked must be addressed to a single specific god; asking one question to all the gods would constitute three questions. Asking a single god multiple questions is permissible. The question you choose to ask and the god you choose to address may be dynamically chosen based on the answers to previous questions. No self-referential questions (e.g. "is this question true iff ...").

Note 2: Because of possible loop conflicts, you may not ask any questions regarding how a knexus would answer.

Note 3: Designed by the contributor, Eric Yeh! E-mail him feedback: click here.

The town of Friendville has an interesting property. Given any two people in the town, they either know eachother or they don't. If they don't know eachother, then they can be introduced to eachother. One single introduction will work for both people. That is, "Tom this is Phil, Phil this is Tom" counts as one introduction.

The other interesting property that this town has, is that if any group of n people get together, the number of introductions that must be made in order that everyone in the group knows everyone else is at most n-1.

Problem: Prove that the town can be divided into two groups (A and B) such that everyone in group A knows each other, and everyone in group B knows each other.

There are two houses of parliament in the land of Orange Milano. Each member of parliament has at most 3 enemies. PROVE that all the members can be placed in a house such that each member will have at most one enemy in the same house.

What is the mean distance between two random points on a unit square?

This is a magic trick performed by two magicians, Alice and Bob, with one shuffled deck of N unique cards. (Nothing is mentioned about suits: you may consider these cards to be simply enumerated from 1 to N.) Alice asks a member of the audience, Carol, to randomly select 5 cards out of a deck. Carol then returns her chosen 5 cards to Alice. After looking at the 5 cards, Alice picks one of the 5 cards and gives it back to Carol. Alice then arranges the other four cards in some way, and gives them to Bob in a neat, face-down pile. Bob examines these 4 cards and determines what card is in Carol's hand (the missing 5th card). Carol is astonished!

• What is the largest number of cards N that the deck can contain before the trick is no longer performable? Prove it.
• How specifically do you execute the trick on a deck of maximal size N?

Note 1: There's no secretive message communication in the solution, like encoded speech or ninja hand signals or ESP or whatever ... the only communication between the two magicians is encoded in the 4 cards transferred from Alice to Bob. Think of these magicians as mathematicians.

Note 2: Essentially, this is the same 5 card magic trick, but now I am challenging you to get away with it using a deck larger than 52 playing cards.

100 prisoners in solitary cells. There's a central living room with two light bulbs. The initial states of these light bulbs is unknown. No prisoner can see these light bulbs from his or her own cell. Every now and then, whenever he feels like it, the warden picks a prisoner at random, and that prisoner enters the central living room. While there, the prisoner can toggle the bulbs if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be executed. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the warden begins this sick game, the prisoners are allowed to get together one night in the cafeteria to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion? (Alternatively phrased: Devise an algorithm that has a 100% chance of success, optimizing for the expected number of warden choices until success.)

After that, try generalizing to N light bulbs (disclaimer: I don't know where this N bulb thing leads).

Note: Summary of differences between this riddle and the notorious "100 prisoners and one light bulb":

• two light bulbs
• initial state of bulbs is unknown
• warden chooses whenever he feels like it, rather than once a day.

There are three omniscient gods sitting in a chamber: AND, OR, and XOR. They all answer the truth, but they all apply their namesake operations in one of the following ways:

• BACKWARD: The operator is applied to ALL of the questions that have been asked THUS FAR.
• UNIVERSAL: The operator is applied to ALL of the questions (you have to pick your questions beforehand).
• SELFLESS: The operator is applied to ALL of the questions NOT asked to them (you pick your questions beforehand).

For each of the 3 cases, determine with proof the minimum number of questions that will allow you to identify which god is which.

Note 1: (Standard; rules that are generally assumed unless otherwise noted.) The gods only answer yes/no questions. Each god answers in the single word of their language as appropriate to the question; i.e. each god always gives one of only two possible responses, one affirmative and one negative (e.g. they would always answer "Yes" rather than "That would be true"). Each question asked must be addressed to a single specific god; asking one question to all the gods would constitute three questions. Asking a single god multiple questions is permissible. The question you choose to ask and the god you choose to address may be dynamically chosen based on the answers to previous questions.

Note 2: (Specific) Because of possible time conflicts, you must determine your questions ahead of time, rather than based on previous answers. However, you are still allowed to choose who you ask each of your three questions to dynamically. Scoping is also dynamic; e.g. the pronoun "you" in a question will always refer to the person to whom you are currently asking a question, not a predetermined person. No time related questions (e.g., "if the answer to my second question was 'no', then X otherwise Y") are permissible, as this could lead to paradoxes within the space-time continuum.

Note 3: Another gem designed by Eric Yeh. E-mail him feedback: click here.

You roll a k-sided die n times. What is the probability that each of the k faces appeared at least once?

The set of numbers {9, 99, 999, 9999, ...} has some interesting properties. One of these has to do with factorization. Take any number n that isn't divisible by 2 or by 5. You will be able to find at least one number in the set that is divisible by n. Furthermore, you won't need to look beyond the first n numbers in the set.

Prove it.

There are three puzzlers in the puzzle forum: A Newbie, a Senior Riddler, and an Uberpuzzler. All three are honest, but can only give answers to the best of their knowledge.

Newbies are confused creatures. Until their fifteenth posts, they are only able to make random responses!*

Senior Riddlers have great powers of perception, but are not yet infallible. In fact, they have been known to give incorrect responses up to once per day!** They are always able to deduce the identities of their fellow puzzlers, but have no access to individual thoughts or the future.

Uberpuzzlers are omniscient beings who are your greatest allies in the Puzzle Forum!!! Not only do they always know and tell the truth, but they also have a special power of Influence! Uberpuzzlers are able to telepathically communicate with anyone else in the room, and thereby clarify the person's thoughts so that he knows the answer to the current question. However, they must do so BEFORE the other person chooses an answer, or it may be too late.

The Uberpuzzler can exert Influence arbitrarily often. However, before each session in the Puzzle Forum, he randomly chooses a limit for how many times he will apply his special power (i.e. how helpful he will be). The result is a secret; all you know is that the limit is always a positive integer.

Furthermore, an Uberpuzzler only uses his power of Influence in a very specific way. First, he determines the goal of the puzzler (which may, for example, be to identify all three puzzlers in five questions). Then he will determine the strategy of the puzzler (in this case, it would be a binary tree of questions, with each node determining a question and the person who should be asked; i.e. a fully dynamic set of questions and answerers). Finally, IF POSSIBLE UNDER HIS CHOSEN INFLUENCE LIMITATION, he will determine circumstances (in this case, questions following certain reply paths such as TFF or T or TFFTF) for each possible situation (in this case, permutations of the three people) under which he would apply his Influence, such that over all situations, the final set of responses would be distinct relative to the situation.

(Thus, he employs a strategy defined as a mapping

f : S3 x {(T|F)*} -> {0,1},

which can be interpreted as follows: for each ordering of the puzzlers "sigma" (a permutation in S3, e.g. USN) and set of responses "s" (a string in (T|F)*, e.g. TFTF), he will exert Influence on the question following a response of s in the permutation sigma iff f(sigma,s) = 1. The Uberpuzzler may choose ANY mapping f such that the strings of all possible responses will be disjoint for the six orderings of the puzzlers -- IF POSSIBLE given the limitations.

Note that this is different from saying that the puzzler chooses when the Uberpuzzler applies Influence! In general, the Uberpuzzler may have more than one way to make the answer sets disjoint, but the puzzler will not know which one he is employing!!!)

Determine with proof the minimum number of questions which will allow you to identify which puzzler is which.

[* The Newbie does not make any new posts during questioning. ;) ]

[** It is assumed that the question asking session takes place during the confines of one day.]

Note: Writing credits to Eric Yeh! The titles in this riddle are taken after various member rankings you can earn in our wonderful riddle forum. E-mail him feedback: click here

Willywutang recently took a personality test ... he failed :)

Actually, the test was set up so he couldn't fail. There were four personality "colors", and the objective was to decide which color was strongest in him. There were three test sections, and in each section, he had to rank the four colors from 1 (weakest) to 4 (strongest).

At the end of the test, he summed up the rankings from each section to get his personality "profile". The minimum he could score on any color was therefore 3, and the maximum was 12. After he knew how he scored for each color, the test asked him to color in a circle (with crayons) in proportion to his color scores.

Willywutang complained that he didn't have a protractor to measure out the exact angles. (I wonder what this says about his personality?)

Willywutang then remarked loudly that the test makers could have divided up the circle beforehand (pie-chart style) and then he would only have to color between the lines. The natural question is, of course: What is the minimum number of divisions that must be made so that the circle can be colored to accurately represent any possible proportion of colors? How are these divisions arranged?

Note: Writing credits to James Fingas!

You have a deck of 52 cards - for convenience, number them 1 through 52. You cut the cards into two equal halves and shuffle them perfectly. That is, the cards were in the order 1,2,3,...,52 and now they are 1,27,2,28,...,26,52. Let's call this a perfect in-shuffle.

If you repeat this in-shuffling process, will the cards ever return to their initial ordering? If so, how many in-shuffles will it take?

How does the solution change if you have a deck of 64 cards, or 10, or in general, n cards? For odd integer values of n, in-shuffling will take 1,2,3,...,n to 1,(n+3)/2,2,(n+5)/2,...,n,(n+1)/2. For example, when n=5, the first shuffle in-yields 1,4,2,5,3.

What if you do out-shuffles instead? (27,1,28,2,...,52,26)

The diabolical Two-Face has acquired an atomic bomb, and is setting it to detonate somewhere in Gotham City in 2 days. Two-Face plans to deactivate the bomb only if the mayor agrees to pay him 2 bazillion dollars. The bomb can be deactivated with a 2,000 digit passcode that only Two-Face will know. In signature style, Two-Face wants exactly half of the passcode digits to be "2"s, and the other half to be "1"s.

Two-Face anticipates that Batman, the world's greatest detective, will probably find the bomb somehow. To reduce chances of Batman cracking the passcode and foiling the plan, Two-Face wants to choose a passcode equally at random, and without sacrificing the aforementioned symmetry. One way of doing this would be to just conjure "2"s and "1"s randomly off the top of his head, while making sure that in the end, the total number of "2"s equals the total number of "1"s. However, Two-Face doesn't trust his mind to be truly random. It sure would be nice if he had a computer or calculator to generate random numbers, but there are no such devices nearby. So Two-Face once again pulls out his fair-sided coin, the elegant tool he uses to make all decisions in life. Using only his coin, how can Two-Face construct a satisfactory passcode equally at random? And at least how long / how many flips will the construction take?

Note: Writing credits to William Wu =)

A Bright Star is a sphere, not just a point, that emits light in all directions from every point on its surface. A Dark Star is an opaque sphere whose dull black surface reflects no light. Dark Stars come in all sizes. Your assignment is to get and position a few of them around a given Bright Star in such a way as will absorb all its light, thus rendering it invisible from afar in every direction. What is the minimum number of Dark Stars required to carry out this task, and why?

Note 1: Brought to Math H90 at UC Berkeley by Jason Behrstock in 1995.

Note 2: I've decided to cross-list this riddle in the putnam section. The accessibility of the beautiful premise makes it suitable here, but the solution may seem more appropriate for a mathematical audience. Couldn't make up my mind.

Borromean Circles are three perfect circles (perhaps of different radii) made of wire and so artfully linked in space that they cannot be separated; however, if any one circle were removed, the others would fall apart. Example diagram:

Prove that perfect Borromean Circles are actually impossible to construct.

Note: (Useless historical information) Borromean circles were the symbol of the Borromean League founded in 1586 to reimpose Catholicism over Protestant areas of Switzerland, which was almost destroyed by consequent prolonged warfare. The League named itself after a controversial but widely admired St. Carlo Borromeo (1538-84, canonized in 1610), Cardinal and Archbishop of Milan, whose influential family had been established on the four little Borromean islands in Lake Maggiore, which runs North-East across the border between Italy and the Swiss canton of Ticino.

The Moonstone, a fabulous gem, has been stolen again. Witnesses saw one person steal it, but cannot describe him (or her) at all, nor has any physical evidence been found. Police suspect some one of the three most notorious jewel thieves may be responsible and have all three under close surveillance, including telephoto lenses and paraboloidal microphones, but lack a reason to arrest any of them. Each suspect, denying involvement in the theft, has expressed his curiosity: Who took the Moonstone this time? Later the three were observed dining together. Each one had occasion to leave their table and visit the lavatory; during his absence the two at the table flipped a (presumably fair) coin, hiding its face from the absentee (and from the surveillance team) but not from each other. After the third suspect returned, all three winked at each other and dispersed silently. The surveillance team saw only the back of one suspect’s head when he winked, so his wink was not recorded. The team says all three suspects know now whether one of them stole the gem but, if he did, the other two do not know which one did; and the team does not know whether one did. How was all this information communicated?

When equations z = z(y) and y = y(x) can be solved for x = x(z) satisfying z = z(y(x(z))), then 1 = dz/dz = (dz/dy)(dy/dx)(dx/dz) as if all the d...'s were parts of fractions that cancelled each other out.

But in a different situation when an equation f(x, y, z) = 0 can be solved for any one of the variables x, y, z as a function of the other two satisfying, for example, f(x, y, z(x,y)) = 0, then

(@z/@y)(@y/@x)(@x/@z) = -1

where "@" denotes the funky partial derivative symbol that looks like a reversed "6". Prove this last equation and explain why the "@"s don't cancel out the way the d...'s did.

3 overlapping circles are drawn to cut the plane into 7 finite regions, each with 3 circular arcs as its boundary. 7 coins are placed, 1 in each region, all Heads-Up. Then a game is played, consisting of a sequence of coin flipping steps. At each step a circle is chosen, and one of the following two operations is performed upon all coins in it:

• Operation A: Turn every coin Heads-Up.