Interesting Puzzles

Exponentials

We all know the fable of the inventor of the chessboard, who shows his invention to the King.  The latter is so impressed that he asks the inventor to name his price for the invention. The inventor, pointing to his chessboard. says that he would like to receive one cent for the for the first square, two cents for the second square, four for the third square, eight for the fourth square, and so on - each time doubling the sum.  The King, who does not understand exponentials, readily agrees.  It is only later that one of his aides tells him that the total 'price' will come to a total of 264-1 cents, or $184,467 Trillion - far, far more than the national income of the Kingdom.1

The moral: learn how exponentials work before you make an expensive mistake.

Of course exponentials can also work for us in ways we don't forsee at first.  One is the proposition that "you're bound to have famous ancestors" if you go back far enough.  If we go back n generations, we would have 2n ancestors of that generation.  Many of us only know about a small number of our ancestors, but if we could find out all our ancestors going back 23 generations, for example, we would find 223 (or 8,388,608) in that 23rd generation.2

Of course, it is most unlikely that these are all different people.  If, for simplicity, we assume an age difference of 30 years between one generation and the next, then our ancestors of 23 generations back were born approximately 690 years before us.  For most of us that means they were born in the 13th Century.  But taking the UK, for example, that figure of 8,388,608 is definitely more people than were alive in the UK in the 13th Century.  In short, there must have been much inter-marriage between relations (distant or otherwise).

This inter-marriage makes it very complicated to estimate the actual number of distinct people amongst these 8,388,608 ancestors.  It depends on mobility and other demographic factors.  Nonetheless, for many of us, it seems reasonable to conclude that our group of ancestors from 23 generations back includes a substantial proportion of all those alive at the time, and is therefore likely to include some famous names.3

The Birthday Puzzle

This puzzle is not as well known amongst ordinary people as one might expect.  But it is one of those puzzles with an unexpected result that may be applicable to a much wider class of problems.

A lecturer teaching probability to a class of 35 students tells them that there is a more than 50% probability that at least two of them share a birthday (i.e. the day but not necessarily the year).  This assertion is met with disbelief by the students, who all feel that the chance of a match is far smaller than that.  But when the lecturer asks them to call out their dates of birth in turn, he soon finds a match.  One student asks: did the lecturer cheat, by consulting student records in advance?  No, he did not. The lecturer's confident assertion was based on a sound understanding of probability theory.

There are two tricks to the understanding of this puzzle.  The first is to understand that the outcome, "at least two of them share a birthday" includes a range of possibilities.  For example: there could be just one match between two; two matches (each between two); one match between three; and so on.  The easiest way to allow for all these possibilities is to work out the probability that no-one in the class shares a birthday with any other.  If we call that P0 , then the probability that "at least two of them share a birthday" is 1-P0 .  The second is to understand that the probability P0 (that no-one in the class shares a birthday with any other) declines rapidly as the class size increases from 10 to 40.

To see a detailed calculation, follow this link.  We can show the probability that at least two students share a birthday depends on class size as follows:

 Class size
 Probability that at least two students share a birthday
 23 50.6%
 27 62.6%
 30 70.5%
 35 81.3%
 41 90.3%

For the class of 35 described in the puzzle, the probability that at least two students share a birthday is 81.3%.  It is not surprising that the lecturer was confident to make his assertion and that he found a match in the class.

This puzzle has a much wider field of application in the analysis of network effects - in particular where our interest is to compute the probability of finding people who share an uncommon interest or characteristic.4

Notes

1 Indeed, this sum of $184,467 Trillion is the total of current world GDP accumulated over almost 3000 years.
2 And a total of 224-2 (or 16,777,214) across all generations 1 to 23.
3 For example, I can claim King Ethelred (the 'Unready') of England and King Robert the Bruce of Scotland amongst my direct ancestors.
4 See also G.M.P. Swann "The Functional Form of Network Effects", Information Economics and Policy, 14 (3), 417-429 (2002)
Comments