The Birthday Problems (Yes, there is more than one)

"Happy Birthday to YOU!!! ... ok, it's my mom's birthday and I was thinking about that old birthday problem. You've probably seen it. How many people must be in a room before the probability of at least two sharing a birth date (just month and year) is greater than 1/2?. Yeah, that one.

It is one of those problems that is best attacked by answering a different question, (there seem to be a lot of those in probability) what is the probability that NO two have a common birth date. If you begin by thinking of people entering a room one at a time, and calculate the probability that no two have a common birth date, then the probability after the n^th person enters is given by P(n)=P(n-1)*^(366-n) /₃₆₅. We are assuming a 365 day year here.. so P(1) = 1 (if you are the only one in the room, there is no match)..
Now the next guy has 364/365 probability of preserving the NO MATCH and so on for each new body. After each calculation we check to see if the probability of NO MATCH is less than 1/2, in which case the proabability of a match would be more than 1/2. It turns out that at n=23 the probability of at least one match is slightly over 1/2, about .507.

Actually, it only seems like the problem has been around forever. I saw a quote that it was created in 1932 by Richard von Mises, the Austrian born scientist whose work spans several areas of engineering science, however, the earliest citation I can find is " Mises, R. von. "Über Aufteilungs--und Besetzungs-Wahrscheinlichkeiten." Revue de la Faculté des Sciences de l'Université d'Istanbul, N. S. 4, 145-163, 1939.", so you decide which is right.

After you play with that for a little while, you might want to tackle one of several different variations, that can take it well beyond a high school classroom exercise. For example, the classical problem ask for when there is at least one match, but if you ask for the number so that the probability is 1/2 of exactly one matched pair, it gets a little tougher (OK, a lot tougher). With modern technology, it can be examined by students withour some of the formal probability training if they are good at simulations. I gave this problem to one class and asked them to describe a way to simulate the event using a graphing calculator. The best answer I got was this one: a) Put n (for example 23) random integers from 1 to 365 in a list 1. b) sort the list in ascending order c) copy this list 2 and then replace the last number with zero and resort just this list (effectivly this moves the zero to the top and each number down one in the list from its natural position). d) Now do a logical L1=L2 store L3. This produces a list of ones when the n th term in the list is equal to the n+1 st term, ie, for each match. Sum this list to get the number of matches. e) repeat like crazy.

I thought it was a great way to solve it, although if you have Fathom or other good statistical software for simulations, it can be done much easier, but sometimes the software hides some of the understanding in the early stages of learning simulations. When I tried it (with Fathom) and using 23 for the sample size, and 5000 trials of the experiment, there were no matches in 2431 or 48.6% of them, there was exactly one match in 1829 or 36.6% of them, and to my surprise, there were 604 or 12% that had either two seperate matches, or three of a kind.... and if you do the arithmetic, that leaves another 136 or almost 3% that had multiple matches beyond these (I used the unique value function of the program so I only knew there were less than 21 unique numbers in those cases). With the student method, adjacent ones on the third list would identify triplets etc, while seperated ones would indicate multiple pairs.

A couple of examples you might want to explore, and I will try to get back to solutions if they are not submitted sooner:
1) What happens to the birthday problem if you switch to a different number of days in the year (say 400 or 1000) or what if we use weeks or months... in short, is there a general formula for the number of people to reach the p=1/2 that there is at least one match.

2) what is the number of people needed to make the probability that EVERYONE has a match equal to or greater than 1/2?

3) and what if we only wanted to have two people who came close. What is the number of people that must be present to make the probaiblity that at least two have birthdays no more than one day apart?

4) and finally, back to the original problem, suppose a group (several hundred) are entering an auditorium, and you know that the first person to enter having a birthday that matches someone already inside will win a prize. Ok, you know not to go first, and if you go too late, it will already be gone.... so where in the line do you insert yourself to have the highest probability of being the first to enter and have a birthday match in the room?

More on all of these later..good luck, and have fun..

Whither the Schoolhouse

Recently reading Andrew Robinson's The Last Man Who Knew Everything, about the polymath Thomas Young, I came across a quote he wrote to his brother, "Although I have readily fallen in with the idea of assisting you in your learning, yet (there) is in reality very little that a person who is seriously and industriously disposed to improve may not obtain from books with more advantage than from a living instructor....Masters and mistresses are very necessary to compensate for want of inclination and exertion, but whoever would arrive at excellence must be self taught."

Yikes!!!. I am a teacher, one who struggles to "compensate for want of inclination and exertion" and I am finding I agree with him. I mean, REALLY strongly agree with him. And in the age of the internet, is not the availability of information more than ever before available to those who have the "inclination"? When you can independently peruse many of the great courses at MIT on line for free, is ignorance not a self-inflicted predicament?

All of which leads me to wonder what is the role of the typical school in the future. In many areas they have already been reduced to day-care for those intended to be held out of the workforce until a later date. My daughter in law teachers language and literature classes with more students than she has desks or textbooks, and this in a moderately wealthy community which is just outside Detroit. What educational atrocities will she face with the impending economic crisis in that area? Can the schools descend to such a state that home-schooling becomes the predominant choice of college bound students.

