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.
• Operation B: Reverse every coin.

The object of the game is to put the coin in the central (inside-most) region Heads-Down, and all other coins Heads-Up. Is this objective accomplishable?

Hint: Consider what each kind of operation will do the following predicate concerning an odd number of coins: "Every circle has an odd number of conis Heads-Down."

Alice and Bob play a game. Starting with Alice, they alternate in selecting digits for a 6-digit decimal number UVWXYZ that they construct from left to right. Alice chooses U, then Bob chooses V, then Alice chooses W, and so on. No digit can be repeated. Alice wins if UVWXYZ is not a prime. Can Alice always win?

Update 11/4/2002 8:42PM: There was a typo: I had written "Alice wins if UWXYZ is not a prime". Thanks [SWF].

Consider the following process:

1. Pick a positive integer.
2. Square each of digits and add the squares together, to get a new number.
3. Repeat steps 2-3 with the new number.

"Happy numbers" are numbers destined to reduce to one. "Sad numbers" are those that get stuck in an infinite loop of distinct numbers; for example, the loop { 89, 145, 42, 20, 4, 16, 37, 58, 89, 145, ... }.

In general, what kinds of numbers are happy, and what kinds are sad? Give a closed-form expression for which integers are happy, and which integers are sad.

Player A has n+1 coins, while player B has n coins. Both players throw all of their coins simultaneously and observe the number that come up heads. Assuming all the coins are unbiased, what is the probability that A obtains more heads than B?

A solid cube 20x20x20 is built out of bricks each 2x2x1 . All bricks are laid with their faces parallel to the cube’s faces, though bricks need not be laid flat. Prove that at least one straight line perpendicular to a face of the cube pierces its interior but no brick’s interior.

Consider a country in which people live in high buildings and buy things from street vendors, using some form of money. Each building is equipped with a pulley in the eaves over which runs a long rope with a basket on it, operable by either party. Is there a system by which a resident and a vendor who don't trust each other can conduct trade? Note that either party may plan to play the opposite role with someone else later.

You are given a Rubik's cube in a randomly chosen initial position. Denote a "move" as a 90 degree rotation of a face. "God's Algorithm" is the name of an algorithm which solves a Rubik's cube in the fewest number of moves.

1. Determine a lower bound for the number of moves God's Algorithm requires.
2. Determine an upper bound.
3. Can you devise a small, simple algorithm to solve a Rubik's cube in the minimum number of moves?
   (e.g. not brute-force lookup tables)

Note 1: Forum thread: click here

Note 2: What is a Rubik's cube? It is the most famous puzzle in history. Enro Rubik invented it in 1974, and already about one-eighth of the world's population has had its hands on it. The Rubik's cube consists of 27 smaller cubes. Initially, all faces of the cube are the same color. You can rotate 9-block sections of the cube to break this pattern, as illustrated by the image below. Afterwards, the objective is to return the Rubik's cube to its initial state of monochromatic faces. Given that you didn't know the steps taken to randomize the cube faces, this is surprisingly difficult to do.

Enro Rubik was a lecturer in the Department of Interior Design at the Academy of Applied Arts and Crafts in Budapest. While giving lectures, he liked to illustrate his ideas with actual models made from wood, cardboard, plastic, and other common materials. He created the cube as an experiment in aesthetic geometric forms, and to help students with spatial visualization. Rubik himself did not expect the process of returning the cube to its initial state to be so difficult. Eventually the Cube caught on as an international phenomenon. Today it is a common household item, and the subject of many mathematical papers.

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 in Roman numerals. What numbers are on the faces of the cubes to allow this? You can have as few (including zero) or as many numerals on a single face as you wish.

When the Prince of Trianglia (an island where all intersections are Ys, and no roads lead to dead ends) returned from his voyage of discovery, he issued two edicts:

1. Because he spent a month trapped by a washed-out road, new roads are to be built so that there is more than one route to every portion of Trianglia.

2. Because dirt roads are tiresome and boring, all roads will be paved with either red, yellow, or blue bricks (each road having only one color). The color of each road should be chosen so that every intersection is the meeting of roads of all three colors.

Can the Trianglians assign a color to each of the roads to satisfy the second edict? If so, how?

