wu :: forums - Print Page


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

        riddles >> medium >> 40 envelopes
        
(Message started by: benjaminvh on Mar 27^th, 2009, 2:09am)

Title: 40 envelopes
Post by benjaminvh on Mar 27^th, 2009, 2:09am

Hi guys

I came across this problem a little while ago.

The are 40 envelops. 5 contain A, 6 contain B, 7 contain C and the remainder (22) contain D.

Open the envelopes at random, stopping as soon as a letter appears for the 5th time. That letter (i.e. the one that appeared for the 5th time) is then the prize.

Question: what is the probability of A? And similarly B, C, D?

Title: Re: 40 envelopes
Post by SMQ on Mar 27^th, 2009, 6:08am

It's a fairly striaghtforward (if tedious) combinatorial/probability problem, no? The chance you win on A is: (the chance you pick A five times) + (the chance you pick A four times and B once, then A) + (the chance you pick A four times and C once, then A) + ... + (the chance you pick A four times, B four times, C four times and D four times, then A). Similarly for the others.

There may be a clever way to shortcut the process, though. I'll think on it some more.

--SMQ

Title: Re: 40 envelopes
Post by Eigenray on Mar 31^st, 2009, 2:56pm

For the record,

Code:

p = {5, 6, 7, 22};
e[i_] := e[i] = Array[If[# == i, 1, 0] &, 4]
f[L_] := f[L] = If[MemberQ[L, 5],
e@Position[L,5][[1,1]],
(p-L).(f[L+e@#]&/@Range@4)/Total[p-L]];
f[{0, 0, 0, 0}]

{4257449/2911044708, 4071567/646898824, 23507867/1455522354, 172209059/176426952}
~ {0.001463, 0.006294, 0.016151, 0.976093}

Title: Re: 40 envelopes
Post by Hippo on Mar 31^st, 2009, 11:06pm

on 03/31/09 at 14:56:00, Eigenray wrote:

For the record,

Code:

p = {5, 6, 7, 22};
e[i_] := e[i] = Array[If[# == i, 1, 0] &, 4]
f[L_] := f[L] = If[MemberQ[L, 5],
e@Position[L,5][[1,1]],
(p-L).(f[L+e@#]&/@Range@4)/Total[p-L]];
f[{0, 0, 0, 0}]

{4257449/2911044708, 4071567/646898824, 23507867/1455522354, 172209059/176426952}
~ {0.001463, 0.006294, 0.016151, 0.976093}

Seems I should learn this powerful language.

Thanks for explanation, now I understand most of the code. What remains is the [1,1] in the branch "5 of a same kind was selected".

(Without the transposition table (f[L_]:=) trick the computation would take a lot of time. So this is how 4dimensional dynamic programming (in rational numbers) is done in Mathematica.)

Title: Re: 40 envelopes
Post by benjaminvh on Mar 31^st, 2009, 11:50pm

what language is it? Impressive...

I managed to solve it using VBA, but this is certainly more elegant...

Title: Re: 40 envelopes
Post by Eigenray on Apr 1^st, 2009, 1:37am

It's Mathematica. The main points for reading it:
If f is a function, f@n is short for f[n]. If L is a list, then f/@L is the list obtained by applying f to each element of L. f(#)& is the function which given x, returns f(x). So
f[L+e@#]&/@Range@4
is short for
Table[f[L+e[i],{i,1,4}]
Apparently it depends on the font which one of these is shorter :)
(Edit: One could also use
f[L+#]&/@IdentityMatrix@4
but I had already defined the unit vectors e anyway. I guess
Array[f[L+e@#]&,4]
is probably best though. It has the same number of characters as the first one, but you don't need parenthesis around it.)
This is actually a matrix, and left multiplying by the vector (p-L)/Total[p-L] gives the weighted sum of the rows.
And importantly,
f[x_] := f[x] = expression(x)
does memoization. (This is because Mathematica always uses the most specific definition that applies. The first time f[a] is evaluated, it uses the general rule and performs "f[a] = expression(a)", which saves the result.)

Title: Re: 40 envelopes
Post by benjaminvh on Apr 1^st, 2009, 1:42am

thats incredible.
so the code you put there is all you need??
wow. vba was a LONG route

Title: Re: 40 envelopes
Post by towr on Apr 1^st, 2009, 2:34am

Declarative programming languages are great that way; often much shorter than imperative programming.