Who Created the Birthday Problem, and Even One More Version

Steven Coyler who blogs at Multiplication by Infinity sent me a nice comment on my last blog that included a time line of big moments in the development of the birthday problem. It was, I believe, part of a larger work that he blogged here on conjoining the time lines from the book "50 Things You Really Should Know About Mathematics."


The last part of his time line on the birthday problem said, "1939 - Richard von Mises proposes the birthday problem." You can search almost anywhere and find that confirmed...but being the contrary guy I am, I will disagree. I realize that in disagreeing with Crilly I am disagreeing with an established world class Math Historian (his biography of Arthur Cayley is classic work)..... and yet I press on.

I think it may be that
A)the birthday problem as we know it was not first given by von Mises and
B) the typical version may have appeared over twelve years before von Mises publication.....(but von Mises may have published first).

For support I call upon that great historian of mathematical recreations, David Singmaster. In his "Chronology of Recreational Mathematics" he has:

1927 Davenport invents Birthday Problem.


|
|
|
1939 von Mises first studies Birthday Problems, but not the usual version.
1939 Ball-Coxeter: Mathematical Recreations and Essays, 11th ed. - first publication of Davenport's version of the Birthday Problem

In another note he gives source information:

Richard von Mises. Ueber Aufteilungs und Besetzungs Wahrscheinlichkeiten. Rev. Fac. Sci. Univ. Istanbul (NS) 4 (1938 39) 145 163. = Selected Papers of Richard von Mises; Amer. Math. Soc., 1964, vol. 2, pp. 313 334. Says the question arose when a group of 60 persons found three had the same birthday. He obtains expected number of repetitions as a function of the number of people. He finds the expected number of pairs with the same birthday is about 1 when the group has 29 people, while the expected number of triples with the same birthday is about 1 when there are 103 people. He doesn't solve the usual problem, contrary to Feller's 1957 citation of this paper.

and another:

Ball. MRE, 11th ed., 1939, p. 45. Says problem is due to H. Davenport. Says "more than 23" and this is repeated in the 12th and 13th editions.

Regarding Davenport, he has :

