Braess’ Paradox
Image: Wikimedia Commons

The diagram above represents a road network where T is the number of travelers. The leg from START to A takes T/100 = t minutes to traverse, as does the leg from B to END. The legs from START to B and from A to END each take a constant 45 minutes.

Now suppose that 4000 drivers want to travel from START to END. The northern and the southern routes are equally efficient, so the drivers will split into two groups, and each will arrive at END in 2000/100 + 45 = 65 minutes.

But now suppose that planners, hoping to improve matters, add a shortcut between A and B with a travel time of 0 minutes. Now all the drivers will take the route from START to A, since in the worst case it will take 4000/100 = 40 minutes, rather than the guaranteed 45 minutes taken by the leg from START to B. From A every driver will take the shortcut to B, for the same reason: Even in the worst case, the trip from B to END is 5 minutes faster than the trip from A to END.

As a result, every driver’s trip now takes 4000/100 + 4000/100 = 80 minutes, which is 15 minutes longer than in the original state of affairs. No individual driver has an incentive to change his behavior, since now the two original routes (northern and southern) each take 4000/100 + 45 = 85 minutes. If the 4000 drivers as a body could agree never to use the shortcut, they’d all be better off. But without a way to enforce this, all are stuck with longer commutes.

The principle was discovered by German mathematician Dietrich Braess in 1968. It’s known as Braess’ paradox.

Math Notes

The American Mathematical Monthly of January 1959 notes an “interesting Pythagorean triangle” discovered by Victor Thébault: If the two perpendicular sides of a right triangle measure 88209 and 90288, then the hypotenuse is 126225.

In other words, if you sum the squares of 88209 and its reverse, the result is a perfect square.

A Prime Number Generator

Take the first n prime numbers, 2, 3, 5, …, pn, and divide them into two groups in any way whatever. Find the product of the numbers in each group, and call these A and B. (If one of the groups is empty, assign it the product 1.) No matter how the numbers are grouped, A+B and \left |A-B  \right | will always turn out to be prime numbers, provided only that they’re less than p_{n+1}^{2} (and greater than 1, of course). For example, here’s what we get for (2, 3, 5) (where p_{n+1}^{2} = 72 = 49):

2 × 3 + 5 = 11
2 × 5 + 3 = 13
2 × 5 – 3 = 7
3 × 5 + 2 = 17
3 × 5 – 2 = 13
2 × 3 × 5 + 1 = 31
2 × 3 × 5 – 1 = 29

In More Mathematical Morsels (1991), Ross Honsberger writes, “For me, the fascination with this procedure seems to lie to a considerable extent in the amusement of watching it actually turn out prime numbers; I’m sure I only half believed it would work until I had seen it performed a few times.”

It makes sense if you think about it. Each of the first n prime numbers will divide either A or B but not the other, so it will fail to divide either A+B or \left |A-B  \right |. That means that any prime divisor of A+B or \left |A-B  \right | must be at least as big as p_{n+1}, and if there were more than one of them, the number would amount to at least p_{n+1}^{2}, putting it outside the limit. So for A+B or \left |A-B  \right | between 1 and p_{n+1}^{2}, it must itself be a prime number p such that pn+1p < p_{n+1}^{2}.


  • When written in all caps, the title of John Hiatt’s song “Have a Little Faith in Me” contains no curves.
  • Tycho Brahe kept a tame elk.
  • It isn’t known whether the sum of π and e is irrational.
  • Abraham Lincoln, Andrew Johnson, Ulysses Grant, and James Garfield died without wills.
  • “Selfishness is one of the qualities apt to inspire love.” — Nathaniel Hawthorne

The medieval Latin riddle In girum imus nocte et consumimur igni (“We enter the circle at night and are consumed by fire”) is a palindrome. The answer is “moths.”

The Revelation Game

brams revelation game

Is it rational to believe in the existence of a superior being? In 1982, New York University political scientist Steven J. Brams addressed the question using game theory. Assume that SB (the superior being) chooses whether to reveal himself, and P (a person) chooses whether to believe in SB’s existence. The two players have the following goals:

SB: Primary goal — wants P to believe in his existence. Secondary goal — prefers not to reveal himself.
P: Primary goal — wants belief (or nonbelief) in SB’s existence confirmed by evidence (or lack thereof). Secondary goal — prefers to believe in SB’s existence.

These goals determine the rankings of the four outcomes listed above. In each ordered pair, the first number refers to SB’s preference for that outcome (4 is high, 1 is low), and the second number refers to P’s preference. For example, SB prefers the two outcomes in which P believes in SB’s existence (because that’s his primary goal), and of these two outcomes, he prefers the one in which he doesn’t reveal himself (because that’s his secondary goal).

Brams finds a paradox here. If the game is one of complete information, then P knows that SB prefers not to reveal himself — that is, that SB prefers the second row to the first, regardless of P’s choice. And if SB will undoubtedly choose the second row, then P should choose his own preferred cell in that row, the second one. This makes (2, 3) the rational outcome of the game; it’s also the only outcome that neither player would choose unilaterally to depart once it’s chosen. And yet outcome (3, 4) would be preferred by both to (2, 3).

“Thus,” writes Brams, “not only is it rational for SB not to reveal himself and for P not to believe in his existence — a problem in itself for a theist if SB is God — but, more problematic for the rationalist, this outcome is unmistakably worse for both players than revelation by SB and belief by P, which would confirm P’s belief in SB’s existence.”