A quote from the "Fun Facts about Trianglia" Tourist brochure: "Trianglians are very superstitious about having things over their heads when they are travelling. There are no overpasses or tunnels anywhere in Trianglia."

Note: Writing credits to Paul Sinclair!

We have a discrete time signal x[n] that is bandlimited to pi/3. In other words, if X(w) is the discrete-time fourier transform (DTFT) of x[n], then:

for pi/3 < w < pi, |X(w)| = 0.

In the process of retrieving x[n] from a hard disk, one sequence value has become corrupted, resulting in a corrupted signal y[n]. The graphs below show the real and imaginary parts of the DTFT of y[n].

1. By examining the above graphs, estimate n₀, the index of the sequence value that has been corrupted. Explain.

2. If y[n₀] = x[n₀] + c, estimate c. Explain your reasoning.

Note 1: Requires some knowledge of the discrete-time fourier transform. A pretty cool puzzle nevertheless.

Note 2: Writing credits to Dr. Avideh Zakhor, UCB EE 123 Fall 2001. No, it's not from my homework this week ;)

Willywutang had been travelling for nearly two days when he came to the fork in the road. Willy knew it was inevitable, but he was prepared. Willy knew from the various puzzles he had solved that one path led to the City of Safety, and the other path led to the City of Cannibals. There should also be two people waiting at the intersection, who, willingly or not, would tell him how to get to the City of Safety ...

Slouched against a tree trunk near the intersection was a scruffy stranger. Willy stopped in his tracks and stared at the man, very worried. He was certain to be from one of the two cities, but which one? Where was the second person? The man returned Willy's gaze, saying nothing.

There was a tense silence, broken only when the mysterious stranger finally spoke up.

"If you're wonderin' where the other guy is, he's home sick today. You see, he's from the City of Cannibals, and someone came through here with a bad cold. You're lucky that I'm here, from the City of Safety!"

Willy was too much on his guard to be reassured by the scruffy man's story. Perhaps it was true, and perhaps it wasn't. Willy also knew the rules about getting directions--he could ask just one yes/no question. Is there any way Willy could find out which path led to the City of Safety?

Note: Writing credits to James Fingas!

Three criminals just robbed a bank and go back to their hideout. They put the money behind a high tech security door. There are 3 locks on the door, each activated/deactivated by a button next to it. All locks are originally deactivated, and once a lock is activated it is impossible to tell whether it is activated or not. The three criminals want to work out a system so that any two of them can access the money but a single criminal cannot. The 2 criminals accessing the money must be assured that all locks are deactivated, otherwise an alarm will sound, and built-in lasers will shoot them. Also, each criminal may only give information about which locks he toggled to one other criminal. Figure out how their system will work.

Here is the story of three unhappy people: Angelica, Bernardo, and Cameron. Angelica and Cameron have been friends since childhood. Cameron is hopelessly in love with Angelica, but Angelica has always thought of Cameron as "just a friend".

During high school, a new boy, Bernardo, moves into the area. Bernardo immediately catches the attention of Angelica, who falls head-over-heels for him. However, Bernardo is not interested in women--he is strongly attracted to Cameron. Cameron, of course, is jealous of Bernardo, because he has stolen Angelica's love away. Angelica is angry at Cameron, because she feels that Bernardo's lack of attention to her is Cameron's fault. Bernardo is jealous of Angelica, who recieves all of Cameron's attention. What are these three to do? (Please, this is a rhetorical question--there is no need to answer it)

One day, you meet them, all together in a chat room. They are all using nicknames: Uberkewl, Vaxxipaxx, and Willywutang (in no particular order). Because they are so jealous and screwed-up, each of them will only answer a question truthfully only if:

1. one of your last two questions was to their sweetheart, and
2. your last question wasn't to the person with whom they are upset.

Otherwise, they will answer spitefully--giving you the answer that will confuse you the most.

Your task is to figure out who is who. Is it possible? If so, how many questions might you have to ask?

Note: Writing credits to James Fingas!

There are three families, each with two sons and two daughters. In how many ways can the sons all be monogamously matched with the daughters?

Generalize to M families, each with N sons and N daughters.

Note: Assume you can't marry within your own family, and all persons are heterosexual. Also, no one has a sex change.

