Navy Rat Snail lottery

A peculiar lottery is played in an eastern country. Three tokens are randomly drawn (without replacement) from a bag of fourteen tokens. Each token has a unique mark, one of the national symbols of the region:

Navy
Milk
Ogee
Pot
Quill
Rat
Snail
Tuber
Uvala
Vole
Whelp
Xylem
Yarn
Zadar

Players enter the lottery by buying tickets and choosing three symbols for each ticket. A ticket wins if at least two of the three symbols guessed match the symbols on the tokens drawn from the bag.

What is the minimum number of tickets necessary to guarantee a prize?

Rencontre

In October of 1779, Euler prepared for the St. Petersburg Academy a paper on “a curious question from the doctrine of combinations.” So great was the backlog of Euler's writings that this was not published in the Academy's Memoirs until 1811, more than a qurter-century after his death. This delay notwithstanding, he provided an example not only of a “curious” problem but also a method of attack—[redacted]—that has become one of the primary weapons in the combinatorial arsenal.

The problem had been posed, and solved, decades earlier. In 1708, Pierre Remond de Montmort (1678-1719) discussed a card game called Treizeor, more descriptively, Rencontre (“coincidence”). The rules are these: a player shuffles a deck of 13 cards from ace to king, then deals them one at a time saying “one” with the first card dealt, “two” with the second, and so on. Victory is achieved if at some point the card overturned exactly matches the word spoken—for instance, if the fourth card turned over is a “four” or the eleventh card laid down is a “jack.” should such a coincidence occur, the dealer wins.

Montmort determined the probability of winning thereby earning for himself a place of honor in the history of combinatorics....

—William Dunham, Euler: The Master of Us All

Born on a Tuesday

Suppose I tell you that I have two children and one of them is a boy, what is the probability that I have two boys?

The correct answer is not 1/2 but 1/3. How can that be? Well there are four possible combinations, BB, GG, BG and GB but but at least one is a boy so you can get rid of GG. So all that's left is BB, BG and GB; and in only one of those three possibilities do I have two boys.

Now I tell you that I have two children and one of them is a boy born on a Tuesday. What is the probability that I have two boys?

Wise Men Don't Wear Hats

An emperor decides to give 100 of his philosophers a test. The philosophers will stand in line, one behind the other, so that the last person in the line sees everyone else. The emperor has 101 hats, each of a different color, and the philosophers know all the colors. The emperor puts all but one of the hats on the heads of the philosophers, one per philosopher. The philosophers can only see the colors of the hats on people in front of them. Then, in any order they want, each philosopher guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the philosophers cannot speak. They are not allowed to repeat a color that was already announced. Each person who guesses his color wrong will get his head chopped off. If a color is guessed a second time, all the philosophers will have their heads chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?

Bug march

A bug starts at the top-right corner of a square and marches counterclockwise around the perimeter of the square at a uniform speed. A spider starts at the bottom-right corner of the square and moves at the same speed as the bug, always in the direction of the bug. Where is the spider when the bug reaches the top-left corner? Does the spider catch the bug?

The penny drops

Stolen from a place. What is the shape of a coin that has probability 1/3 of landing (and standing) on its edge?

Naively, you accept

While walking through the park one day you encounter a man you
have never met before, who comes up to you and shows you a
folded up piece of paper.

"On this piece of paper I have written an integer from
0 to 119," he says. "If you give me $10, I will allow you to choose one of the
groups I am about to list; if the number I wrote is in the group you
pick, I will give you $30. If not, I will give you nothing.
Each group contains 60 of the 120 numbers from 0 to 119."

Naively, you accept. He lists the groups as follows:

1. The numbers from 0-59
2. The numbers from 60-119
3. Even numbers
4. Odd numbers
5. Numbers which have a remainder of 0 or 1 when divided by 4
6. Numbers which have a remainder of 2 or 3 when divided by 4
7. Numbers which have a remainder of 0, 1, or 2 when divided by 6
8. Numbers which have a remainder of 3, 4, or 5 when divided by 6
9. Numbers which have a remainder of 0, 1, 2, or 3 when divided by 8
10. Numbers which have a remainder of 4, 5, 6, or 7 when divided by 8
11. Numbers which have a remainder of 0, 1, 2, 3, or 4 when divided by 10
12. Numbers which have a remainder of 5, 6, 7, 8, or 9 when divided by 10

Which group do you choose?

More interestingly, what is your strategy for playing multiple iterations of this game?

Dyson's Double

Is there an integer such that, if you take its last digit and move it to the front, its value doubles?

Reportedly solved by Mr. Dyson in two seconds (spoiler).

Mathematical Constant Day

Celebrating "Pi Day" on March 14 seems pretty arbitrary, to say nothing of lame. When are you supposed to observe "e Day" or "Phi Day"? If you're going to pick a point during the year to recognize pi, why not the moment between January 1 and December 31 proportional to a circle's diameter's ratio to its circumference? This will fall on April 26 most years, and I suppose should be called "One Over Pi Day." (Alas, I see this has all been covered.)

On Pi Day, someone must observe that "The first 144 digits of pi add up to 666." What are the chances that a randomly generated series of consecutive digits will at some point add up to 666 (or any other large, evil number)?

The Hardest Logic Puzzle Ever

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.

Prime directive

Which bases, if any, is the number 10101 prime in? Prove your answer.

Integer bombing

A ship is sailing at a constant, integral speed along the number line. At time = 0 it is located at position 100, but you do not know its speed or direction. Starting at time = 1 second you can begin dropping one bomb every second at locations you specify in advance. Can you be guaranteed of hitting the ship?

Gift exchange