I can almost imagine a rebirth of that approach that was common here in England when knowledgeable people would support themselves by sitting up small instruction programs in a single topic where students would come and pay for instruction until they reached the level of competence they desired. An instruction guided mostly by independent study guided by the mentor with a few choice insights of the "masters." And if the public schools do not fade away completely, they will serve a purpose much like the gladiatorial combats of ancient Rome, to entertain the festering masses and keep them mostly off the streets while the talented few, with inclination and exertion, begin to widen the gap ever more greatly between the educational (and probably financial) haves and have-nots. I think the system will prevail, at some level for my grandchildren, but wonder at the education of their children.

Opinions are welcomed.

Harmony, and Harmonic Problems

Things happen in threes according to the old myth, and in this case it was true. I was doing some research on the early history of a mathematical problem often called the "cistern" problem. You probably know the type; "If one pipe can fill a cistern in 6 hours and another can fill it in four hours, how long would it take both pipes working together." While I was working on that, I got a nice article sent to me on the first proof that the harmonic sequence diverges... and then, I was reading a blog by Dave Marain Math Notationsin which he posed a problem that asked, in its general form, given a square inscribed in a right triangle (with one corner at the right angle of the triangle), what is the length of a side of the square in terms of the legs of the triangle.

So what do all these have in common with each other. dare I say what makes them in "harmony"?.... the answer is Harmony, or at least the mathematical relationship of the harmonic mean.

To the early Greeks, if Nichomachus can be believed, all the means were descriptive of musical relations. Much is often made of the Harmonic Mean in relation to a musical sense, but this may not represent the Greek view. Euclid used the word enarmozein to describe a segment that just fits in a given circle. The word is a form of the word Harmozein which the more competent Greek Scholars tell me means to join or to fit together. Jeff Miller's Web site on the first use of Mathematical terms contains a reference to the very early origin of the harmonic mean, 'A surviving fragment of the work of Archytas of Tarentum (ca. 350 BC) states, 'There are three means in music: one is the arithmetic, the second is the geometric, and the third is the subcontrary, which they call harmonic.' The term harmonic mean was also used by Aristotle. "
My search for the early roots of the cistern problem had taken me back to Heron's Metre'seis around the year fifty of the common era. The problem became a staple in arithmetics and problem books and was used by Alcuin (775) and appears in the Lilavati of Bhaskara (1150). I found the illustration I used on the blog for The First Illustrated Arithmetic a few days ago, from the 1492 arithmetic, Trattato di aritmetica by Filippo Calandri.
The solution to a cistern problem is the harmonic mean of the times taken by each pipe. For example, one problem asks "If one pipe can fill a cistern in three hours, and a second can fill it in five hours, how fast will the two pipes take to fill the cistern if both are opened at once. The solution is given by finding the average rate of fill of the two rates, the harmonic mean of three and five, which is three and three-quarter hours. But as the name "mean" suggest, that's the average rate of the two so working together, they would take one-half the time, one and seven-eighths hours, or about an hour and 53 minutes.

The Harmonic mean is the reciprocal of the mean of the reciprocals of the values, so for values a and b, the harmonic mean is given by which for two numbers can be simplified to the more economical
Heron might have been the first recorded example of a cistern problem, but a problem calling on the reader to use the harmonic mean occurs even earlier in the Rhind Mathematical Papyrus, now located in the British Museum, in problem 76. The problem involves making loaves of bread with different qualities, but the solution is still the harmonic mean. (I have learned from David Singmaster's Chronology of Recreational Mathematics that the cistern problem appeared, perhaps 300 years before Heron's use, in China by Chiu Chang Suan Shu (around 150 BC).


The series of terms formed by the reciprocals of the positive integers is a common torment for college students in their first introduction to analysis. The sequence in which each number gets smaller and smaller seems to very slowly approach some upper limit. Even after adding 250,000,000 terms, the sum is still less than twenty, and yet... in the mid 1300's, Nichole d'Oresme showed that it will eventually pass any value you can name. In short, it diverges, slowly, very, very slowly, to infinity. Even when warned, it seems like students want to believe it converges. A well-known anecdote about a teacher trying to get student's to remember that it diverges goes:

"Today I said to the calculus students, “I know, you’re looking at this series and you don’t see what I’m warning you about. You look and it and you think, ‘I trust this series. I would take candy from this series. I would get in a car with this series.’ But I’m going to warn you, this series is out to get you. Always remember: The harmonic series diverges. Never forget it.”<\blockquote>

By the way, each number in the harmonic series is the harmonic mean of the numbers on each side of it (so 1/2 and 1/4 have a harmonic mean of 1/3), and in fact, of any numbers equally spaced away from it such as 1 and 1/5 also have a harmonic mean of 1/3. 

And then, I came across that little problem of a square inscribed in a right triangle. If the two legs are a and b, then the sides of the square will have a length equal to the one-half the harmonic mean of a and b .  More generally, a square inscribe in any triangle with one side along a base will have sides equal to one half the harmonic mean of the base and the altitude to that base.  There are lots of other interesting problems that yeild to the use of the harmonic mean, and I mean to write again on that collection.

So I guess things do come in threes, unless I come across another one, but whether it comes in threes or fours, it all seems to work together, in perfect harmony.

Problem Solving?

Here is a neat little inspirational video my beautiful wife forwarded to me. You can draw your own meaning. For me it was a reminder of what I tell kids is the first rule of problem solving; "When you don't know what to do, do something!". Enjoy.