In the Hemlock Grove retirement villa, four seniors are discovering the joys and sorrows of a "love square". Amelia, Bertrand, Claire, and Donald have gotten themselves mixed up in a little more than they can handle.

Amelia has fallen for Bertrand, with his youthfully craggy face and his deep gravely voice. Bertrand does not realize this, and secretly admires Claire, with her youthful temperament and derring-do. Claire is oblivious to Bertrand's feelings, and is instead obsessed with Donald and his mysterious past. Donald doesn't know that Claire is interested in him, but he has the hots for Amelia.

Of course, Bertrand realizes that Claire likes Donald, and has secretly vowed to get Donald on the bad side of the cleaning staff. Donald shares Bertrand's emnity, since his beloved Amelia is bewitched by the old git. He has been trying to get a bird to build its nest over top of Bertrand's patio door for nearly a year now.

Amelia recognizes the glint in Bertrand's eye when he looks at Claire, and she is determined to sabotage Claire's next candlelight supper by replacing her baking powder with powdered salt. Claire is likewise jealous of Amelia, that slut, and she plans to run her over on the sidewalk with her electric three-wheeled buggy.

One day, you meet all four of these unhappy individuals in a chat room, going under the nicknames UsUxOrZ, VampireBob, WussMania, and Xanadu. Because they are all slightly crazy (they are in love after all), each person will only answer a question correctly if:

• one of your last two questions was asked of their sweetheart, and
• your last question was not to their enemy.

Otherwise, they will tell you whatever they feel like telling you. Is there any way that you can deduce the identities of these four individuals? How many questions must you ask to determine who is who?

Note: Writing credits to James Fingas!

A man is stuck in a box. There are no doors, no windows, no openings of any kind. Inside with him is a round table and a mirror. How does he get out?

Big Hint: This is perhaps an unfair riddle. You'll need a cute sense of humor to solve it without this hint. Think wordplay.

Imagine an infinitely extending grid of squares. Between every two adjacent intersection points is a resistor of 1 ohm. Compute the resistance between two adjacent intersection points.

Note: Anyone know how to solve this problem by comparing resistance to commute times of random walks on graphs? H_uv + H_vu = 2mR_uv, where H_uv is the hitting time between vertices u and v, and R_uv is the resistance between u and v. We should be able to show that the ratio of commute time to edges converges to a stable value as the grid size approaches infinity. E-mail me at wwu at ocf.berkeley.edu if you have an idea.

A great advance has occured in the field of artificial intelligence. A computer has been programmed to predict your actions, and has proven itself able to do so with amazing accuracy. You have put it through many difficult and devious tests, yet it has always been correct in its predictions. A certain multibillionaire with a twisted sense of humor has decided to reward you for your great discovery. He take you into a room with two boxes and tells you that box A contains $10,000 while box B either contains nothing, or a certified check for 1 billion dollars. You will be allowed to open exactly one box and keep it contents. The catch is this: Earlier, your program was asked what you would do. If the computer predicted you would open box A, then the 1 billion dollar check was placed in box B. If the computer predicted you would open box B, the box will be empty. Which box should you open?

Note that box B was prepared before you enter the room.

Note: From the pages of Martin Gardner. "Newcomb" refers to William A. Newcomb, a physicist at Lawrence Livermore Laboratory, who came up with the puzzle in 1960.

Find different arrangements of the 13 pieces below to form two different figures: a (non-square) rectangle and a square. Each shape must use all 13 pieces as part of the shape. Click here for a larger figure more suitable for printing and cutting.

Note: Writing credits to [SWF].

Turkey Sandwich was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Turkey awoke early in the morning, aroused by devilish laughter, only to see an impish looking homunculus sitting at the bottom of the bed next to a seemingly infinite pile of chips. Hello Turkey it said, would you like to play a little game? This pile contains 43546758343209876 chips and the bottom chip represents your immortal soul. The rules are quite simple. The first player takes some chips, but not all of them. After that we take it in turns to take some chips.

The only rule now is that a player cannot take more in their turn than the previous player took. The winner is the player who takes the last chip. If I win I get to keep your soul and if you win, you get an A in the test. Would you like to go first or second? This seemed a reasonable bet to Turkey. Can you give Turkey a strategy for playing no matter how many chips there are?

Note: Writing credits to Alan Frieze and Danny Sleator.

