Problems
Ozzie's RiskHere is a problem offering practice with Permutations, but also introducing the mysterious growth constant e. Those who remember the Lesson formulas will zip through the first part of the problem at sight. Tables of permutations are nevertheless included, for the convenience of those who are being referred to this page from other Lessons.
Problem
The Tycoons in their top hats like to lunch at the corner table in Ozzie's Grill. Austin, the richest, is always there. Basil, the next richest, joins the party from Tuesday on. Cecil, who since he is only third richest has to work through lunch two days in the week, turns up beginning Wednesday. Dinsmore first appears on Thursday, and harried Edsel is only there on Friday. At the end of lunch, each Tycoon present puts his business card in one of the top hats. In order of wealth, each draws a card from the hat. The first Tycoon to draw his own card pays for lunch. If no Tycoon draws his own card, they put on their top hats and walk out without paying. Mild-mannered Ozzie is then stuck with the cost of the lunch.
Question: What is Ozzie's Risk, the chance that Ozzie is stuck for the cost of lunch? And what is that cost, averaged over one week?
Answer 1
On Mondays, Austin puts his own card in the hat, draws it out again (it is his own card; there is only 1! = 1 way that 1 card can be drawn from a set consisting of 1 card), and pays for lunch. Ozzie's risk is 0 out of 1, or 0/1 = 0.0000.
Answer 2
On Tuesdays, Austin and Basil put their cards in the hat. Let us call their respective cards A and B. There are 2 cards in the hat, and there are 2! = 2 ways in which they can be drawn. These are the two ways:
AB BA
Austin goes first. If the cards are drawn in AB order, he draws his own card, and pays. If the order of drawing is BA, Austin will not draw his own card (the first card is B), but neither will Basil (the second card is A). In that case, out of the two possibilities, Ozzie is stuck with the cost of the lunch in just one option. His risk is 1 out of 2, or 1/2 = 0.5000.
Answer 3
On Wednesdays, we have three Tycoons, and 3! = 6 ways of drawing the cards from the hat:
ABC BAC CAB
ACB BCA CBAAs the emphasized letters show, in 2 cases Austin (going first) draws his own card (A), in 1 case Basil (going second) draws his own card where Austin had not previously drawn his own card (B), and in 1 case Cecil draws his own card where neither Austin nor Basil had previously done so (C). In the other 2 cases, Ozzie pays. His risk is thus 2/6 = 0.3333.
Answer 4
On Thursdays, with Dinsmore joining in, we have four Tycoons, and 4! = 24 ways of drawing the cards from the hat:
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADBC BDCA CDBA DCBAThere are 6 ways in which Austin, going first, can draw his own card, 4 ways for Basil (going second), 3 for Cecil (going third), and 2 for Dinsmore (going fourth). There are thus 15 ways in which one or another of the Tycoons pays for lunch, leaving 9 outcomes in which Ozzie pays. His risk is thus 9/24 = 3/8 = 0.3750.
Answer 5
On Fridays, Edsel completes the company, and there are 5! = 120 possible sequences for the final card draw. They are:
ABCDE BACDE CABDE DABCE EABCD
ABCED BACED CABED DABEC EABDC
ABDEC BADCE CADBE DACBE EACBD
ABDEC BADEC CADEB DACEB EACDB
ABECD BAECD CAEBD DAEBC EADBC
ABEDC BAEDC CAEDB DAECB EADCBACBDE BCADE CBADE DBACE EBACD
ACBED BCAED CBADE DBAEC EBADC
ACDBE BCDAE CBDAE DBCAE EBCAD
ACDEB BCDEA CBDEA DBCEA EBCDA
ACEBD BCEAD CBEAD DBEAC EBDAC
ACEDB BCEDA CBEDA DBECA EBDCAADBCE BDACE CDABE DCABE ECABD
ADBEC BDAEC CDAEB DCAEB ECADB
ADCBE BDCAE CDBAE DCBAE ECBAD
ADCEB BDCEA CDBEA DCBEA ECBDA
ADEBC BDEAC CDEAB DCEAB ECDAB
ADECB BDECA CDEBA DCEBA ECDBAAEBCD BEACD CEABD DEABC EDABC
AEBDC BEADC CEADB DEACB EDACB
AECBD BECAD CEBAD DEBAC EDBAC
AECDB BECDA CEBDA DEBCA EDBCA
AEDBC BEDAC CEDAB DECAB EDCAB
AEDCB BEDCA CEDBA DECBA EDCBAThis counts out to 24 options in which A pays, 18 in which B pays, 14 in which C pays, 11 in which D pays, and 9 in which E pays. This gives a total of 76 options out of 120 in which somebody pays. The remainder, 44/120 = 0.3667, is Ozzie's Risk.
Assessment To Date
Here is a table divided by number of Tycoons present, showing who pays and how often, and what is Ozzie's Risk in that situation:
Tyc A Pays B Pays C Pays D Pays E Pays Tyc Pay Oz Pays 1 1.0000 1.0000 0.0000 2 0.5000 0.0000 0.5000 0.5000 3 0.3333 0.1667 0.1667 0.6667 0.3333 4 0.2500 0.1667 0.1250 0.0833 0.6250 0.3750 5 0.2000 0.1500 0.1167 0.0917 0.0750 0.6334 0.3667 Shutting it Down
That is the end of the problem as defined. It is given that one each of the 5 possible configurations of lunching Tycoons occurs each business week. Over time, and in percentages, Ozzie's Risk should work out as shown in the table. But his financial risk varies with the number of lunching Tycoons present. With 1 tycoon, he has no risk, with 2 Tycoons, he has an 0.5000 chance of being out 2 lunches, or a liability of 1 lunch. With 3 Tycoons, he has an 0.3333 chance of being out 3 lunches, again, a liability of 1 lunch. With 4 Tycoons, he is at risk for an average of 1.5 lunches, and with 5 Tycoons, for an average of 1.834 lunches. His total liability for each week, over time, will average out to the sum of those lunches, or 5.334 lunches, in a week where the Tycoons have consumed a total of 15 lunches.
For the problem as defined at the outset, If Ozzie raises the price of lunch by 5.334/15 = 0.3556, he will cover his losses, over time, and can look on with equanimity as the Tycoons file in, any one weekday noon, and sit down around the corner table.
Opening It Up
So we have Ozzie covered, and our homework is technically over. But the answer is just a number. It is not very interesting. Suppose we open the problem up by taking off the limit on 5 lunching Tycoons. What happens when there are 6 or more Tycoons?
We can get a vague idea of the answer by noticing the Ozzie's Risk figures in the table above. They start from 0, jump to 0.5, recede to 0.3333, rise again to 0.3750, and in short, they oscillate ever more closely around a figure which we have not yet reached, but which seems to be in the neighborhood of 0.36. What is that figure, and why are we asymptotically approaching it in this way? In short, what is going on here?
Computation
First we identify the mystery figure to which Ozzie's Risk approaches. Enough of full tables of options, let's use what we know, or failing that, let's use what, with a little trouble, we can see happening.
Ozzie's Risk is simply 1 minus the Tycoons' Risk, and it is the Tycoons' Risk that is amenable to analysis, because we know the fractions out of which it is composed. Those fractions are the risk of each Tycoon, and the risk of each Tycoon depends on how many Tycoons are present. Given n Tycoons, the number of possible ways of drawing the cards out of the top hat is simply n!. The fraction representing the risk of each Tycoon thus has n! as its denominator. And we can see, whether by reason or by inspection (it does not matter in the slightest how you get it, just get it), that the fraction for the risk of Tycoon A will always have (n-1)! as its numerator.
The numerators for the risks of Tycoons B and higher are not quite so obvious. So let's look back over the data. Here is a table of numerators for all the above options:
1st Numerator All Numerators Numerators Differ By (n = 1) 0! = 1 1 (n = 2) 1! = 1 1, 0 1 (n = 3) 2! = 2 2, 1, 1 1, 0 (n = 4) 3! = 6 6, 4, 3, 2 2, 1, 1 (n = 5) 4! = 24 24, 18, 14, 11, 9 6, 4, 3, 2
In other words, we can compute A's fractional risk from first principles (that is, from n or the number of lunchers), and we can compute the numerators of successive fractions, for B, C, and so on, by subtracting the set of previous numerators from that first new numerator. Terrific. Knowing this, and knowing nothing else, we can immediately write down the Tycoons' Risk numerators for n = 6. They will be:
5!=120, 120-24=96, 96-18=78, 78-14=64, 64-11=53, 53-9=44
From which the actual Tycoons' Risk fraction for n = 6 will be:
(120 + 96 + 78 + 64 + 53 + 44) / (6!=720) = 455/720 = 0.6319
and Ozzie's risk is 1 minus this, or 0.3681. No permutation charts required.
With that much of a head start, it is child's play to write down the fraction for the next few values of n. We wouldn't presume to do it here. We skip ahead, and present instead a cumulative table of n = 1~8:
Tycoons' Risk Ozzie's Risk (n = 1) 1.0000 0.0000 (n = 2) 0.5000 0.5000 (n = 3) 0.6667 0.3333 (n = 4) 0.6250 0.3750 (n = 5) 0.6334 0.3337 (n = 6) 0.6319 0.3681 (n = 7) 0.6321 0.3679 (n = 8) 0.6321 0.3679
and our mystery number has stabilized. To four decimal places, it is 0.3679.
Epiphany
So what? Thus may ask some smart aleck in the back row.
So this, my friend: 0.3679 is the reciprocal of the growth constant e (2.71828); that is, 1/2.71828 = 0.3679. And now, if you ever hope to be a mathematician, go you home and sit you down and ponder why.
Social Outcome
Ozzie, grasping this principle (even if our back row does not), at once raises his lunch price by exactly 36.8 cents on the dollar. And what do you suppose happens when the Tycoons next turn up for lunch and look at the bill of fare? Do they grouse that things are more expensive? Do they raise an eyebrow that the $10 Special is now the $13.68 Special? Remember, these are men in sealskin coats, men who can do the Exponential Distribution in their sleep, men who can quote you a monthly mortgage payment for 20 years at 8% without reaching in the drawer for the little green book. These are men who know the score.
They look at the bill of fare, and one mumbles, Hmm, base times 1 plus 1/e. He looks over at Ozzie, and he gives Ozzie just the very slightest little nod of acknowledgement.
Not bad, Ozzie.
For Extra Credit
What is Basil's Risk, in terms of the number of lunches he is liable to pay for?
Contact The Project / Exit to Resources Page
