29 July 2009

Fields of onions

The Onion, commenting on Sarah Palin's resignation as governor of Alaska, writes that "Nothing can distract her laser focus from the ultimate prize: the Fields Medal.”

But Palin is 45, and the age limit for the Fields is 40. Perhaps she should aim for the Abel Prize instead?

(Note to the humor-impaired: this is not meant to disparage the Abel Prize.)

27 July 2009

Plats diviseurs, or how the French cut cakes

Apparently in France they have an interesting solution to cake-cutting problems -- a plate with markings on the rim for the proper place to cut into 3, 5, 6, 7, or 9 slices, called the plat diviseur. See also here. You can buy them here; the site is in French. Some especially ornate examples are due to Paul Urfer, who appears to be the original inventor.

I found out about these from The Number Warrior, Jason Dyer. Unfortunately I have no use for one of these, because I live alone, in a small apartment where I couldn't reasonably have enough people over to need a whole cake, and so I do not buy a whole cake at once.

I suspect I have some French readers. Have you seen these before?

24 July 2009

A meta-proof

A meta-proof of P=/!=NP, from the Geomblog in 2004. (That's "equals or does not equal".)

Note that you don't need to know anything about the P vs. NP problem to find it funny.

(via Michael Trick.)

21 July 2009

A number-theoretic coincidence

An interesting little tidbit from Tanya Khovanova: consider the Pythagorean triple 32 + 42 = 52, in which all three numbers are consecutive, and another similar coincidental-seeming equation 102 + 112 + 122 = 132 + 142. These are the first two elements of a sequence of similar equations, with k+1 squares on the left-hand side and k squares on the right-hand side, which she presents there.

Still perhaps coincidental is the fact that 32 + 42 = 52 and 33 + 43 + 53 = 63. Of course once you see these it's tempting to check if 34 + 44 + 54 + 64 = 74. (It doesn't.) In fact, for n ≥ 4,

3n + 4n + ... + (n+2)n < (n+3)n

and here's a proof. I'll prove it for n ≥ 5. It suffices to show that

(3/(n+3))n + (4/(n+3))n + ... + ((n+2)/(n+3))n < 1.

Call the left-hand side f(n). But the last term on the right-hand side is decreasing in n, and for n ≥ 5, is at most 16807/32768 (its value at 5). Now, we can write the left-hand side of the above inequality as

((n+2)/(n+3))n (1 + ((n+1)/(n+2))n + (n/(n+2))n + ... + (3/(n+2))n)

and each term in the second factor is at most ((n+1)/(n+2))n times the previous one. So we have

(1 + ((n+1)/(n+2))n + (n/(n+2))n + ... + (3/(n+2))n) > (1 + r + r2 + r3 + ...)

where r = ((n+1)/(n+2))n. Of course the right-hand side of the previous inequality is 1/(1-r). r is positive and decreasing in n, so 1/(1-r) is as well. Since n ≥ 5, 1/(1-r) is bounded above by its value at 5, which is 16807/9031. Thus for n ≥ 5,

f(n) < (16807/32768)(16807/9031)

and the right-hand side is easily checked to be less than 1.

For n = 4 this proof doesn't work, because I threw away a bit too much in bounding the sum of a finite series by the sum of an infinite one, but it's easy to check.

In fact, f(n) approaches 1/(e-1) as n goes to infinity.

Edit (8:41 pm):: See also The Everything Seminar.

16 July 2009

"Roommates" is a euphemism?

I'm at the Cornell Probability Summer School. (This announcement is too late for anybody who wants to find me here, as it's almost over! But I have been tracked down by at least one fan.)

In a lecture here this morning, Ander Holroyd spoke about the stable marriage problem and variations of it involving point processes (see this paper of Holroyd, Pemantle, Peres, and Schramm, which I've mentioned before, for details). The goal of the problem is to pair up n men and n women in such a way that no two people who aren't married to each other prefer each other to their current partners; this is called a "stable matching" and one always exists.

The original paper on the stable marriage problem is that of Gale and Shapley, in 1962. This paper also talks about the "stable roommates" problem, which is the analogous problem where everybody is of the same gender. Rather surprisingly, I never realized that "roommates" might be a euphemism here, which is something that Holroyd pointed out this morning to quite a bit of laughter.

15 July 2009

Batting under .200

Stat of the day (from baseball-reference.com) has a list of players who went an entire season, had enough at bats to qualify for the batting title (I forget the statistics for this, but this basically means they have to play regularly), and are batting under .200.

Most of them are from a long time ago. Why? Because .200 is well below average and always has been (which is why the list was worth compiling) and the variance in batting averages has gone down as the standard of play has improved. Stephen Jay Gould wrote about this in Full House: The Spread of Excellence from Plato to Darwin; the argument is roughly that as baseball scouting and training has gotten better, there are not as many bad pitchers in the major leagues as there were in the past, so players can't inflate their batting average that way. (I'm in Ithaca and my copy of the book is in Philadelphia, so I can't check if I'm stating this correctly.)

11 July 2009

A puzzle

229, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 229. (Thanks to Kate for this one; a solution is there, so don't look until you've thought about it.)

05 July 2009

Problems that are hard for intermediate values of some parameter

In Clifford Henry Taubes' review of Monopoles and three-manifolds, by Peter Kronheimer and Tomasz Mrowka (citation information; article), near the end of the first paragraph the authors mention the problem of classifying compact manifolds with the homotopy type of the n-sphere. In any dimension there is exactly one. The history of this problem is roughly as follows:

  • n ≥ 5: Smale, 1960 (and Stallings at around the same time)

  • n = 4: Freedman, 1980

  • n = 3: Perelman, early 2000s (this is the Poincare conjecture)

  • n = 2: "follows from the Riemann mapping theorem"

  • n = 1: "a nice exercise for an undergraduate"

So in low dimensions the problem is easy, or at least doesn't require "modern" apparatus; in high dimensions it's harder (Smale and Freedman both got Fields Medals); in "middle" dimensions (like 3) it's the hardest, or at least took the longest. It's my understanding that it's pretty typical in geometry/topology for the three- or four-dimensional cases of a problem to be the most difficult?

Can you think of other problems (from any area of mathematics) that have a similar property -- that they're hardest for some medium-sized value of whatever a natural parameter for the problem is? (Yes, it's a vague question.)