Is it possible for two checker players, playing cooperatively, to king all twelve of both players' checkers? Keep in mind the following rules of checkers:

1. The initial checkers setup is to use only the black squares of a chessboard, with red checkers on the 12 North-most squares, and black checkers on the 12 South-most squares.
2. Players alternate turns, and cannot pass their turn
3. If a player can "jump" an opposing player's piece, he must do so. This is where all the difficulty arises.
4. If a player cannot jump, then he must move one of his checkers diagonally. All non-kinged checkers can only move forward.
5. When a checker gets to the opposing end of the board, it is "kinged" and can now move backwards as well as forwards.

Note: Writing credits to James Fingas, who doesn't know the answer either :)

1/19/2003 1:56AM

Two cylinders of equal radius are intersected at right angles as shown at left. Find the volume of the intersection between the two cylinders, without using calculus! A 3D picture of the intersection is shown at right.

Hint (medium hint - exactly which high school formulae you need): 1) Area of circle = pi * radius², and 2) Volume of sphere = (4/3) * pi * radius³

Note: Solved by the mathematician Archimedes (287 B.C. - 212 B.C.), waaay before calculus came around!

1/19/2003 1:56AM

Here's the puzzle: How do you make sense of this puzzle? I'd like to salvage the following interesting puzzle such that it is solvable, but I don't know how to -- or even if the answer is supposed to be that it's not solvable. Exact quote:

I think it's supposed to be a good puzzle because the page I found it on had it next to sink the sub and single-file hat execution, as examples of problems the webmaster discusses with his CS faculty. Problem is, I don't know what entails not trusting B. Does it mean B will translate our English queries reliably, but won't reliably tell us if A responds in Tamil properly? I e-mailed the author for clarification and his answer was meaningless, and then I e-mailed again and he stopped responding (I think he's sick of me). I won't reprint his e-mail address here. Perhaps we can figure out what is necessary to fix the problem?

Note 1: I believe the riddle is supposed to say "you want to test that A knows Tamil" instead of "you want to test that A knows B."

Note 2: [redPepper] from the riddle forum offers the following amusing answer:

1/19/2003 1:56AM

A taut rubber band connects a wall to the back side of a toy racecar 1 meter away. Starting at time t=0, the racecar drives away from the wall at 1 meter per second, stretching but never breaking the rubber band. At the same time, an ant resting on the rubber band near the wall starts to move toward the racecar at 1 centimeter per second. Does the ant ever reach the racecar? If so, in exactly how much time? Why?

Note 1: Treat the ant as a dot, like in geometry. Its initial position at t=0^- is 0 distance away from the wall.

Note 2: Assume that the angle of incidence between the rubber band and the wall never changes. (In other words, this is all happening along one dimension.)

Note 3: Does this remind you of something related to cosmology ("the study of the physical universe considered as a totality of phenomena in time and space")?

Note 4: Forum thread (spoilers galore, but interesting physics discussions): click here

1/19/2003 1:56AM

A bacterium asexually reproduces k children for the next generation according to a probability distribution P(X = k), where X is a random variable that returns the number of children it has between 0 and +infinity. After reproducing, a bacterium dies.

1. What is the probability that the bacterial colony lasts forever?
2. In general, what statistical property should an offspring distribution have to ensure immortality?

Note: A complete answer to the 2nd question should discuss two cases, one of which is a special case.

2/3/2003 3:30PM

Imagine the object above in the figure to the left made from perfectly elastic material. Can you transform it so as to unlink the two rings as in the figure on the right? One possible way is to cut one ring, move the other ring through the gap, and rejoin the the first ring exactly as it was. That would be a legitimate topological transformation. However, it is also possible to transform the first shape into the second without any cutting, simply by manipulating the objects in the appropriate manner (stretching, bending, but not breaking). Can you see how to do it?

2/5/2003 3:57AM

A prisoner is awaiting execution by firing squad. A row of N robotic soldiers stands nearby.

These robotic soldiers can be in a finite number of states (they are all finite state machines). A clock provides a sequence of time steps: 0, 1, 2, etc.. At each step, the state of each soldier is given by a transition function. This function takes three arguments as input: the soldier's previous state, the previous state of the soldier to the right, and the previous state of the soldier to the left. The transition function must be identical for all soldiers except for the soldiers at the ends of the row, whom could have different transition functions.

