Author |
Topic: 40 envelopes (Read 900 times) |
|
benjaminvh
Newbie
Posts: 3
|
 |
40 envelopes
« on: Mar 27th, 2009, 2:09am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: 40 envelopes
« Reply #1 on: Mar 27th, 2009, 6:08am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 40 envelopes
« Reply #2 on: Mar 31st, 2009, 2:56pm » |
Quote Modify
|
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}
|
| « Last Edit: Mar 31st, 2009, 3:00pm by Eigenray » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 40 envelopes
« Reply #3 on: Mar 31st, 2009, 11:06pm » |
Quote Modify
|
on Mar 31st, 2009, 2:56pm, 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.)
|
| « Last Edit: Apr 1st, 2009, 9:39am by Hippo » |
IP Logged |
|
|
|
benjaminvh
Newbie
Posts: 3
|
|
Re: 40 envelopes
« Reply #4 on: Mar 31st, 2009, 11:50pm » |
Quote Modify
|
what language is it? Impressive...
I managed to solve it using VBA, but this is certainly more elegant...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 40 envelopes
« Reply #5 on: Apr 1st, 2009, 1:37am » |
Quote Modify
|
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.)
|
| « Last Edit: Apr 1st, 2009, 2:18am by Eigenray » |
IP Logged |
|
|
|
benjaminvh
Newbie
Posts: 3
|
|
Re: 40 envelopes
« Reply #6 on: Apr 1st, 2009, 1:42am » |
Quote Modify
|
thats incredible.
so the code you put there is all you need??
wow. vba was a LONG route
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 40 envelopes
« Reply #7 on: Apr 1st, 2009, 2:34am » |
Quote Modify
|
Declarative programming languages are great that way; often much shorter than imperative programming.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print