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.

Operationality

Dijkstra attacks the traditional statement as "very operational", because it refers to a process where only the final state matters. This objection does not apply to my statement of the principle, but Dijkstra was referring to the following version which he quoted from Honsberger:

If more than n objects are distributed into a set of n compartments, some compartment must receive more than one of the objects.

As Dijkstra points out, the pigeonhole principle is applicable in situations where no process of distribution and reception takes place. He also suggests that thinking about the process may lead us to worry about irrelevant things like: does the order in which we distribute the objects matter?

I find Honsberger's choice of verbs "distributed" and even more "receive" to be strange (perhaps it is an Americanism?) but they are not essential. I would often state the pigeonhole principle operationally as

If n+1 objects are put into n compartments, then at least one compartment contains at least two objects.

As I demonstated at the beginning of the post, one can remove the operational phrasing without fundamentally altering the statement of the pigeonhole principle. But I also think that Dijkstra takes the operationality of the phrasing too literally. Mathematicians often use irrelevantly operational verbs, especially "choose". In learning to read mathematics, one learns that the action can be ignored and only the result matters. (On the other hand when writing mathematics formally, one perhaps learns to eliminate such verbs. Certainly I make a conscious effort to do so when stating a theorem. I do not have time now to look into how operational verbs are used in published mathematical writing.)

I suspect that Dijkstra's objection to operationality came from a certain controversy in computing science (a term he preferred to computer science).

Naming objects and compartments

Dijkstra dislikes the mention of "objects" and "compartments" in the traditional statement because we are forced to explicitly identify the objects and compartments in each application. On the other hand, in Dijkstra's version, we are forced to identify the numbers that we are going to average. Sometimes this is easier, but often this means first identifying objects and compartments, then naming the number of objects in each compartment.

When I teach the pigeonhole principle, I emphasise identifying objects and compartments, especially compartments. The proof of the pigeonhole principle is so short that you do not shorten proofs by invoking it as a theorem. Rather its value is in making explicit the idea of objects and compartments, giving you the idea to try to identify them in potential applications.

Dijkstra also says something about how the metaphor of objects and compartments may not fit nicely. I do not really understand this point: it seems generic to me but perhaps I am corrupted by years of practice. The words "pigeons" and "holes" do not work very well with students, but I have not yet tried "objects" and "compartments". Would Dijkstra be happier if I replaced the word "compartment" by "class" or "category"?

Generalisations

Dijkstra points out that his principle is more general than the traditional statement of the pigeonhole principle. This is true with regard to the statement I gave at the beginning, but whenever I teach that statement or see it taught it is always accompanied by:

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

This deals at once with many of Dijkstra's examples which he says cannot be dealt with by the traditional statement.

Dijkstra does have a valid point that the traditional statement does not cope very well with cases where an object can be in multiple compartments. Inserting a comment into the principle "objects may be in more than one compartment" badly stretches the metaphor. We can alter our objects and compartments so that each object only belongs to one compartment, but the methods of doing so are difficult for students at the level of learning the pigeonhole principle -- either make a choice of one compartment for each object or replace objects by pairs (\text{obj}, \text{comp}) such that \text{obj} \in \text{comp}.

PS: A remark on pigeons

Dijkstra does not mention this at all, but I have found that talking about "pigeons" in the pigeonhole principle is unhelpful. "What are the pigeons and what are the holes?" is a nice-sounding slogan but students find this metaphor unnatural.

Furthermore it is historically incorrect: the name "pigeonhole principle" originally referred to pigeonholes in a desk rather than in a dovecote. In French it is called the "principe des tiroirs", in German the "Schubfach prinzip", both meaning the "drawer principle". In English it is sometimes called the "box principle".

Tags maths, nmss, teaching

Trackbacks

No trackbacks.

Comments

  1. Barinder said on Sunday, 28 October 2012 at 15:19 :

    "Mathematicians often use irrelevantly operational verbs, especially “choose”."

    Recently I've been supervising first year analysis, where it is important that students get to grips with rigor. I've often stressed, when proving that a given sequence converges to 0 say, that it is important to "fix" an arbitrary positive epsilon, or to consider being "given" one such. Then do what you have to do, and at the end observe that this argument works for any such positive epsilon. It's then like a game...you try to "beat" me by choosing a really really small epsilon, but, if the sequence converges to 0, then I'll always be able to guarantee that, eventually, the terms will be within epsilon of 0, and so I "win". You would "win" if the sequence did not tend to 0.

Post a comment

Markdown syntax with embedded LaTeX.
Type LaTeX between dollar signs, and enclose them between backticks to protect it from Markdown.
All comments are subject to moderation before they appear on the blog.

Archives