wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> The absentminded professor
        
(Message started by: NickH on Mar 24^th, 2003, 1:41pm)

Title: The absentminded professor
Post by NickH on Mar 24^th, 2003, 1:41pm

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?

Title: Re: The absentminded professor
Post by wowbagger on Mar 25^th, 2003, 4:52am

How about these thoughts:
The probability to choose either box is [hide]p = 1/2[/hide].
The absentminded professor has drawn [hide]2n-k[/hide] matches altogether. Of these, [hide] n [/hide] 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
[hide] P_n(k) = C(2n-k,n) 0.5^2n-k = (2n-k)! / ( n! * (n-k)! * 2^2n-k )[/hide]
for 0 <= k <= n, otherwise P_n(k) = 0.

Sorry for not using towr's formula generator (http://tcw2.ppsw.rug.nl/~towr/PHP/FORMULA/formula.php), but to my knowledge it's not possible to hide images.

Title: Re: The absentminded professor
Post by harpanet on Mar 25^th, 2003, 11:54am

I haven't run any simulations against mine so I it's not validated.

My calculation was based on the following statements:
[hide]
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 _2nC_2n-k
Focussing on the box with k matches left (n-k removed), the number of combinations of selecting n-k from n is _nC_n-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.
[/hide]

Title: Re: The absentminded professor
Post by wowbagger on Mar 26^th, 2003, 2:18am

harpanet,
I think your concept is faulty. You said (hidden quote):
[hide]The professor has selected 2n-k matches.[/hide]
This is not true, the professor selects boxes and takes any one of the matches in the selected box. So you don't need [hide]the number of combinations of selecting n-k matches from the box[/hide]. 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?

Title: Re: The absentminded professor
Post by harpanet on Mar 26^th, 2003, 9:17am

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.

Title: Re: The absentminded professor
Post by wowbagger on Mar 26^th, 2003, 10:51am

on 03/26/03 at 09:17:36, 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 10⁶ 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! :D
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 P_A(k) = 0.5^k. Since we didn't specify the box beforehand, the total probability should be
P(k) = 2 * P_A(k) = 0.5^k-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...

Title: Re: The absentminded professor
Post by Icarus on Mar 26^th, 2003, 8:30pm

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? [hide]C(2n-k,n)[/hide]. 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
[hide]
Sum_i=0ⁿ C(2n-k, i).
[/hide]
Again each way is equally probable. So the final probability is:
[hide]
C(2n-k,n) / Sum_i=0ⁿ C(2n-k, i).
[/hide]
Now you just have to simplify! I have not done so, nor compared my answer to wowbagger's yet.

Title: Re: The absentminded professor
Post by wowbagger on Mar 27^th, 2003, 1:57am

on 03/26/03 at 20:30:15, 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!

:P

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. ;)

Title: Re: The absentminded professor
Post by Icarus on Mar 27^th, 2003, 4:41pm

on 03/27/03 at 01:57:05, wowbagger wrote:

No - I am refering to the original puzzle. But I was calculating the wrong probability, and had an error in the calculation besides.

Title: Re: The absentminded professor
Post by harpanet on Mar 29^th, 2003, 9:45am

The Wacky Professor's tenure has been terminated.
I have reached very nearly the same equation as wowbagger's [hide]C(2n-k,n) 0.5^2n-k[/hide]. Mine is [hide]C(2n-k,n-k) 0.5^2n-k[/hide].

I wondered at the difference and, infact, seemed to get the same results out of both of them. Then I realised that the [hide]C[/hide] function is symmetrical about it's 'midpoint', which is [hide]n-(k/2)[/hide].

Title: Re: The absentminded professor
Post by NickH on Mar 29^th, 2003, 11:55am

This problem is attributed to Stefan Banach, of functional analysis and Banach-Tarski paradox fame. Here's a Java applet simulation (http://www-stat.stanford.edu/~susan/surprise/Banach.html).

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?

Title: Re: The absentminded professor
Post by william wu on Apr 2^nd, 2003, 3:29am

on 03/29/03 at 09:45:06, harpanet wrote:

Then I realised that the [hide]C[/hide] function is symmetrical about it's 'midpoint', which is [hide]n-(k/2)[/hide].

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.