Puzzle 11/1/2008:
Evaluate \int_0^{\pi} \ln(sin x) dx.

Puzzle 10/4/2008:
The numbers from 1-10 are arranged on a 5 point star placing a number where any two lines meet. Each line must have 4 numbers on it. Is it possible to arrange the numbers so that each line sums to 22?

Puzzle 9/6/2008:
Take a wire and have an infinite number of birds land on it at random. Take some paint, and for each bird, paint the interval from it to its closest neighbor. What proportion of the wire will be painted?

Puzzle 8/2/2008:
In this problem, the binomial coefficients are denoted by C(n,k) = n!/(k!(n-k)!). Find, if it exists, the limit as n goes to infinity of

Sum{kC(n-k,k)}/Sum{nC(n-k,k)},

where each sum is from k=0 to k=n/2.

Puzzle 7/5/2008:
There are n passengers waiting to board an n-seat plane, each having a unique seat reserved. However, Passenger 1 loses his ticket and chooses a random seat. Passengers then proceed boarding one by one. Every passenger sits in his own seat if not yet occupied, but chooses an independent random seat if his seat is already occupied. What is the probability that Passenger n will sit in his own seat?

Puzzle 6/7/2008:
This month's puzzle was created by Jim Propp and cannot be squeezed into a plain text email. So I refer you to the following web page: http://www.drunkmenworkhere.org/170.

Puzzle 5/3/2008:
Find the limit, as n goes to infinity, of e^{-n} [1 + n^1/1! + n^2/2! + n^3/3! + ... + n^n/n!].

Puzzle 4/5/2008:
The numbers 1 through N are written on slips of paper and placed in a hat. Two players take turns drawing numbers from the hat. If a player draws the number 1, the game is over and that player wins. If the player draws a different number, that slip of paper is destroyed and the turn passes to the next player. Who has the advantage, the player who goes first or the player who goes second?

Puzzle 3/1/2008:
The function f(x) = x - x^2 + x^4 - x^8 + x^16 - ... is well-defined for any x with |x| < 1. Does the limit of f(x) as x approaches 1 from below exist, and if so what is it?

Puzzle 2/2/2008:
In the song, "The Twelve Days of Christmas," the singer's true love gives him 12 partridges in a pear tree -- 1 each day for 12 days; he receives 22 turtle doves -- 2 each day for 11 days; he receives 30 French hens -- 3 each day for 10 days; and so on. How many gifts in total did the singer receive over all 12 days of Christmas? How many gifts would he have received if there had been 365 days of Christmas?

Puzzle 1/5/2008:
In the game of "No Tie War", an ordinary deck of 52 cards is shuffled, and 26 cards are dealt to each of two players. The players then have 26 showdowns, or tricks, with the higher ranked card winning (ace is high). If there is ever a tie, all the cards are immediately collected and reshuffled, and the game restarts. When the game finally ends (meaning there were no ties in any of the 26 tricks), each player counts the number of tricks he or she won and this becomes his or her score. The score will be somewhere from 0 to 26. Tricks won or lost prior to the last reshuffling do not count.

What is the probability that the game will end without requiring a reshuffle?

What is more likely: scoring at least 22 in a game of No Tie War, or flipping at least 22 heads in 26 coin tosses?

Puzzle 12/1/2007:
For what values of n can a cube be dissected into n (non-overlapping) sub-cubes?

Puzzle 11/3/2007:
How many 10-digit numbers are there whose digits are all distinct and which are divisible by 11111?

Puzzle 10/6/2007:
What is the minimum number of queens that can be put on an n x n chessboard so as to command or occupy all the squares? Solve this problem for n = 8, 9, 10, and 11.

Puzzle 9/1/2007:
Your friend Abe found a 6-sided die in the garbage. It is a strange die. First of all, it has no numbers on it. There are 3 red sides and 3 blue sides. Second of all, it is completely mangled. You can still roll it, though, and it will still land on one its 6 sides. But even though 3 out of 6 sides are red, the probability of red is unlikely to be 1/2 since it is mangled so badly.

Abe tells you and your friend Betty about this die, but he does not show it to you. So you have no information to try and guess the probability of red. (Assume you also have no information about the physics of mangled dice. This is an abstract math problem, so just assume you have no information whatsoever about the probability of red.) However, Abe does tell you one thing. He tells you that he rolled the die 3 times. The results, in order, were blue, blue, red. Betty turns to you and says, "I will wager my $7 against your $4 that the next roll will be blue." Assume Betty has no information about the die other than what has been described here. (She has not had any secret meetings with Abe, for instance.) Should you accept her wager? Why or why not? Is there a "right" answer to this problem?

Puzzle 8/4/2007:
Sleeping Beauty volunteers to undergo the following experiment. On Sunday she is given a drug that sends her to sleep. A fair coin is then tossed to determine which experimental procedure is undertaken. If the coin comes up heads, Beauty is awakened and interviewed on Monday, and then the experiment ends. If the coin comes up tails, she is awakened and interviewed on Monday, given a second dose of the sleeping drug, and awakened and interviewed again on Tuesday. The sleeping drug induces a mild amnesia, so that she cannot remember any previous awakenings during the course of the experiment (if any). During the experiment, she has no access to anything that would give a clue as to the day of the week. However, she knows all the details of the experiment.

Each interview consists of one question, "What is the probability that our coin landed heads?" How should she answer?