One of the soldiers at one end of the row is deemed the general of the squad. Initially at time 0, the general is in state q_init, whereas all other soliders are in state q_sleep. The objective is to get all soldiers to enter the state q_bang simultaneously for the first time, thereby riddling the prisoner with N bullets.

Design state machines and transition functions for the robotic soldiers which will accomplish this objective, given that the number of states for a soldier cannot depend on N. What is the running time of your system in terms of N?

Hint (achievable running time): If your machines are sufficiently clever, you can achieve O(N) time! There's even a solution that takes exactly 2N - 2 time steps.

Note 1: If we did not specify "for the first time", a trivial solution would be to have all soldiers keep firing, and eventually they will all be in state q_bang.

Note 2: In a sense, the heart of this problem is that no soldier knows what N is.

Note 3: Problem originally posed by J. Myhill in 1957.

Note 4: This problem describes something called a cellular automaton. The soldiers are like "cells", and how a cell is updated depends on the state of nearby cells. Perhaps the most well-known cellular automaton is John Conway's Game of Life.

2/5/2003 4:00AM

The number of ascents in a permutation is the number of times when one number is greater than the one directly preceding it. Examples: [1,2,3,4,5] has 4 ascents in it, (2>1, 3>2, 4>3, 5>4), [1,4,3,2,5] has 2 ascents in it, (4>1, 5>2), and [5,4,3,2,1] has none.

Create a program to count the number of permutations of n distinct numbers with exactly r ascents in it.

2/5/2003 4:00AM

1. Discrete-Case
   

   N cities are located at integer coordinates on a Cartesian grid. Your task is to lay down roads along the grid such that all the cities are connected, and the total amount of road you lay down is minimized. Devise an algorithm to solve this problem in general.

2. Continuous-Case
   

   N cities are located at real coordinates on the Cartesian plane. Your task is to lay down roads such that all the cities are connected, and the total amount of road you lay down is minimized. Devise an algorithm to solve this problem in general.

3. N-Dimensional Case
   

   N cities are located at real coordinates in an N-dimensional world. Your task is to lay down roads such that all the cities are connected, and the total amount of road you lay down is minimized. Devise an algorithm to solve this problem in general.

Note 1: (potentially unnecessary clarification) I use the modifier "connected" in the graph theory sense, meaning there exists a path from one city to any other city. In the Discrete-Case, when I say "along the grid", I mean that roads can only travel horizontally or vertically. A road network is comprised of line segments, and the endpoints of any line segment should lie on integer coordinates. Also, note that the problem does not restrict the endpoints of a line segment to the locations of the cities. So it will often be beneficial to invent intermediate points where roads should intersect. Finally, of course the more efficient your algorithm is, the better.

Note 2: John Leen, who did graduate research on bubble surfaces, told me what the problem is officially called. The discrete case is called the Rectilinear Steiner Tree problem, and the continuous case is the Euclidean Steiner Tree problem. Formally, you are given a weighted graph in which a subset of the vertices are identified as terminals, and you want to find a minimum-weight connected subgraph that includes all terminals. In general, finding a Steiner Tree is NP-hard.

Note 3: [Icarus] from the forum gives us some fascinating facts: 'The continuous case can also be approached by experimental means. Set up a map on a board and place pegs at the location of each town. Place a second thin board on top to form a "peg sandwich". Dip the contraption in a good bubble solution an after when you pull it out, cut holes in the thin board to allow any trapped air to escape. The remaining bubble film between the pegs should follow the lines of a road system that is a local minimum (that is, small variations will all be longer, but it is possible that a major variation would be shorter).'

2/2/2003 3:31AM

A hacker is attacking a computer network. Each computer on the network is connected to various other computers. The hacker releases a worm on a source computer. When a worm infects a computer, that computer can propagate a copy of the worm to a connected computer at a rate of once per second. Suppose the hacker knows the layout of the network; i.e., he knows which computers are connected to which. How should the worm proceed to infect the whole network as quickly as possible?

Also, if possible, describe an algorithm for computing the minimum time till total network infection. (Admittedly a computer science background will help here, but it is not absolutely necessary.)

