Probability Problem

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?

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.

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.