George Tyson was a retired mathematics teacher when he enrolled in the MSc course in mathematical education at South Bank in about 1980 and I taught him. He once remarked that he had known Davenport and Mordell, so I asked him about these people and mentioned the attribution of the Birthday Problem to Davenport. He told me that he had been shown it by Davenport. I later asked him to write this down.
George Tyson. Letter of 27 Sep 1983 to me. "This was communicated to me personally by Davenport about 1927, when he was an undergraduate at Manchester. He did not claim originality, but I assumed it. Knowing the man, I should think otherwise he would have mentioned his source, .... Almost certainly he communicated it to Coxeter, with whom he became friendly a few years later, in the same way." He then says the result is in Davenport's The Higher Arithmetic of 1952. When I talked with Tyson about this, he said Davenport seemed pleased with the result, in such a way that Tyson felt sure it was Davenport's own idea. However, I could not find it in The Higher Arithmetic and asked Tyson about this, but I have no record of his response.
Anne Davenport. Letter of 23 Feb 1984 to me in response to my writing her about Tyson's report. "I once asked my husband about this. The impression that both my son and I had was that my husband did not claim to have been the 'discoverer' of it because he could not believe that it had not been stated earlier. But that he had never seen it formulated."
I have discussed this with Coxeter (who edited the 1939 edition of Ball in which the problem was first published) and C. A. Rogers (who was a student of Davenport's and wrote his obituary for the Royal Society), and neither of them believe that Davenport invented the problem. I don't seem to have any correspondence with Coxeter or Rogers with their opinions and I think I had them verbally.

So my spin on all this is that probably Harold Davenport came up with the version, "How many people are needed for the probability of a match to be greater than 1/2?", but did not publish it anywhere. This is not uncommon in recreational problems. Consider the Collatz problem which seemed to circulate around and across college campuses for years with multiple names. In or around 1939 von Mises was at a party and came up with a slightly different version, "How many pairs of birthday matches would you expect for a collection of n people?" This is the inverse relationship to the common birthday problem today which asked, given an expected value of 1/2, what is the probability of a match.

I also found an interesting variation of the problem that should be of interest to Steven Coyler. The book he quoted in the comment post is authored by Tony Crilly from Manchester here in the UK. As I was checking some notes in Dr. Singmaster's sources, I came across this citation:

Tony Crilly & Shekhar Nandy. The birthday problem for boys and girls. MG 71 (No. 455) (Mar 1987) 19 22. In a group of 16 boys and 16 girls, there is a probability greater than ½ of a boy and a girl having the same birthday and 16 is the minimal number.

Folks who like probability might try to derive that result.

The problem, I am told, is in this book

Addendum: A few years after I wrote this, I came across yet another version of the birthday problem I had never considered.
How many people needed so probability is 50% that everyone shares a birthday with at least one other?
The strong birthday problem has applications to the interesting problem of look-alikes, which is of interest to criminologists and sociologists.

The answer, it seems, is 3,064.
Amazingly, with 2000 people in the room, the probability is only 1/10000, but by the time you get 4000 the probability is .9334. In even a pretty small village, there is a pretty good chance that someone else shares your birth date.

A Serendipitous Coincidence? The First-Ever Pursuit Problem.

Just reading through some old copies of the Mathematical Spectrum from my great source of mathematical periodicals, Dave Renfro. Intrigued by a couple of posts about a problem from the ancient Chinese Chiu Chang Suan Shu or Jiuzhang suanshu (Nine Chapters of Mathematical Art...about 150 BC) submitted by David Singmaster.

The problem: "A water weed grows 3 feet on the first day, and its growth on each succeeding day is half that on the preceding day. A reed grows 1 foot on the first day and its growth on each successive day is twice that of the preceding day? When are they of equal size?"

Go ahead, stop reading for a minute and try to solve it because I give an answer (actually two different ones) below and I don't want to spoil the fun.

The interesting thing to me, was the two letters of solution. My pre-calc students came through exponential growth and decay a few chapters ago, so they would approve of the first solution that was submitted. It suggested that we assume that the height of the water weed was growing according to the exponential function hw= 3 (1.5)^d-1. The reed would reach a height of hr=3^d-1. Setting these equal we would find the heights are equal when d= log₂6; or at about 2.585 days. They also pointed out that the mutual heights would be 5.705 feet.

Simple, quick, and "Wrong" according to the next commenter. They pointed out that a careful reading of the problem stated that the water weed "growth on any succeeding day is half that of the preceding day", would meant that it grew 3 feet the first day, and then successively it would grow 3/2, 3/4, 3/8 ... feet on each day.. to find the height we should sum this geometric series. So he suggests the height of the water weed would be hw=. This would result in the weed being somewhat shorter after each day than in the previous solution. In the same way, the reed should, on successive days, change by 1, 2, 4, 8 etc feet, so it would have a height of 2^d-1 after d days. Setting these equal we see that the two plants will both reach a height of five feet (exactly) after d= log₂6; or at about 2.585 days.???? WAIT, that sounds familiar....where have I ... Oh YEAH!!!, that was the answer to the problem done the first way? WOW, what a lucky coincidence........ Well, NO... the good Professor who posed the problem stepped up to assure us that, in fact, if you used those same two approaches to similar problems they would always reach equal heights at the same time... (can you prove that???)

Try for yourself. I assumed similar means that the shorter grows at r times its previous days amount, and the taller at 1/r times the previous day. Try a few. In fact, it is frequently the case that the second method gives an integer solution, and when it is not, it seems pretty easy to adjust the growth on the first day of the two plants to make it come out an integer. If we call the first day growths W and R, then the solution works out to log_r(rb/a); where r is the common ratio of the plant whose growth each day is increasing.

Dr Singmaster points out that this ancient text solves both quadratics and cubics, as well as systems of equations (including indeterminate systems with more unknowns than equations) using the "modern" method of elimination. It also is the earliest known text to have used negative numbers, and includes the rules for all the arithmetic operations. It is also the oldest know source of chase or pursuit problems, such as this one. This is problem 11 of the 7th chapter. I had the good fortune to sit with my beautiful Jeannie as the only two non-Chinese speakers at a discussion about the text at the Needham Research Institute in Cambridge by a group of English and Chinese experts. The amount I was able to take in is a credit to the patience of the gracious hosts.