Note 1: Writing credits to Yosen Lin.

Note 2: (Updated 4/7/2003 1:11AM) It appears that Yosen has rediscovered a very difficult problem, the minimal gossip time problem. None of us know of a good solution to this besides brute-force, which would take really, really long. There is some tradeoff involved between graph bushiness and branch depth, which leads me to suspect that the problem is NP-hard. If anyone has some clever ideas, please e-mail me.

3/9/2003 4:48AM

Given a bunch of (x,y) coordinates that form the vertices of one non-self-intersecting polygon, how would you go about finding the area of that polygon? What is the most clever / elegant solution you can devise? The desired answer is remarkably simple.

Note: Notice I did not say the polygon has to be regular or convex. A regular polygon has all sides of equal length. A convex polygon is a polygon such that all line segments formed between any two vertices must lie inside the polygon boundaries.

Let us distinguish Towns from Cities. Airlines avoid cancelling service between cities for fear of losing busy airports’ gate assignments to competitors. However, in hard times, airlines do cancel nonstop services between towns, and sometimes cancel nonstop services between towns and cities. The FAA insists that every town be connected to at least one city by nonstop airline service. Every town is so connected now, and some towns to more than one city. Suppose that, for every collection of towns, the number of towns in the collection does not exceed the number of cities each connected currently by nonstop airline service to at least one town in the collection. Show how airlines can cancel some city«town nonstop flight services leaving no city connected to more than one town and yet every town connected to just one city, barely satisfying the FAA, without adding any new service to the flight-schedule. Explain why your chosen process works.

4/7/2003 12:17AM

Suppose you have an infinite number of small balls, all of which have been uniquely numbered from 1 upwards. What is more, you have an infinitely large bucket, by which I mean it can be made as large as necessary. You decide to fill the bucket by throwing in all the balls, in order. Starting from 1, every minute you throw in two balls. But every minute, an impish pixie takes one ball back out. He always extracts the lowest-numbered ball in the bucket.

For example :

	1st minute: You throw in Ball 1 and Ball 2. 
	                Pixie extracts Ball 1. 
	 
	2nd minute: You throw in Ball 3 and Ball 4. 
	                 Pixie extracts Ball 2. 
	 
	3rd minute: You throw in Ball 5 and Ball 6. 
	                 Pixie extracts Ball 3. 
	 
	                 and so on... 
 

QUESTION: After an infinite amount of time has elapsed, how many balls are in the bucket?

Argument 1: There is an infinite number of balls in the bucket. After 1 minute there is 1 ball. After 2 minutes there are 2 balls. After 3 minutes there are 3 balls, etc.

Argument 2: There are no balls in the bucket. If there are some balls in the bucket, what is the lowest-numbered ball? It can't be Ball 1; that was extracted after 1 minute. Similarly, it can't be Ball 2; that was extracted after 2 minutes. It can't be Ball 3; that was extracted after 3 minutes, etc.

If the phrase 'after an infinite amount of time has elapsed' bothers you, then we can change the problem so that the 1st put-in-and-take-out operation is completed in 1/2 minute, the 2nd operation is completed in 1/4 minute, the 3rd in 1/8 minute, and so on. Now you can ask the question after 60 seconds, and "infinite time" is not longer an issue.

4/7/2003 12:17AM

A property of ellipsoids is that if the inside surface is a perfect reflector, a ray of light originating at one focus will reflect off of the ellipsoid and pass through the other focus.

In the figure below FC is a portion of ellipse with foci A and B. DE is a portion of a larger ellipse also having foci A and B. Arcs CD and EF are part of the circle with center B. Points A, C, and D lie on the same line and A, E, and F are also collinear.

Think of a perfect reflector made by revolving this shape about line AB to form an axisymmetric shape. Any photon originating at A must strike one of the ellipsoid surfaces and will be reflected toward B. For photons orginating at B, some strike the ellipsoids and reflect toward A, but some also strike the spherical portion of the reflector and come right back to B.

Take two small identical objects of the same temperature and place one at A and the other at B inside the reflector. Also the rest of the space inside the reflector is vacuum. Objects emit thermal radiation based on temperature in the form of photons. All the radiation from A strikes B. Only a fraction of that emitted from B arrives at A. So with time B will become hotter than A. In theory, this temperature difference can be used to generate power.