Bitkidoku proposes this holiday nut. Six friends want to exchange gifts. Each person will buy one gift. To determine who they will give their gift to, they each put their name in a hat and take turns drawing. If a person draws their own name, they put it back and draw again. If the last person draws their own name, they all start over from the beginning.

How many possible outcomes are there?

Four-way word set

The Puzzle Podcast introduced (in episodes 5 and 6) a puzzle called, unaccountably, "GO Mental." Four words are given; three of them follow an unstated rule and one does not. For example:

twin triplet king queen

Which one doesn't fit? The puzzles provide a few seconds of wonderment and a pleasant little flash of recognition.

It occured to me that a good challenge would be to come up with a quartet of words based on four rules, such that each word obeys three rules and violates one. After a year, I came up with this set:

charger colt dolphin mustang

Instead of stating the rules, the solver is encouraged to provide a word that satisfies all four rules. And then to come up with a new quartet in under a year.

Ball drop protocol

Someone told about this phone interview question.

If you drop a ball from a high enough floor of a 100-story building, it will break into pieces when it hits the ground. You have two balls to test with. How do you determine the lowest floor that is high enough to break a ball with the fewest number of drops?

Bent coin flip

You and a friend want to make a decision by coin toss, but all you have is a beat-up old ducat, which you fear is slightly biased. How do you make the fairest decision in a reasonable amount of time?

Bernoulli coin flip

Nicolaus [Bernoulli] proposes a game to be played between Peter and Paul, in which Peter tosses a coin and continues to toss it until it comes up heads. Peter will pay Paul one ducat if heads comes up on the first toss, two ducats if heads comes up on the second toss, four ducats on the third, and so on. With each additional throw the number of ducats Peter must pay Paul is doubled. How much shoud someone pay Paul -- who stands to rake in a sizable sum of money -- for the privilege of taking his place in this game?
--Against the Gods

Il problema dei punti

Una brigata gioca a palla a 60 el giuoco e 10 p caccia. E fano posta duc 10. Acade p certi acideti che non possano fornire, e l’una pte a 50 e l’altra 20. Se dimanda che tocca p parte de la posta.
--Luca Pacioli, Summa de arithmetica, geometria, proportioni et proportionalita, 1494

A group plays a ballgame to 60 and each goal is 10. They stake 10 ducats in all. It happens by certain accidents they are not able to finish; and one party has 50 and the other 20. What portion of the stake is due to each party?

Elliptical swimming pool

A recent Radiolab episode on Numbers had some interesting content, including an introduction to Benford's Law, unfortunately presented as something utterly mysterious and only comprehensible to mathematicians. I don't think it would be too terribly oversimplifying to explain it with dice. If you throw a normal die, the first digit of the results will tend to be evenly distributed among numbers from 1 to 6. A ten-sided or twelve-sided die will favor the initial digit 1. This effect will be even more pronounced with a 20-sided die, which will also show a bit of favoritism toward an initial 2.

There was also a short profile of Paul Erdös, with the first recording I've heard of his voice and that of his biographer, Paul Hoffman.

Somewhere in the story an elliptical swimming pool was mentioned. I thought it was going to be something similar to the elliptical billiard table, with waves instead of balls converging on a focus, but it turned out to be a clever problem. If the elliptical swimming pool has a uniformly wide border around the edge, is the outer edge of the border also an ellipse?

Obscure how-to

One way or another, people mostly get along. You walk into a restaurant and eat, with the understanding that you will pay. You work with the expectation of being compensated at the end of the week. Reputation, tradition, and contracts make most transactions run smoothly. In other cases, prepayments and security deposits reduce risk.

What about cases when these mechanisms are not reliable? A playground exchange has each party grip the object to be received, and both sides release the object to be given at the same time. But a bully with a good grip can cheat and end up with both toys. Is it possible to come up with strategies that allow adversarial parties to make reliable transactions without depending on third parties?

Fair Division
A well-known tactic solves the problem of dividing a cake evenly between two people. Alice cuts the cake such that she is satisfied with either slice. Bob then chooses which piece he wants. (1) Can three people divide a cake such that they are all satisfied? Can a solution be extended to more people?

Adversarial Trade
Two people who don't trust each other want to exchange some goods, and no escrow service is available. One solution: Alice leaves her item on one end of a long table. Bob leaves his item on the other end. Both parties proceed clockwise around the table to collect the other's item. (2) Is there a solution for three or more people?

Promise to Pay
At the end of a taxi ride, the fare asks the cabby to wait while he runs an errand. He tears a banknote down the middle and gives half to the cabby. It's now worthless to the fare, so the cabby is encouraged to wait. But the fare has nothing to lose by abandoning the taxi if he changes his mind. (3) Is there a better way to promise payment?

Remote Coin Flip
Heads-or-tails is a fair way to pick a winner between two people. But what if they are not in the same place? (4) If one party is only available by phone, can the flip be fair? What if they are not present at the time of the flip but will come later? More generally, (5) can you pick a winner among three or more people together using only fair coins or dice?

Who Makes More?
Two employees want to know who makes more, but don't want to reveal their salaries. Alice enters her salary on a calculator with the display covered. Bob then subtracts his salary, and divides the result by the absolute value of the result. The display is revealed, and a 1 indicates that Alice makes more; a -1 indicates that Bob makes more. (6) Can this be extended to three or more employees? They should all learn their rank, but no one (except those at the top and bottom) should have any knowledge of which employees rank above or below them.

Some of these questions can be approached with logic, and others require a more pragmatic approach. My high school science teacher, Mr. Hutchinson, solved the Promise to Pay problem by requiring a shoe to be held in escrow when he loaned out a pencil. Each item is more valuable to the owner than the borrower, making the eventual return more likely. Pawn shops operate somewhat differently on similar principles. For those looking for more pure logic, the Commitment scheme article is a good place to start.