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.

Change of pace

Here's a cleverish cryptic crossword clue. It's easy to see what the answer must be, but it took me a little while to figure out how it fit the clue, which is the challenge. The enumeration was withheld in the original, but no reason not to include it here:

Orbital path may be derived from astronomical event taking half-second? (7)

.

Three contestant Monty Hall problem

The simplest children in the streets have long known that one should switch doors when faced with the Monty Hall problem. A variant is proposed as follows:

Monty Hall presents three doors to Xavier, you, and Zebediah. Two doors conceal a goat, and one door conceals a car (assume that all contestants prefer a car to a goat). Each contestant chooses a door and communicates this choice to Monty without revealing this choice to the other contestants; if more than one contestant chooses the same door, all contestants choosing that door are awarded an instance of the prize behind it.

After each contestant has chosen a door, Monty reveals that each door has been chosen by exactly one person. He then opens the door chosen by Xavier, and there is a goat behind it. Monty offers you and Zebediah the choice to keep your respective doors or switch (again, if you both wind up with the same door you each get an instance of the prize behind it).

Should you stick or switch? Should Zebediah stick or switch?

The monkey's wheel

Someone with a British accent constructed this device:

It's a small car with two spools for wheels. A toy wheel rests on top of the spools. Pushing the car to the right causes the spools to rotate clockwise and the big wheel to rotate "anticlockwise," as expected. He then proposes to lightly set the edge of a ruler on top of the big wheel and use it to push the top of the wheel to the right. What will the car do?

One stuffed animal says the big wheel will be turned clockwise, turning the spools anticlockwise, causing the car to move to the left. Another stuffed animal says the ruler will push the car to the right, but the wheels will push it to the left, and it just won't go. A third stuffed animal says it will go to the right, but can't say why. What do you say?

A simple programming question

Suppose you have an array of 99 numbers representing the integers from 1 to 100, unordered, with one missing. What's the most efficient way to find and return the missing number?

Stochasticity

As part of a recent Radiolab episode on randomness, the hosts visit Statistics Professor Deborah Nolan at the University of California, Berkeley. She has the class do an exercise: while she is out of the room, two groups each generate a list of one hundred coin flips. One group flips a penny and records the results as a series of H's and T's, the other group imagines they are flipping a coin and writes what they suppose the results would be.

The two lists are then written on the chalkboard. The professor returns, takes a look at the two lists, and promptly identifies which list is the result of actual coin flips and which one was faked.

How did she do it?

Combinatorics for fun and profit

Score in my office:

This problem - 3
Hackers - 0

Suppose Steve and Rasalom are evenly matched at playing Azad. That is, any time Steve and Rasalom play Azad, each has a 50% chance of winning (there are no draws). Which scenario is more likely: a) Steve and Rasalom play 4 times and Steve wins exactly 3, or b) Steve and Rasalom play 8 times and Steve wins exactly 5.

Justify your answer; right guesses will be ignored, wrong guesses will be mocked.

Doctored Photo #9

Find the original version of this modified photo and win ten points.

Constrained excerpt

Anu Garg offers this passage as an example of writing with a constraint. I didn't read the rest of the article to find out what the constraint is, but these kind of things are typically based on tricks like leaving out a common letter, acrostics, or palindromic constructions.

None of the stations played anything good, but I kept at the buttons, pushing off songs from a childhood we were all supposed to have had. Commercials bothered me more than ever, news was propaganda, and traffic reports were no more useful than the weather. It wasn’t yet 1988, and I was driving home from Tacoma.

The passage contains no j, q, x, or z, but these hardly qualify as common. There's no obvious pattern in word lengths, which include everything from 1 to 11. It doesn't seem like Uncleftish Beholding, either. Any ideas?

Tank production

A story is told from World War II, when the Allies were considering a ground invasion of Europe. Critical to their success would be the number of Mark V tanks fielded by the Germans. Intelligence, however, gave contradictory estimates as to the number of tanks that were being produced per month.

It was noticed that captured tanks had serial numbers, which were apparently assigned in order of production. Statisticians came up with a formula which would give an estimate of the total number of tanks produced given a sample of serial numbers. After the war, German production records showed that the estimate was almost exactly correct.

Suppose tanks are numbered 1, 2, 3, 4, 5, ... N, where N is the total number of tanks produced. Given a sample of, say, five serial numbers, how would you estimate the value of N?

Right triangles

Prove that a triangle with sides that can be written in the form of n² + 1, n² - 1 and 2n (where n > 1) is right-angled.

Show, by means of a counterexample, that the converse is false.

[from The Curious Incident of the Dog in the Night-time]

Crossing cylinders

Imagine two cylinders of diameter one with axes intersecting at right angles.

• What is the volume of the space belonging to both cylinders?

• Describe the curve along the intersection you would get by "unrolling" one cylinder like a piece of paper.

(The shape of the intersection is called a "Steinmetz Solid," and Wolfram has spoilers about it.)