0
$\begingroup$

We place $N$ red balls and $N$ black balls in $N$ boxes. No empty boxes. Someone picks one ball from one box.

Red ball = success, black ball = fail.

How to place balls so that we have highest probability of success (not fail). If we put all red balls in all boxes ( $1$ red in each) and all black in one, probability of picking red will be close to $1$ as $N$ grows, but how I can prove that that is best distribution (if it is) (since it will be also close to $1$ as $N$ grows if we for example put $N-1$ black balls in one and one in some other?

$\endgroup$
0
$\begingroup$

Start with any position, and show that certain moves - like moving a black ball to a fuller box - improves your chance of success. If your moves can apply to any position except the solution you mentioned, that solution must be the best.

$\endgroup$
0
$\begingroup$

With the distribution you prososed, $P_1=1-\frac1N*\frac{N}{N+1}=1-\frac{1}{N+1}=\frac{N}{N+1}$

If some box does not contain red ball then $P_2=1-\frac1N-...<\frac{N-1}{N}$, so $P_2<P_1$

so, every box must contain exactly one red ball.

If you move one black ball from the last box, $P_3=1-\frac1N*\frac12-\frac1N*\frac{N-1}N$

In general, if you move a black ball from a box1 that contains $b_1$ black balls into a box2 that contains $b_2$ black balls where $b_2<b_1$ then

  • the factor of the box1 gets from $\frac1N*\frac{b_1}{b_1+1}$ to $\frac1N*\frac{b_1-1}{b_1}$

that means that we have a decrease of $d_1=\frac1N*\frac{b_1}{b_1+1}-\frac1N*\frac{b_1-1}{b_1}=\frac1{Nb_1(b_1+1)}$

  • and the factor of the box2 gets from $\frac1N*\frac{b_2}{b_2+1}$ to $\frac1N*\frac{b_2+1}{b_2+2}$

that means that we have an increase of $d_2=\frac1N*\frac{b_2+1}{b_2+2}-\frac1N*\frac{b_2}{b_2+1}=\frac1{N(b_2+1)(b_2+2)}$

but since $b_2<b_1$, we have $d_2>d_1$.

Note that these factors are factors that get decreased from 1, in order to get your result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.