If this would not work, why not? If it would work, why aren't ellipsoids being used to generate power?

4/7/2003 12:17AM

Take any three circles of differing radius in the plane. For each pair of circles, draw two tangent lines that touch both circles and cross each other outside the convex hull of the circles. You now have three intersections, one for each pair of circles. Prove that these three points lie on a line.

4/7/2003 12:17AM

A game begins with 1.e4 and ends in the fifth move with knight takes rook mate. Reconstruct the game.

Note: This puzzle has apparently stumped many smart people, including Garry Kasparov, Anatoly Karpov, Mikhail Botvinnik, and Ken Thompson (a la Unix and C). Major kudos if you solve it yourself!

4/7/2003 12:17AM

In a stripped-down version of Conway's game of life, cells are arranged on a square grid. Each cell is either alive or dead. Live cells do not die. Dead cells become alive if two or more of their immediate neighbours are alive. (Neighbours to north, south, east and west.) What is the smallest number of live cells needed in order that these rules lead to an entire N X N square being alive? And how should those cells be arranged? Prove your claims.

In a d-dimensional version of the same game, the rule is that if d neighbours are alive then you come to life. What is the smallest number of live cells needed in order that an entire N X N X ... X N hypercube becomes alive? And how should those live cells be arranged? Prove your claims.

Note: From David MacKay's book Information Theory, Inference, and Learning Algorithms.

4/7/2003 12:17AM

1. What is the area of the smallest ellipse that can be circumscribed around a 3-4-5 triangle?

2. What is the area of the largest ellipse that can be inscribed in a 3-4-5 triangle?

Exact answers only.

Note 1: This one comes from Jakob Steiner, a Swiss geometer in the 19th century.

Note 2: A cool quote from the great Martin Gardner about this problem: "... it is one of the best examples I know of a problem that is difficult to solve by calculus or analytic geometry but is ridiculously easy if approached with the right turn of mind and some knowledge of elementary plane and projective geometry." Thanks [Icarus].

4/7/2003 12:17AM

The southeast puzzle is played on a semi-infinite chessboard, starting at its northwest (top left) corner. There are three rules:

1. In the starting position, one piece is placed in the northwest-most square, as shown in (a).
2. It is not permitted for more than one piece to be on any given square.
3. At each step, you remove one piece from the board, and replace it with two pieces, one in the square immediately to the East, and one in the the square immediately to the South, as illustrated in (b). Every such step increases the number of pieces on the board by one.

After move (b) has been made, either piece may be selected for the next move. (c) shows the outcome of moving the lower piece. At the next move, either the lowest piece or the middle piece of the three may be selected; the uppermost piece may not be selected, since that would violate rule 2. At move (d) we have selected the middle piece. Now any of the pieces may be moved, except for the leftmost piece.

Puzzle: Is it possible to obtain a position in which all of the ten squares closest to the northwest corner, marked in the rightmost figure (z), are empty?

Hint 1: What does this puzzle have to do with data compression?

Hint 2: Symbol codes.

Note: From David MacKay's book Information Theory, Inference, and Learning Algorithms.

5/11/2003 11:47PM

Below are 10 statements, all either true or false:

1. At least one of statements 9 and 10 is true.
2. This is either the first true statement or the first false stament.
3. There are three consecutive false statements.
4. The difference between the number of the last true statement and the first true statement divides the number which is to be found.
5. The sum of the numbers of the true statements is the number which is to be found.
6. This is not the last true statement.
7. The number of each true statement divides the number which is to be found.
8. The number that is to be found is the percentage of true statements.
9. The number of divisors of the number that is to be found (apart from 1 and itself) is greater than the sum of the numbers of the true statements.
10. There are no three consecutive true statements.

    Find the minimum admissible number (which is to be found).

On April 1st a typist found the hammers of the typewriter resoldered in an arbitrary order, so typing a text resulted in gibberish. The typist decided to type a document in its entirety using this typewriter. Afterwards, if the result does not represent the original text, he will type the result, and so on. Prove that the clear text will emerge sooner or later. How many iterations are enough to guarantee that the clear text will appear, if the typewriter has, say, 46 keys? N keys?

Author: Leonid Broukhis

