Martin's Blog

Dijkstra on the pigeonhole principle

Posted by Martin Orr on Thursday, 04 October 2012 at 17:41

The computing scientist Edsger Dijkstra did not like the standard formulation of the pigeonhole principle:

If n compartments contain n+1 objects, then at least one compartment contains at least two objects.

He preferred:

For a non-empty, finite bag of numbers, the maximum value is at least the average value.

Of course there are times when Dijkstra's principle is preferable to the traditional statement above (and to its generalisation which I will state below) but I think that there are also times when the traditional statement is preferable, and I am going to counter some of Dijkstra's arguments below. These come from EWD980 and EWD1094.

I am thinking about this today because I am going to teach the pigeonhole principle to some sixth formers at the Maths Olympiad Club at Orsay on Saturday, and I have already taught it twice at the National Mathematics Summer School in Birmingham.

3 comments Tags maths, nmss, teaching