Author |
Topic: The absentminded professor (Read 1549 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
The absentminded professor
« on: Mar 24th, 2003, 1:41pm » |
 Quote  Modify
|
An absentminded professor buys two boxes of matches and puts them in his pocket. Every time he needs a match, he selects at random (with equal probability) from one or other of the boxes. One day the professor opens a matchbox and finds that it is empty. (He must have absentmindedly put the empty box back in his pocket after he had taken the last match from it.) If each box originally contained n matches, what is the probability that the other box currently contains k matches?
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: The absentminded professor
« Reply #1 on: Mar 25th, 2003, 4:52am » |
Quote Modify
|
How about these thoughts:
The probability to choose either box is p = 1/2.
The absentminded professor has drawn 2n-k matches altogether. Of these, n were from the now empty box.
Now, no matter which box you define to be a "hit" (with prob. p), the overall probability of having the according number of hits (in any order) is
Pn(k) = C(2n-k,n) 0.52n-k = (2n-k)! / ( n! * (n-k)! * 22n-k )
for 0 <= k <= n, otherwise Pn(k) = 0.
Sorry for not using towr's formula generator, but to my knowledge it's not possible to hide images.
|
| « Last Edit: Mar 25th, 2003, 4:55am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: The absentminded professor
« Reply #2 on: Mar 25th, 2003, 11:54am » |
Quote Modify
|
I haven't run any simulations against mine so I it's not validated.
My calculation was based on the following statements:
There are a total of 2n matches
The professor has selected 2n-k matches.
The number of combinations of selecting 2n-k from 2n is the 2nC2n-k
Focussing on the box with k matches left (n-k removed), the number of combinations of selecting n-k from n is nCn-k
Dividing the latter by the former. You get (and it probably can be simplified further) n!(2n-k)!/(2n)! (n-k)!
So what I think I am getting is the proportion of match selections that leave the remainder (k) in a single box to the total number of ways that the matches could be selected.
I'm not totally sure that the division is a valid thing to do but it 'seems' right.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: The absentminded professor
« Reply #3 on: Mar 26th, 2003, 2:18am » |
Quote Modify
|
harpanet,
I think your concept is faulty. You said (hidden quote):
The professor has selected 2n-k matches.
This is not true, the professor selects boxes and takes any one of the matches in the selected box. So you don't need the number of combinations of selecting n-k matches from the box. Instead, you want to know how probable it is for the professor to choose one box n times and the other n-k times.
As for the formula you arrive at in the end, it can't be right. Think about the case k = 0. Your formula simplifies to an unreasonable result, right?
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: The absentminded professor
« Reply #4 on: Mar 26th, 2003, 9:17am » |
Quote Modify
|
I ran a validation program and sure enough, my equation does not fit at all. However, not wishing to write it off totally, I would like to offer this interpretation of what it means:
Given that 2n-k matches have been selected, what is the probability that the remaining k all reside in a single box?
The result for a value of k=0 is 1. This is interpreted as "given that all the matches have been selected the probability that the remaining (0) matches are all in one box is 1". A somewhat existential statement and yet not totally illogical 
Useful? Probably not. And I haven't validated it with a program! Anyway back to solving the actual problem.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: The absentminded professor
« Reply #5 on: Mar 26th, 2003, 10:51am » |
Quote Modify
|
on Mar 26th, 2003, 9:17am, harpanet wrote:| I ran a validation program and sure enough, my equation does not fit at all. |
|
By now, I more or less validated my formula using n = 2, 3, ..., 10 with 106 realizations each.
Quote:However, not wishing to write it off totally, I would like to offer this interpretation of what it means:
Given that 2n-k matches have been selected, what is the probability that the remaining k all reside in a single box? |
|
Good idea! If you're convinced you have a good answer, all you have to do is find the appropriate question! 
Alas, I think your proposal isn't working with your formula either. If I understand correctly, the professor now chooses a match (say by number from 1..2n) and then takes it from its box (A for matches 1..n, B for the rest).
In this case we seek the probability of k matches remaining all in the same box (either A or B). Each match has probability p = 0.5 of belonging to box A, all k in box A have PA(k) = 0.5k. Since we didn't specify the box beforehand, the total probability should be
P(k) = 2 * PA(k) = 0.5k-1 (1 <= k <= n).
Note that already for k = 1, "all" remaining matches have to be in the same box.
Hm, by my logic, the result is independent of n...
|
| « Last Edit: Mar 26th, 2003, 10:53am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: The absentminded professor
« Reply #6 on: Mar 26th, 2003, 8:30pm » |
Quote Modify
|
The way I see it, he has drawn a total of 2n-k matches, n of them from the first box. How many ways can he have accomplished this? C(2n-k,n). Each of the ways is equally probable. Now how many ways could he have drawn the 2n-k with or without emptying the first box? That is
Sumi=0n C(2n-k, i).
Again each way is equally probable. So the final probability is:
C(2n-k,n) / Sumi=0n C(2n-k, i).
Now you just have to simplify! I have not done so, nor compared my answer to wowbagger's yet.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: The absentminded professor
« Reply #7 on: Mar 27th, 2003, 1:57am » |
Quote Modify
|
on Mar 26th, 2003, 8:30pm, Icarus wrote:| The way I see it, he has drawn a total of 2n-k matches, n of them from the first box. |
|
Are you referring to the original absentminded professor or harpenet's wacky professor?
I suppose the latter. As for the former, the professor selects a box, looks whether it's empty, and if not takes one of the matches out. He doesn't select any particular match.
Quote:| Now you just have to simplify! |
|
Quote:| I have not done so, nor compared my answer to wowbagger's yet. |
|
I haven't done any calculations by hand, but your result seems to always give a value greater than 1 when adding all k = 0..n (for 1 <= n <= 100). That's not a good sign.
Needless to say, your result doesn't agree with mine. 
|
| « Last Edit: Mar 27th, 2003, 2:07am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: The absentminded professor
« Reply #8 on: Mar 27th, 2003, 4:41pm » |
Quote Modify
|
on Mar 27th, 2003, 1:57am, wowbagger wrote:
Are you referring to the original absentminded professor or harpenet's wacky professor?
I suppose the latter. As for the former, the professor selects a box, looks whether it's empty, and if not takes one of the matches out. He doesn't select any particular match. |
|
No - I am refering to the original puzzle. But I was calculating the wrong probability, and had an error in the calculation besides.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: The absentminded professor
« Reply #9 on: Mar 29th, 2003, 9:45am » |
Quote Modify
|
The Wacky Professor's tenure has been terminated.
I have reached very nearly the same equation as wowbagger's C(2n-k,n) 0.52n-k. Mine is C(2n-k,n-k) 0.52n-k.
I wondered at the difference and, infact, seemed to get the same results out of both of them. Then I realised that the C function is symmetrical about it's 'midpoint', which is n-(k/2).
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: The absentminded professor
« Reply #10 on: Mar 29th, 2003, 11:55am » |
Quote Modify
|
This problem is attributed to Stefan Banach, of functional analysis and Banach-Tarski paradox fame. Here's a Java applet simulation.
A more difficult problem, that I don't know the answer to, is what is the expected value of the number of matches remaining in the other box?
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: The absentminded professor
« Reply #11 on: Apr 2nd, 2003, 3:29am » |
Quote Modify
|
on Mar 29th, 2003, 9:45am, harpanet wrote:Then I realised that the C function is symmetrical about it's 'midpoint', which is n-(k/2).
|
|
It's symmetrical about more than it's midpoint. In general, C(N,K) = C(N,N-K). An intuitive understanding for this relationship might be as follows: if you're choosing k out of n kids to be on your kickball team, the number of ways to accept k people is the same as the number of ways to reject n-k people.
|
| « Last Edit: Apr 2nd, 2003, 3:29am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print