Puzzle 7/7/2007:
Consider a solid physical object small enough to fit in the palm of your hand, weighing 10 grams, made of hard plastic, and shaped like a pyramid. That is, it has a square base and its apex lies directly above the center of its base. Let h be its height, s the side length of its base, and r = h/s. Imagine the following experiment. We will place this object in a cup, shake it vigorously, and drop it from 1 meter above a flat, smooth oak table. Let p denote the proportion of times in a long sequence of repetitions of this experiment that the "die" lands on its base.

If r is very small, then the die is nearly flat, like a coin, and we might expect p to be very close to 0.5. If r is very large, then the die looks like a needle and we might expect p to be very close to 0. It is also natural to assume that p varies continuously with r. Hence, there is a value of r such that p = 0.2, in which case this 5-sided die is a fair die. Call this value of r the "fair ratio."

Is the fair ratio stable under perturbations of the experimental conditions? If we throw the die instead of drop it, or if we change the weight of the die, or if we change the material the die is made of, or if we change the hardness of the surface onto which it is thrown, will the fair ratio remain roughly the same? If the fair ratio is stable, then can it be derived without experimenting, by simply considering the geometry of the die?

By the way, asymmetrical "fair" dice apparently do exist in the real world. Here is a picture of one: http://www.byov.com/Images/gencon2004/5sideddie.jpg. Here are some technical details about it: http://www.patentstorm.us/patents/6926275.html. The shape of this one is not a pyramid as in this month's puzzle, but we can ask similar questions. Is it really fair under a wide array of experimental conditions? And can its dimensions be deduced through mathematical reasoning, rather than experiment?

Puzzle 6/3/2007:
Prove that for every integer x, there is an integer y such that (y^2-2)/(x^4+1) is an integer.

Puzzle 5/5/2007:
527 degrees Fahrenheit (F) coverts to 275 degrees Celsius (C). Notice that the string of digits 275 is formed from the string of digits 527 by moving the digit in the left-most position to the right-most position. 527 is the smallest positive integer whose Celsius counterpart is formed this way. What is the next smallest?

Puzzle 4/7/2007:
Is there a triangle all of whose vertices are points with rational coordinates on the circle x^2 + y^2 = 1 and whose interior angles are 45, 60, and 75 degrees?

Puzzle 3/3/2007:
A random variable X is said to be Poisson(L) if the probability that X = k is e^{-L}L^k/k! for all nonnegative integers k. Let X_1, X_2, ... be a sequence of independent Poisson(1)'s. Let Y_1, Y_2, ... be another sequence of independent Poisson(1)'s, independent from the first sequence. Let N be the smallest index such that X_N = Y_N. Prove that the expected value of X_N is

1/(1 + 1/(2 + 1/(3 + 1/(4 + ...

Puzzle 2/3/2007:
A prison contains 100 prisoners. In a special room are 100 boxes. Each box contains the name of one the prisoners. Tomorrow, each prisoner will be compelled to enter the room and select 50 boxes, hoping to find the box with his or her name in it. If every prisoner succeeds, they are all set free. If even one prisoner fails to find his name, they are all executed. The prisoners may not communicate tomorrow, but they may communicate today. That is, they may discuss and decide upon a selection strategy. Find a strategy which guarantees they will have at least a 30% chance of being freed.

Puzzle 1/6/2007:
You buy a brand new deck of playing cards. You remove them from the plastic and find that they are ordered as follows: ace through king of spades, followed by ace through king of hearts, then ace through king of diamonds, and finally ace through king of clubs. You play the following game with your friend. You give the deck a thorough shuffle. You win if, after your shuffle, every card is in a different position from where it started. What is the probability you win? Generalize this to a deck of n cards. What is the limit as n goes to infinity?

Now suppose that when you remove the cards from the plastic, you find that the deck is defective and all the cards are spades. Now what is the probability you win? (Note that it is now harder for you to win. For example, you lose if, after you shuffle, the top card is the ace of spades. But this time it could be any of the four aces in the deck.)

Puzzle 12/3/2006:
An unlucky gardener planted a 10x10 square array of 100 old seeds out in the garden. Only 5 of these seeds have germinated including one at the southwest corner (0,0) where a slug is currently reducing it to ground level. When it finishes it will head directly to the next closest doomed plant. After it eats that one it will again leave a slime trail to the closest remaining plant and so on until the garden is no more. Where are the 4 remaining seedlings if the path crawled by the slug is the longest possible and it never has to choose between two equidistant snacks?

Puzzle 11/5/2006:
You must choose either Jim or Bob to be on your bowling team. Bob is a better bowler, so you should choose him. But Jim is your friend, so you want to give him a chance. You decide to choose randomly. But you don't want to just flip a coin, since you want Bob to have the better chance of being chosen. You decide you want to choose Jim with probability 1/3. The problem is, you don't have any random mechanism other than a coin. In your infinite cleverness, you decide to do this: you will flip the coin twice. If both are heads, you pick Jim. If one is heads and one is tails, you choose Bob. If both are tails, you discard the results and flip again.

Part I: Show that, if you do this, you will indeed choose Jim with probability 1/3. Also show that the average number of flips it will take you to decide is 8/3.

Part II: The algorithm you just employed is only one of many possible ways to generate an event of probability 1/3 using a fair coin. This algorithm has an average running time of 8/3 flips. Find an optimal algorithm. That is, find an algorithm such that no other algorithm has a smaller average running time.

Part III: Same as Part II, but replace 1/3 with an arbitrary value p between 0 and 1.