Hurray! I have returned :)
Let's start from an easy one:
The following is a well known puzzle. I have encountered it several times in my life.
(cited from:
http://www.techinterview.org/post/526363745/red-marbles-blue-marbles/)
"You have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red."
Solution:
The solution to this puzzle is to throw one red marble to one of the jars (say, w.l.o.g, jar A) and to throw all other marbles (49 reds and 50 blues) to the other jar (jar B). If we do so the probability to pick a red marble is:
Let's start from an easy one:
The following is a well known puzzle. I have encountered it several times in my life.
(cited from:
http://www.techinterview.org/post/526363745/red-marbles-blue-marbles/)
"You have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red."
Solution:
The solution to this puzzle is to throw one red marble to one of the jars (say, w.l.o.g, jar A) and to throw all other marbles (49 reds and 50 blues) to the other jar (jar B). If we do so the probability to pick a red marble is:
\(P(picking\, a\, red\, marble)=\)
\(P(picking\, a\, red\, marble|choosing\, jar\, A)\cdot P(choosing\, jar\, A)+\)
\(P(picking\, a\, red\, marble|choosing\, jar\, B)\cdot P(choosing\, jar\, B)=\)
\(1\cdot\frac{1}{2}+\frac{49}{99}\cdot\frac{1}{2}\sim0.74\)
This solution is also well known and easy to come up with, however most of the places and web sites that solve this puzzle fail to post a convincing proof for this solution. Indeed trying to find a rigorous explanation for it might be seem a little tedious, but it is essential -from my experience facts that seem 'obviously true' can fall apart easily with close inspection.
Proof of Solution
The method of the proof is the following:
We start with any ordering of the marbles in the jars (we call this ordering 'ordering 1'( and show that the probability to draw a red marble in this ordering will always be smaller or equal than the probability to draw a red marble with the ordering of the solution (we call this ordering- 'ordering 2').
We use the following notations:
(These notation are all with respect to ordering 1)
The number of blue marbles in jar A - \(\textrm{N}_{blue}^{A}\)
The number of red marbles in jar A - \(\textrm{N}_{red}^{A}\)
The number of blue marbles in jar B - \(\textrm{N}_{blue}^{B}\)
The number of red marbles in jar B - \(\textrm{N}_{red}^{B}\)
\(1\cdot\frac{1}{2}+\frac{49}{99}\cdot\frac{1}{2}\sim0.74\)
This solution is also well known and easy to come up with, however most of the places and web sites that solve this puzzle fail to post a convincing proof for this solution. Indeed trying to find a rigorous explanation for it might be seem a little tedious, but it is essential -from my experience facts that seem 'obviously true' can fall apart easily with close inspection.
Proof of Solution
The method of the proof is the following:
We start with any ordering of the marbles in the jars (we call this ordering 'ordering 1'( and show that the probability to draw a red marble in this ordering will always be smaller or equal than the probability to draw a red marble with the ordering of the solution (we call this ordering- 'ordering 2').
We use the following notations:
(These notation are all with respect to ordering 1)
The number of blue marbles in jar A - \(\textrm{N}_{blue}^{A}\)
The number of red marbles in jar A - \(\textrm{N}_{red}^{A}\)
The number of blue marbles in jar B - \(\textrm{N}_{blue}^{B}\)
The number of red marbles in jar B - \(\textrm{N}_{red}^{B}\)
W.l.og - we assume that \(\textrm{N}_{red}^{A}\leq \textrm{N}_{red}^{B}\).
We also need to assume that \(0<\textrm{N}_{red}^{A}\). Because if one of the jar doesn't have any red marbles then the probability of getting a red marble is \(\frac{1}{2}\cdot\frac{50}{50+\textrm{N}_{blue}^{B}}\leq\frac{1}{2}\) which is smaller than the probability of our solution.
Now let us move all the blue marbles from jar A to jar B. We call this new ordering - 'ordering 3'.
We also need to assume that \(0<\textrm{N}_{red}^{A}\). Because if one of the jar doesn't have any red marbles then the probability of getting a red marble is \(\frac{1}{2}\cdot\frac{50}{50+\textrm{N}_{blue}^{B}}\leq\frac{1}{2}\) which is smaller than the probability of our solution.
Now let us move all the blue marbles from jar A to jar B. We call this new ordering - 'ordering 3'.
Lemma 1
First I will show that :
\(\frac{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\geq\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\) (1)
Proof of Lemma 1
This inequally is valid if and only if both the l.h.s and the r.hs. complementaries to 1 will satisfy the opposite inequallity:
\(\frac{\textrm{N}_{blue}^{B}}{\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\leq\frac{\textrm{N}_{blue}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\).
Note that the denominator of the l.h.s is greater than the denominator of the r.h.s- hence this inequality holds.
\(\frac{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\geq\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\) (1)
Proof of Lemma 1
This inequally is valid if and only if both the l.h.s and the r.hs. complementaries to 1 will satisfy the opposite inequallity:
\(\frac{\textrm{N}_{blue}^{B}}{\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\leq\frac{\textrm{N}_{blue}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\).
Note that the denominator of the l.h.s is greater than the denominator of the r.h.s- hence this inequality holds.
We will show that:
\(P(picking\, a\, red\, marble\, with\, ordering\, 1)\leq P(picking\, a\, red\, marble\, with\, ordering\, 3)\)
Proof:
\(P(picking\, a\, red\, marble\, with\, ordering\,1)=P_{1}=\)
\(\frac{1}{2}\cdot\frac{\textrm{N}_{red}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}+\frac{1}{2}\cdot\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\)
\(P(picking\, a\, red\, marble\, with\, ordering\,3)=P_{3}=\)
\(\frac{1}{2}\cdot1+\frac{1}{2}\cdot\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\)
We take the difference between \(P_{3}\) and \(P_{1}\) and get :
\(P_{3}-P_{1}=\)
\(\frac{1}{2}\cdot\left(1-\frac{\textrm{N}_{red}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\right)\)
\(=\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\right)\)
\(=\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\right)\)
\(\geq\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\right)\)
Where the last inequality holds because of Lemma 1 ( we subtract a smaller quantity). Carring on :
\(=\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)-\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\right)\).
Now all we need to show is that :\(\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)\geq\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\right)\).
but this inequality holds since \(\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}\geq\textrm{N}_{blue}^{A}\), and \(\textrm{N}_{red}^{B}\geq \textrm{N}_{red}^{A}\) because of our assumption. Therefore the denominator of the l.h.s is smaller than the denominator of the r.h.s.
but this inequality holds since \(\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}\geq\textrm{N}_{blue}^{A}\), and \(\textrm{N}_{red}^{B}\geq \textrm{N}_{red}^{A}\) because of our assumption. Therefore the denominator of the l.h.s is smaller than the denominator of the r.h.s.
We have proven the 'hard part'. We are only left with the relatively easy part of proving that moving from ordering 3 to ordering 2 can only increase the odds of getting a red marble. I leave this proof for the reader.
No comments:
Post a Comment