(Steven J. Brams, Superior Beings, 1983. This example is drawn largely from his paper “Belief in God: A Game-Theoretic Paradox,” in International Journal for Philosophy of Religion 13:3 [1982], 121-129.)

For the Record
Image: Wikimedia Commons

In December 2001, mathematician Bill Richardson received a call from a television producer asking for a formula that would reveal the total number of gifts given for any specified day in the song “The Twelve Days of Christmas.” He worked out that the total number of presents given on each day is a triangular number:

1 + 2
1 + 2 + 3
1 + 2 + 3 + 4

And so the cumulative total is the sum of triangular numbers:

1 + 3
1 + 3 + 6
1 + 3 + 6 + 10

So if Pn is the total number of presents given in the first n days, then

\displaystyle P_{n}=\sum_{i=1}^{n}\frac{1}{2}i(i + 1),

which works out to

\displaystyle \frac{n(n+1)(n+2)}{6},

“which is an elegant result,” Richardson writes. “So, the lucky girl received 1/6 × 12 × 13 × 14 = 364 presents in total. She should have had a very happy Christmas!”

(Bill Richardson, “The Twelve Days of Christmas,” Mathematical Gazette 86:507 [November 2002], 468.)

Image: Wikimedia Commons

Seeing the earth from a distance has changed my perception of the solar system as well. Ever since Copernicus’ theory (that the earth was a satellite of the sun, instead of vice versa) gained wide acceptance, men have considered it an irrefutable truth; yet I submit that we still cling emotionally to the pre-Copernican, or Ptolemaic, notion that the earth is the center of everything. The sun comes up at dawn and goes down at dusk, right? Or as the radio commercial describes sunset: ‘When the sun just goes away from the sky …’ Baloney. The sun doesn’t rise or fall: it doesn’t move, it just sits there, and we rotate in front of it. … Everyone knows that, but I really see it now. No longer do I drive down a highway and wish the blinding sun would set; instead I wish we could speed up our rotation a bit and wing around into the shadows more quickly. I do not have to force myself to call this image to mind; it is there, and occasionally, I use it for other things, although admittedly I have to stretch a bit. ‘What a pretty day’ makes me think that it’s always a pretty day somewhere; if not here, then we just happen to be standing in the wrong place. ‘My watch is fast’ translated into no, it’s not, it’s just that you should be standing farther to the east.

— Astronaut Michael Collins, Carrying the Fire, 1975

None for All
Image: Wikimedia Commons

If a lion hunts a herd of antelope, what rules govern the herd’s behavior? One intriguing possibility is known as selfish herd theory: Rather than acting to benefit the group as a whole, each member positions itself so that there’s at least one other animal between it and the predator. This produces a pattern known as a Voronoi tesselation — if each dot in the diagram above is an antelope, then the surrounding colored region is the area that’s closer to that antelope than to any of its neighbors. If a lion enters your cell, then you’re the antelope that’s going to get eaten.

This understanding helps to explain some herd behavior. Each animal wants to make its “domain of danger” as small as possible and to be as far as possible from the predator. Dominant animals tend to get prime positions near the center, subordinate animals get pushed to the fringes, and the whole formation evolves continuously as predator and prey move about.

Studies have shown that groups of fiddler crabs tend to take up Voronoi patterns fairly quickly when a predator first appears, and to huddle together when the danger increases as each tries to reduce its surrounding polygon. This actually leads some to move toward the predator as they try to reach the center and put others between the hunter and themselves. Those that violate the movement rules tend to get picked off, which reinforces the evolutionary strength of the strategy.

The Union-Closed Sets Conjecture

A family of sets is said to be union-closed if, given any two sets in the family, their union is as well. Here’s an example:

{}, {1,3}, {2}, {1,2,3}, {1,2,3,4}

Combine any two of those sets and you’ll get a member of the same family.

Now, provided our family is finite and consists of more than just the empty set, is there always an element that’s present in at least half of the sets? In the example above, the answer is yes: The element 2 appears in three of the five sets.

Will this always be the case? Strange to say, no one knows. Though the problem is almost absurdly simple to state, it has remained unsolved since Péter Frankl first posed it in 1979.

Henning Bruhn and Oliver Schaudt survey the state of the inquiry here. “The union-closed sets conjecture still has a bit of a journey ahead of it,” they conclude. “We hope it will be an exciting trip.”

(Thanks, Drake.)

Foregone Conclusions

Here’s the opening of Alice’s Adventures in Wonderland:

Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do; once or twice she had peeped into the book her sister was reading.

Choose any of the first 12 words and tap your way forward in the sentence from that point, tapping one word for each letter. So, for example, if you choose the word Alice, which has five letters, you’d tap was, beginning, to, get, and land on very. Then do the same thing with that word, advancing four letters to land on by. If you keep this up you’ll always arrive at the word sister.

That’s from Martin Gardner; the same trick works with “Twinkle, Twinkle, Little Star,” the opening of the Bible, and countless other texts.

It’s less surprising than it seems — it’s based on a principle called the Kruskal count, proffered originally by Rutgers physicist Martin Kruskal as a card trick. In each case various tributaries merge into a common stream that arrives at a predictable destination. Here’s an analysis (PDF).