This is an update of several posts I wrote as late as 2009, and some additional information acquired since then.
Sometimes problems that seem very hard, can be very easy if they are viewed in the right way, and one of those easy ways to make some hard problems manageable is the Pigeon-Hole Principle. Over the last few weeks seems like lots of problems invovling this idea have shown up, so I thought I would bring it to you.
The basic idea is so easy any sixth grader would agree; if you have two boxes, and you are going to put three balls in the boxes, then at least one box will get more than one ball..... "well, Duh!" they answer... and yet... it seems easier to apply than it might be. Now that you know the secret, try these two problems. I'll post the answer down lower on the page where you must not look until you take a few minutes to ponder the problems.
Here is the first from a recent blog I read: "39 people are attending a large, formal dinner, which must of course occur at a single, circular table. The guests, after milling about for a while, sit down to eat. It is then pointed out to them that there are name cards labeling assigned seats, and not a single one has sat in the seat assigned to them. Prove that there is some way to rotate the table so that at least two people are in the correct seats."
This one seems tougher, but really isn't, it just requires a different way of thinking. "Suppose you pick six unique integers from 1 to 1000. Prove that at least two of them must have a difference that is a multiple of five.
I'll give you the proofs of each of these, and then get to the main topic of the history of this important theorem in discrete mathematics
Ok, The Proofs... for number one... Suppose you handed each person a number that was how many seats they needed to move to the right to find their assigned seat. Since no one is at the right seat, the number can not be zero or thirty-nine. SO each of the people has a number between 1 and 38...wait, there are 39 people...two of them (at least) must be the same distance away from their assigned seats.... admit it…..that’s pretty cool.
For number two it is sort of the same idea, but you have to think about how much each number would have for a remainder if you divided them by five. The only possible choices are 0, 1, 2, 3, or 4... but there are six numbers, so two of them have the same remainder...and two numbers that have the same remainder on division by five, are a multiple of five apart.... think of 1,6, 11, etc for remainders of one. If you want to read more about how remainders can play a part in solving problems, see my blog on "casting out sevens"
The basic idea behind this mathematical principle is what students would call common sense; if there are n objects to be placed in m receptacles (with m less than n), at least two of the items must go into the same container. While the idea is common sense, in the hands of a capable mathematician it can be made to do uncommon things. Here is a link to an article by Alexander Bogomolny in which he uses the principle to argue that there must be at least two persons in New York City with the same number of hairs on their head. This "counting hairs" approach dates back to the earliest version of the principal I have ever seen.
The same axiom is often named in honor of Dirichlet who used it in solving Pell's equation. The pigeon seems to be a recent addition, as Jeff Miller's web site on the first use of some math words gives, "Pigeon-hole principle occurs in English in Paul Erdös and R. Rado, A partition calculus in set theory, Bull. Am. Math. Soc. 62 (Sept. 1956)" (although they credit Dedekind for the principle). In a recent discussion on a history group Julio Cabillon added that there are a variety of names in different countries for the idea. His list included "le principe des tiroirs de Dirichlet", French for the principle of the drawers of Dirichlet, and the Portugese "principio da casa dos pombos" for the house of pigeons principle and "das gavetas de Dirichlet" for the drawers of Dirichlet. It also is sometimes simply called Dirichlet's principle and most simply of all, the box principle. Jozef Przytycki wrote me to add, "In Polish we use also:"the principle of the drawers of Dirichlet"
that is 'Zasada szufladkowa Dirichleta' ". I received a note that said, "Dirichlet first wrote about it in Recherches sur les formes quadratiques à coefficients et à indéterminées complexes (J. reine u. angew. Math. (24 (1842) 291 371) = Math. Werke, (1889 1897), which was reprinted by Chelsea, 1969, vol. I, pp. 533-618. On pp. 579-580, he uses the principle."
He doesn't give it a name. In later works he called it the "Schubfach Prinzip" [which I am told means "drawer principle" in German]
The idea has been around much longer than Dirichlet, however, as I found out in June of 2009 when Dave Renfro sent me word that the idea pops up in the unexpected (at least by me) work, "Portraits of the seventeenth century, historic and literary", by Charles Augustin Sainte-Beuve. During his description of Mme. de Longuevillle, who was Ann-Genevieve De Bourbon, and lived from 1619 to 1679 he tells the following story:
-------------------------
He published Port-Royal Grammar in 1660 which was strongly influenced by Descartes' Regulae. In Port-Royal Grammar Arnauld argued that mental processes and grammar are virtually the same thing. Since mental processes are carried out by all human beings, he argued for a universal grammar. Modern linguistic theorists consider this work as the beginnings of the modern approach their subject. Arnauld's next work was Port-Royal Logic which was another book of major importance. It was also strongly influenced by Descartes' Regulae and also gave a first hand account of Pascal's Méthode. This work presented a theory of ideas which remained important in philosophy courses until comparatively recent times. In 1667 Arnauld published New Elements of Geometry. This work was based on Euclid's Elements and was intended to give a new approach to teaching geometry rather than new geometrical theorems."
He was a correspondent of Gottfried Wilhelm Leibniz, and of course Pascal, who wrote the Pascal "Provincial Letters" in support of Arnauld. I enjoyed the quote about him from the Wikipedia bio: "His inexhaustible energy is best expressed by his famous reply to Nicole, who complained of feeling tired. 'Tired!' echoed Arnauld, 'when you have all eternity to rest in?"
I have not been able to find any thing in Arnauld's personal writing at this time to confirm that he was aware of or used the Pigeon-hole Principle. I have also seen a comment that there is a book by Henry (or Henrik) van Etten (pseudonym of Jean Leurechon, who coined the term thermometer) , circa 1624, which uses the method for problems involving "if there are more pages than words on any page" and various other illustrations. The writer suggests that the problem is in the French version but not the English translation. Would love to hear from someone who can confirm, and perhaps send a digital image.
Around five years after I wrote the above, I was advised of a paper published by A. Heeffer and B. Rittaud that mentioned this Leurechon (They give the date as 1622) contained a single line about the principle, and amazingly, that involved the idea of proving two men had equal hairs on their heads. " “It is necessary that two men have the same number of hairs, gold, and others.”
Later the authors add, "It is now established that an immensely popular work published at Pont-`a-Mousson in 1624 resulted from these disputationes. Entitled R´ecr´eation mathematicque, this French work is commonly attributed to Jean Leure-chon, but there are good reasons to believe that this attribution is wrong." This book goes on to explain the solution from the idea posed in the 1622 book. They say there is an English translation from 1633, which is [Jean Appier Hanzelet],Mathematicall Recreations , T. Cotes (1633).
Shortly after I wrote the original post, I had a classroom encounter with a student who presented me with another teaching moment.
A young man in one of my classes, obviously trying to improve his A+ by sucking up to the teacher, mentioned that he had read my recent blog on the pigeon-hole principle. He went on to suggest that he really doubted the idea that 39 people could randomly seat themselves and ALL be in the wrong seat. "It just seems VERY unlikely." he suggested.
Rather than tell him the answer, I set him the task of simulating the activity with a deck of cards. Pull out any suit, say the spades, and really shuffle the remaining cards well. Now we need to decide on an order for the remaining suits, so let clubs be the numbers one to thirteen in order from Ace, two, up to King for thirteen. Then the ace of diamonds can be 14, up through the King of diamonds for 26. Finally the ace of hearts is 27 up to the king of hearts for 39. Now turn over the cards and as you do count, one, two, etc... and if you get a card that is where it should be, stop.. they didn't all sit in the wrong chairs. You need not go on forever, just ten or so trials should give you an idea of whether the event is really, really uncommon, or not so very uncommon. (I now realize an easier way to do this would be to have two decks of cards, lay 39 out in one row in order, then from the shuffled deck, lay the cards one at a time under where they should appear.)
I didn't tell him that I knew the probability (or a good approximation), and that he should probably get three or four trials in a string of ten shuffles in which none of the cards landed in the right place. Such a mis-ordering of the cards was just the idea behind the first critical study of the idea we now call derangements by Leonhard Euler, the great Swiss mathematician. Euler was studying the probability of winning in the game of rencontre, now called "coincidences" in his paper "Calcul de la Probabilite dans le jeu de Rencontre", published around 1751.
So what did Euler discover? Well for larger values of N, say 39 or so, the probability of having a perfect mis-sorting of the items approaches 1/e, or about 36.8%, more than a third of the time. It is not an unusual event at all. For smaller numbers you can find the probability by using the idea shown here for six items..
. This can be rewritten more easily using the factorial notation as P= 1/2! - 1/3! + 1/4! - 1/5! + 1/6! which is only a tiny bit above 36.8%, already very close to the 1/e value given above for the limiting value. If the number of items is even, the series will be a little more than 1/e, and if it is odd (and the last term is subtracted) then the probability will be a little below 1/e, with the propbability approaching 1/e as a limit as n gets greater and greater.
My student got two completely mismatched sets of 39, and expressed surprise that it was higher than he would have thought, but he didn't sound convinced that what had occurred was not just an unusual anomaly (or else he thought I might have rigged it somehow?)
I decided to simulate a lot more times than would be practical with a deck of cards, so I cranked up Fathom, a wonderful simulation software by the folks at Key Curriculum, and had it repeat the experiment of seating the 39 people at random 1000 times, and then count how many landed in the right place. The results are shown in the graph below.
It happened that no one landed in the right place 371 times.... Hmmmm, I guess Euler got it right.
Comments about additional sources related to this are always welcomed.
Sometimes problems that seem very hard, can be very easy if they are viewed in the right way, and one of those easy ways to make some hard problems manageable is the Pigeon-Hole Principle. Over the last few weeks seems like lots of problems invovling this idea have shown up, so I thought I would bring it to you.
The basic idea is so easy any sixth grader would agree; if you have two boxes, and you are going to put three balls in the boxes, then at least one box will get more than one ball..... "well, Duh!" they answer... and yet... it seems easier to apply than it might be. Now that you know the secret, try these two problems. I'll post the answer down lower on the page where you must not look until you take a few minutes to ponder the problems.
Here is the first from a recent blog I read: "39 people are attending a large, formal dinner, which must of course occur at a single, circular table. The guests, after milling about for a while, sit down to eat. It is then pointed out to them that there are name cards labeling assigned seats, and not a single one has sat in the seat assigned to them. Prove that there is some way to rotate the table so that at least two people are in the correct seats."
This one seems tougher, but really isn't, it just requires a different way of thinking. "Suppose you pick six unique integers from 1 to 1000. Prove that at least two of them must have a difference that is a multiple of five.
I'll give you the proofs of each of these, and then get to the main topic of the history of this important theorem in discrete mathematics
Ok, The Proofs... for number one... Suppose you handed each person a number that was how many seats they needed to move to the right to find their assigned seat. Since no one is at the right seat, the number can not be zero or thirty-nine. SO each of the people has a number between 1 and 38...wait, there are 39 people...two of them (at least) must be the same distance away from their assigned seats.... admit it…..that’s pretty cool.
For number two it is sort of the same idea, but you have to think about how much each number would have for a remainder if you divided them by five. The only possible choices are 0, 1, 2, 3, or 4... but there are six numbers, so two of them have the same remainder...and two numbers that have the same remainder on division by five, are a multiple of five apart.... think of 1,6, 11, etc for remainders of one. If you want to read more about how remainders can play a part in solving problems, see my blog on "casting out sevens"
The basic idea behind this mathematical principle is what students would call common sense; if there are n objects to be placed in m receptacles (with m less than n), at least two of the items must go into the same container. While the idea is common sense, in the hands of a capable mathematician it can be made to do uncommon things. Here is a link to an article by Alexander Bogomolny in which he uses the principle to argue that there must be at least two persons in New York City with the same number of hairs on their head. This "counting hairs" approach dates back to the earliest version of the principal I have ever seen.
The same axiom is often named in honor of Dirichlet who used it in solving Pell's equation. The pigeon seems to be a recent addition, as Jeff Miller's web site on the first use of some math words gives, "Pigeon-hole principle occurs in English in Paul Erdös and R. Rado, A partition calculus in set theory, Bull. Am. Math. Soc. 62 (Sept. 1956)" (although they credit Dedekind for the principle). In a recent discussion on a history group Julio Cabillon added that there are a variety of names in different countries for the idea. His list included "le principe des tiroirs de Dirichlet", French for the principle of the drawers of Dirichlet, and the Portugese "principio da casa dos pombos" for the house of pigeons principle and "das gavetas de Dirichlet" for the drawers of Dirichlet. It also is sometimes simply called Dirichlet's principle and most simply of all, the box principle. Jozef Przytycki wrote me to add, "In Polish we use also:"the principle of the drawers of Dirichlet"
that is 'Zasada szufladkowa Dirichleta' ". I received a note that said, "Dirichlet first wrote about it in Recherches sur les formes quadratiques à coefficients et à indéterminées complexes (J. reine u. angew. Math. (24 (1842) 291 371) = Math. Werke, (1889 1897), which was reprinted by Chelsea, 1969, vol. I, pp. 533-618. On pp. 579-580, he uses the principle."
He doesn't give it a name. In later works he called it the "Schubfach Prinzip" [which I am told means "drawer principle" in German]
The idea has been around much longer than Dirichlet, however, as I found out in June of 2009 when Dave Renfro sent me word that the idea pops up in the unexpected (at least by me) work, "Portraits of the seventeenth century, historic and literary", by Charles Augustin Sainte-Beuve. During his description of Mme. de Longuevillle, who was Ann-Genevieve De Bourbon, and lived from 1619 to 1679 he tells the following story:
"I asked M. Nicole (See below for description of M. Nicole) one day what was the character of Mme. de Longueville's mind; he told me she had a very keen and very delicate mind in knowledge of the character of individuals, but that it was very small, very weak, very limited on matters of science and reasoning, and on all speculative matters in which there was no question of sentiment ' For example,' added he, ' I told her one day that I could bet and prove that there were in Paris at least two inhabitants who had the same number of hairs upon their head, though I could not point out who were those two persons. She said I could not be certain of it until I had counted the hairs of the two persons. Here is my demonstration/ I said to her: M lay it down as a fact that the best-fiimbhed (not sure what this word was supposed to be, ..Plumed??) head does not possess more than 200,000 hairs, and the most scantily furnished head b that which has only 1 hair. If, now you suppose that 200,000 heads all have a different number of hairs, they must each have one of the numbers of hairs which are between 1 and 200,000; for if we suppose that there were 2 among these 200,000 who had the same number of hairs, I win my bet But suppose these 200,000 inhabitants all have a different number of hairs, if I bring in a single other inhabitant who has hairs and has no more than 200,000 of them, it necessarily follows that this number of hairs, whatever it b, will be found between 1 and 200,000, and, consequently, b equal in number of hairs to one of the 200,000 heads. Now, as instead of one inhabitant more than 200,000, there are, in all, nearly 800,000 inhabitants in Paris, you see plainly that there must be many heads equal in number of hairs, although I have not counted them.' Mme. de Longuevillle still could not understand that demonstration could be made of the equality in number of hairs, and she always maintained that the only way to prove it was to count them. "The M. Nicole who demonstrated the principal was Pierre Nicole, (1625 -1695), one of the most distinguished of the French Jansenist writers, sometimes compared more favorably than Pascal for his writings on the moral reasoning of the Port Royal Jansenists. It may be that he had picked up the principal from Antoine Arnauld, another Port Royal Jansenist who was an influential mathematician and logician. Here is a segment from his bio at the St. Andrews Math History site.
-------------------------
He published Port-Royal Grammar in 1660 which was strongly influenced by Descartes' Regulae. In Port-Royal Grammar Arnauld argued that mental processes and grammar are virtually the same thing. Since mental processes are carried out by all human beings, he argued for a universal grammar. Modern linguistic theorists consider this work as the beginnings of the modern approach their subject. Arnauld's next work was Port-Royal Logic which was another book of major importance. It was also strongly influenced by Descartes' Regulae and also gave a first hand account of Pascal's Méthode. This work presented a theory of ideas which remained important in philosophy courses until comparatively recent times. In 1667 Arnauld published New Elements of Geometry. This work was based on Euclid's Elements and was intended to give a new approach to teaching geometry rather than new geometrical theorems."
He was a correspondent of Gottfried Wilhelm Leibniz, and of course Pascal, who wrote the Pascal "Provincial Letters" in support of Arnauld. I enjoyed the quote about him from the Wikipedia bio: "His inexhaustible energy is best expressed by his famous reply to Nicole, who complained of feeling tired. 'Tired!' echoed Arnauld, 'when you have all eternity to rest in?"
I have not been able to find any thing in Arnauld's personal writing at this time to confirm that he was aware of or used the Pigeon-hole Principle. I have also seen a comment that there is a book by Henry (or Henrik) van Etten (pseudonym of Jean Leurechon, who coined the term thermometer) , circa 1624, which uses the method for problems involving "if there are more pages than words on any page" and various other illustrations. The writer suggests that the problem is in the French version but not the English translation. Would love to hear from someone who can confirm, and perhaps send a digital image.
Around five years after I wrote the above, I was advised of a paper published by A. Heeffer and B. Rittaud that mentioned this Leurechon (They give the date as 1622) contained a single line about the principle, and amazingly, that involved the idea of proving two men had equal hairs on their heads. " “It is necessary that two men have the same number of hairs, gold, and others.”
Later the authors add, "It is now established that an immensely popular work published at Pont-`a-Mousson in 1624 resulted from these disputationes. Entitled R´ecr´eation mathematicque, this French work is commonly attributed to Jean Leure-chon, but there are good reasons to believe that this attribution is wrong." This book goes on to explain the solution from the idea posed in the 1622 book. They say there is an English translation from 1633, which is [Jean Appier Hanzelet],Mathematicall Recreations , T. Cotes (1633).
After the fact
Shortly after I wrote the original post, I had a classroom encounter with a student who presented me with another teaching moment.A young man in one of my classes, obviously trying to improve his A+ by sucking up to the teacher, mentioned that he had read my recent blog on the pigeon-hole principle. He went on to suggest that he really doubted the idea that 39 people could randomly seat themselves and ALL be in the wrong seat. "It just seems VERY unlikely." he suggested.
Rather than tell him the answer, I set him the task of simulating the activity with a deck of cards. Pull out any suit, say the spades, and really shuffle the remaining cards well. Now we need to decide on an order for the remaining suits, so let clubs be the numbers one to thirteen in order from Ace, two, up to King for thirteen. Then the ace of diamonds can be 14, up through the King of diamonds for 26. Finally the ace of hearts is 27 up to the king of hearts for 39. Now turn over the cards and as you do count, one, two, etc... and if you get a card that is where it should be, stop.. they didn't all sit in the wrong chairs. You need not go on forever, just ten or so trials should give you an idea of whether the event is really, really uncommon, or not so very uncommon. (I now realize an easier way to do this would be to have two decks of cards, lay 39 out in one row in order, then from the shuffled deck, lay the cards one at a time under where they should appear.)
I didn't tell him that I knew the probability (or a good approximation), and that he should probably get three or four trials in a string of ten shuffles in which none of the cards landed in the right place. Such a mis-ordering of the cards was just the idea behind the first critical study of the idea we now call derangements by Leonhard Euler, the great Swiss mathematician. Euler was studying the probability of winning in the game of rencontre, now called "coincidences" in his paper "Calcul de la Probabilite dans le jeu de Rencontre", published around 1751.
So what did Euler discover? Well for larger values of N, say 39 or so, the probability of having a perfect mis-sorting of the items approaches 1/e, or about 36.8%, more than a third of the time. It is not an unusual event at all. For smaller numbers you can find the probability by using the idea shown here for six items..
. This can be rewritten more easily using the factorial notation as P= 1/2! - 1/3! + 1/4! - 1/5! + 1/6! which is only a tiny bit above 36.8%, already very close to the 1/e value given above for the limiting value. If the number of items is even, the series will be a little more than 1/e, and if it is odd (and the last term is subtracted) then the probability will be a little below 1/e, with the propbability approaching 1/e as a limit as n gets greater and greater.My student got two completely mismatched sets of 39, and expressed surprise that it was higher than he would have thought, but he didn't sound convinced that what had occurred was not just an unusual anomaly (or else he thought I might have rigged it somehow?)
I decided to simulate a lot more times than would be practical with a deck of cards, so I cranked up Fathom, a wonderful simulation software by the folks at Key Curriculum, and had it repeat the experiment of seating the 39 people at random 1000 times, and then count how many landed in the right place. The results are shown in the graph below.
It happened that no one landed in the right place 371 times.... Hmmmm, I guess Euler got it right.
Comments about additional sources related to this are always welcomed.
No comments:
Post a Comment