Science & Math

Kirkman Schoolgirls Problem

“Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast.”

The Rev. Thomas Penyngton Kirkman posed this query innocently in The Lady’s and Gentleman’s Diary in 1850. It’s trickier than it looks — though seven solutions are possible, they’re difficult to discover by trial and error. Here’s one:

kirkman schoolgirl solution

Each letter appears once in each row, but no two letters share a cell more than once. The problem’s simplicity made it popular among Victorian amateur mathematicians, and Kirkman later complained that it had eclipsed his more serious work — though he took pains to dispute James Joseph Sylvester’s claim to have invented the problem himself.

Do such problems generally have solutions? Surprisingly, the answer remained unknown until just last January, when Oxford mathematician Peter Keevash showed that the answer is yes if certain basic requirements are met. Keevash’s result was “a bit of an earthquake as far as design theory is concerned,” said Cambridge mathematician Timothy Gowers.

Now that the schoolgirl problem is under control, a related challenge has taken its place. If 20 golfers want to arrange themselves into different foursomes on five successive days, is it possible to plan the groups so that each golfer plays no more than once with any other golfer? Formally the “social golfer problem” remains unsolved — though tournament organizers work out individual solutions every day.

(Thanks, Martha.)

Made to Order

Divide the number 999,999,999,999,999,999,999,998,999,999,999,999,999,999,999,999 into 1 and express the result as a decimal expansion, and you’ll find the Fibonacci sequence presented in tidy 24-digit strings:

fibonacci expansion

(Thanks, David.)

Color Scheme

Amateur magician Oscar Weigle invented this surprising effect in 1949. Assemble a deck of 20 playing cards, 10 red and 10 black, in strictly alternating colors. Hold this deck under a table. Now turn over the top two cards as one, place them on top, and cut the deck. Repeat this procedure as many times as you like — turn two, cut, turn two, cut. When you’ve finished, the deck will contain an unknown number of reversed cards, distributed randomly.

Now, still holding the deck under the table, shift the top card to the bottom, then turn over the next card and place it on the table. Do this repeatedly — shift a card to the bottom, then reverse the next card and put it on the table — continuing until you’ve put 10 cards on the table. Surprisingly, these cards are sorted by color — the face-up cards are of one color, and the face-down ones are of the other.

You’re still holding 10 cards under the table. Divide these into two stacks and weave them together under the table randomly. Do this as many times as you like — divide the 10 cards into two groups and merge them together however you like, so long as no card is turned upside down. Turn over the packet and shuffle it in the same way a few more times. Give it a final cut if you like.

Now deal these cards out as before: Shift the top card to the bottom, reverse the next card and put it on the table. Like the first group, this one will sort itself by color, with one color face up and the other face down.

Surprise Appearance

Suppose we put eight white and two black balls into a bag and then draw forth the balls one at a time. If we repeat this experiment many times, which draw is most likely to produce the first black ball?

Most people answer 4, but in fact the first black ball is most likely to appear on the very first draw:

surprise appearance table

By symmetry, the second black ball is most likely to appear on the final draw.

(A.E. Lawrence, “Playing With Probability,” Mathematical Gazette, vol. 53 [December 1969], 347-354.)

The Friendship Theorem

If every pair of people in a group have exactly one friend in common, then there’s always one person who is a friend to everyone.

This rather heartwarming fact was proven by Paul Erdös, Alfréd Rényi, and Vera T. Sós in 1966. It’s sometimes more cynically known as the paradox of the politician.

The Erdös proof uses combinatorics and linear algebra, but in 1972 Judith Longyear published a proof using elementary graph theory.

See The Elevator Problem.


“The origin of science is in the desire to know causes; and the origin of all false science and imposture is in the desire to accept false causes rather than none; or, which is the same thing, in the unwillingness to acknowledge our own ignorance.” — William Hazlitt

Three Coins

Three coins are lying on a table: a quarter, a half dollar, and a silver dollar. You claim one coin, I’ll claim the other two, and then we’ll toss all three. A coin that lands tails counts zero, and a coin that lands heads wins its value (in cents, 25, 50, or 100) for its owner. Whichever of us has the larger score wins all three coins. If all three coins land tails then we toss again.

Which coin should you claim to make the game fair — that is, so that each of us has an expected win of zero?

Click for Answer

The Asymmetric Propeller

asymmetric propeller theorem

Arrange three congruent equilateral triangles so that their corners meet at a point, like the red triangles above. The arrangement doesn’t have to be symmetric; the triangles can even overlap. Now draw lines BC, DE, and FA to complete a hexagon inscribed in a circle. The midpoints of these three lines will form the vertices of an equilateral triangle.

That’s called the asymmetric propeller theorem, and it’s been known since the 1930s. But in 1979 Beverly Hills dentist and geometry enthusiast Leon Bankoff told Martin Gardner of some further discoveries. Bankoff never found time to write them up, so after the dentist’s death in 1997 Gardner published them in the College Mathematics Journal:

  • The three equilateral triangles need not be congruent. Each can be of any size and the theorem still holds.
  • The triangles need not meet at a point. They can meet at the corners of any equilateral triangle.
  • They need not even be equilateral! If three similar triangles of any sizes meet at a point, the midpoints of the three added lines will form a triangle similar to each of the “propellers.”
  • The similar triangles need not meet at a point! If they meet at the corners of a fourth triangle (of any size) that’s similar to each propeller, then the midpoints of the added lines will form a triangle similar to each propeller, provided that the vertices of the central triangle touch the corresponding corners of the propellers.

Given all this flexibility, Gardner asked, do the propellers even have to be triangles? It turns out that the answer is yes. Still, the discoveries above form a fitting tribute to Bankoff, whom Gardner called “one of the most remarkable mathematicians I have been privileged to know.”

(Martin Gardner, “The Asymmetric Propeller,” College Mathematics Journal 30:1 [January 1999], 18-22.)

The Uncounted,_Rainbow.JPG

It was a good answer that was made by one who when they showed him hanging in a temple a picture of those who had paid their vows as having escaped shipwreck, and would have him say whether he did not now acknowledge the power of the gods, — ‘Aye,’ asked he again, ‘but where are they painted that were drowned after their vows?’ And such is the way of all superstition, whether in astrology, dreams, omens, divine judgments, or the like; wherein men, having a delight in such vanities, mark the events where they are fulfilled, but where they fail, though this happens much oftener, neglect and pass them by.

— Francis Bacon, Novum Organum, 1620

Parrondo’s Paradox

Imagine a staircase with 1001 stairs, numbered -500 to 500. You’re standing in the middle, on stair 0, and you want to reach the top. On each step you can play either of two coin-flipping games — if the result is heads then you move up a step; if it’s tails then you move down a step:

  • In game 1 you flip coin A, which is slightly biased: It comes up heads 49.5 percent of the time and tails 50.5 percent.
  • In game 2 you use two coins, B and C. Coin B produces heads 9.5 percent of the time and tails 90.5 percent. Coin C produces heads 74.5 percent of the time and tails 25.5 percent. In game 2 if the number of the stair you’re on is a multiple of 3 then you flip coin B; otherwise you flip coin C.

Both of these are losing games — if you played either game 1 or game 2 exclusively, you’d eventually find yourself at the bottom of the staircase. But in 1996 Spanish physicist Juan Parrondo found that if you play the two games in succession in random order, keeping your place on the staircase as you switch between them, you’ll rise to the top of the staircase. It’s not, properly speaking, a paradox, but it’s certainly counterintuitive.

This example is from David Darling’s Universal Book of Mathematics. (Thanks, Nick.)