Monthly Archives: October 2008




Here are two additional sectionettes from my “Notices of the AMS” book review entitled “Economic and Common Sense” on Steven Landsburg’s book “More Sex is Safe Sex – the unconventional wisdom of economics”.  Both sectionettes deal with Government intervention in economics. The first is about fertilizer subsidies in Malawi. This was a move made by Malawi’s government against the advice of the world bank and against standard market economic teachings. Judging from the outcomes of the last couple of years it was a successful move. The second is an anecdote about administrative measures the US government took against inflation in the early 1970s, as told by Bob Aumann. I do not know if these measures were successful.

Current events, the financial crisis and the attempted bailout make the topics of these little sectionettes of some relevance. (And so is the issue of “what do firms want” and the larger issue of “economics and common sense”.) I do not think that the dramatic and sad current financial crisis by itself is definite evidence to support more liberal forms of market economy (which I tend to favour) rather than more conservative versions. (Or the other way around.) In other words, I tend to think that a crisis of this nature can occur (and perhaps cannot even be avoided) under both economic systems. The issue of governmental intervention is also far from being clear.  The case for subsidies for fertilizers in a hunger-stricken country seems much clearer than (humongous) subsidies for financial institutions; both in terms of effectiveness and in terms of basic values of fairness and human dignity.   Continue reading

Two Math Riddles

Usually I am not particularly good at telling math riddles or solving them, and I was not planning on presenting math riddles here. But these days, when mathematical blogs break new ground and enter uncharted territories, let me make an exception and tell you two riddles.

1) (Told to me by Sergiu Hart; taken from a MSRI news-teller to the best of my memory.)

You have a 1 meter long (one ant thin) wooden stick and you put on it n ants in arbitrary locations. Each ant is facing one end of the stick. The ants move 1 meter per minute and when two ants meet they both start moving in the opposite directions. If an ant reaches an end of the stick it falls from it.

After how much time you can be sure that no ants will remain on the stick?

2) (Told to me (with the solution) most recently by Sasha Barvinok, who heard the problem on “Car talk“.)

An airplane has 100 seats, and 100 passengers were assigned seats. The first passenger, ‘Joe,’ enters the plane and rather than sitting in his assigned place, he sits in a random place. The next passengers come one by one and every passenger sits in his assigned seat if it is empty, and in a random empty seat if his seat is already taken. What is the probability that the last passenger ‘Jim’ will sit in his assigned seat?

If you want to solve these riddles on your own do not read the rest of this entry. Continue reading

About Mathematics

This post collects some brief philosophical thoughts about mathematics that appeared as part of my paper “Combinatorics with a geometric flavor: some examples,” from the proceedings of the conference “Vision in Mathematics, towards 2000.” I added two small items (the first and fifth).  

1. Mathematical truths – theorems.

“There are infinitely many primes;” “The three angles of a triangle add up to 180 degrees;”  “A continuous real function defined in a closed interval attains there its maximum;” “A non-constant polynomial over the complex numbers has a solution;” If you substitute a matrix A in its characteristic polynomial you get zero;” “A simply connected closed 3-dimensional manifold is homeomorphic to a sphere.”   

These truths appear very different from truths in other areas of life. This sharp difference is the secret to some of the successes of mathematics and explains also its limitation.

What makes a mathematical theorem important, deep, or central? 



2. Proofs, more proofs, “proofs from the book” and computer proofs

Science has a dual role: exploring and explaining. In mathematics, unlike other sciences, mathematical proofs are used as the basic tool for both tasks: to explore mathematical facts and to explain them.

The meaning of a mathematical proof is quite stable. It seems unharmed by the “foundation crisis” and the incompleteness results in the beginning of the 20th century, and unaffected by the recent notions of randomized and interactive proofs in theoretical computer science. Still, long and complicated proofs,
as well as computerized proofs, raise questions about the nature of mathematical explanations.

Proofs are gradually becoming intolerably difficult. This may suggest that soon our days of successfully tackling a large percentage of the problems we pose are over. Also, this may reflect the small incentives to simplify.

Be that as it may, we cannot be satisfied without repeatedly finding new connections and new proofs, and we should not give up hope to find simple and illuminating proofs that can be presented in the classroom. Continue reading

Extremal Combinatorics IV: Shifting




We describe now a nice proof technique called “shifting” or “compression” and mention a few more problems.


The Sauer-Shelah Lemma:

Let N=\{1,2,\dots,n\}. Recall that a family {\cal F} \subset 2^N shatters a set S \subset N if for every R \subset S there is T \in {\cal F}  such that S \cap T=R.

Theorem (Sauer-Shelah): If |{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k} then there exists a set S, |S|=k+1, such that \cal F shatters S.

Proof by Shifting

I will describe now a proof of the Sauer-Shelah theorem which is not the easiest but still is quite easy and demonstrates an important technique called “shifting” or “compression” (for an application to additive number theory look at this post by Terry Tao).

The idea of shifting is to reduce an extremal problem for a family of sets \cal F to the case of families of a special type. In the case of the Sauer-Shelah Theorem we first make a reduction to families which are closed under taking subsets (such families are called “ideals,” “down-sets,” and “simplicial complexes”).  Then we prove the theorem for such families. Continue reading