5/27/2003 2:01PM

A particle starts at origin O in three-space. Think of the origin as centered in a cube 2 units on a side. One move in this walk sends the particle with equal likelihood to one of the eight corners of the cube. Thus, at every move the particle has a 50-50 chance of moving one unit up or down, one unit east or west, and one unit north or south. If the walk continues forever, find the fraction of particles that return to the origin.

Assume the earth is a perfect sphere. Show that at any given time, there exist two antipodal points with the same temperature.

The expected projected area of a convex set S is 1/4 the surface area of S.

The following hints outline one possible approach:

Hint 1: Think about the expected projection of a single line segment of length L. (this calculation should not be difficult)

Hint 2: With your work with respect to Hint 1 in mind, think about the line segments that make up a convex polygon. Consider the projections of a convex polygon.

Call a set of cubes incongruent if they all have different side lengths. Prove that it is impossible to exactly fill a rectangular box with incongruent cubes.

Note: The phrase "exactly fill" means that there is no space in the box which is not occupied by a cube, and that the cubes themselves should be packed together to form the shape of the rectangular box that envelops them.

There are a couple of ways of defining the 10-adics "A10". Conceptually, the easiest is to just "flip" traditional decimal notation: A 10-adic number has a decimal representation that can continue indefinitely to the left, but must terminate to the right. For example, instead of the infamous 0.999..., in the 10-adics you have ...999.0 = ...999.

Addition, subtraction, multiplication, and division are performed exactly as they are for real numbers. Carries that "go on to infinity" are lost. E.g. ...999.3 + 1 = 0.3.

For the most part, these operations obey the same rules as they do for real numbers. For instance, addition and multiplication are commutative and associative, and multiplication still distributes over addition.

On the other hand, there is no ordering ("a < b" is generally undefined for 10-adics). Thus, while irrational 10-adics may appear to be "infinitely big", the concept is without meaning for them.

The 10-adics do not require a "unary minus": ...999 + 1 = 0, so -1 = ...999.

Some challenges, in increasing difficulty:

1. For any 10-adic number x, describe how to calculate -x.
2. Find 1/7 as a 10-adic number. More generally, for integer N, describe how to calculate 1/N.
3. Show that the 10-adics possess zero-divisors (i.e. non-zero numbers whose product is zero).
4. Show that the 2-adics (same construction, but with base 2) do not possess zero-divisors. (The 2-adics form a field.) For what values of N do the N-adics possess zero-divisors?

Author: Paul Sinclair

Prove that there exists a 101 digit string which contains exactly one copy of every possible 2-digit string over the alphabet {0,1,2,3,4,5,6,7,8,9}.

Note: Check out forum thread Willywutang and the Number Stamp for hints and solutions.

A magician takes a deck of 36 cards (nine cards of each suit) lying face down. He predicts the suit of the top card, turns it up and puts aside. Then he predicts the suit of the second card, turns it up and puts aside, and so on with the entire deck. The deck for the trick was prepared by his secret assistant who knows the order of the cards. He uses the fact that the cards in the deck are slightly non-symmetric, and so the magician can distinguish between two possible orientations of every card. The assistant is not allowed to alter the order of the cards, but he can choose the orientation. What is the best strategy the magician and the assistant should agree upon in order to maximize the number of *guaranteed* correct predictions?

Source: Moscow Mathematical Olympiad.

(Nasty Geometry) Given a segment AB in the plane and a region R, as shown in the figure. It is desired to continue the line AB to the right of R. How may this be done with straightedge alone so that the straightedge never crosses R during the construction?

Clarification: The "straightedge" here is a classical Euclidian tool capable of constructing the straight line segment defined by any two arbitrarily chosen points, or extending an existing straight line segment an arbitrary distance in either direction (Thanks rmsgrey for pointing out).

• In drawing lowercase English letters a through z uniformly at random, the expected time till you see willywilly is 26^10 + 26^5.

• In drawing numerals over 0-9 uniformly at random, the expected time till you see 1231231 is 10^7 + 10^4 + 10.

• In flipping a fair coin, the expected time till you see HTHTTHT is 2^7 + 2^2.

See a pattern? Find it ... then prove it.

Forum thread: For a write-up of my solution, see thread Expected number of throws before n heads in a row.