Gerrymandering urns (redux) This is a rehash of this question (and probably the intent of this, and several other similar questions), but I'd like:


a more detailed answer that builds from the simplest cases to potentially higher order applications and more references to explanations, if possible. 
a proof of the optimality of the so-called gerrymandering solution.


So here is a complete statement of the problem:


  Suppose that you are given 50 each of red and blue balls, and two
  urns. You place the red and blue balls in the urns (so that each is
  nonempty, and all the balls are allocated to some urn). Then you pick a jar at
  random and pick a ball at random. The objective is to distribute the
  red and blue balls in each of the urns so that the probability of
  picking a red ball is maximized.


The so-called gerrymandering solution is given after the break below, and I am wondering if there is a systematic way of arriving at this solution, other than guesswork. 



Attempt 1

My first thought was to use calculus on this problem, so that if I denote the jars A and B, and denote the tuple $(x, y)$ as the number of red and blue balls in jar A. The the solution $(x^*, y^*)$ is the solution to the first-order conditions. (This is probably a red herring, since only nonnegative integer solutions are valid.)

$$
\begin{alignat}{2}
&amp;&amp;p(x, y) &amp;= \frac{1}{2}\left(\dfrac{x}{x+y}+ \dfrac{50-x}{100-x-y}\right) \\[1em]
&amp;&amp;\left. \dfrac{\partial p(x, y)}{\partial x}\right|_{(x,y)=(x^*, y^*)} &amp;= 0 \\[1em]
&amp;\implies\quad&amp;\dfrac{2x^*+y^*}{(x^*+y^*)^2}-\dfrac{150-2x^*-y^*}{(100-x^*-y^*)^2} &amp;=0 \\[1em]
&amp;&amp;\left. \dfrac{\partial p(x, y)}{\partial y}\right|_{(x,y)=(x^*, y^*)} &amp;= 0 \\[1em]
&amp;\implies\quad&amp;  \dfrac{-x^*}{(x^*+y^*)^2} +\dfrac{50-x^*}{(100-x^*-y^*)^2} &amp;= 0
\end{alignat}
$$

This involves finding the solution of cubic equations (which I am sure can be done, with the help of CAS, but it is not obvious that this yields the gerrymandering solution (does it?)). Is this the right way to think about the problem? What is? 



Attempt 2

Note however that the objective function is closed-form, so can easily be graphed, and then the solution becomes clear.





The gerrymandering solution

You place one red ball and no blue balls in one urn and all the other balls in the other urn. This leads to the probability of picking a red ball $&gt;\tfrac{1}{2}$.
Assume that we decide to put $50-r$ balls into urn $A$ and $50+r$ balls into urn $B$ where $r$ is between $0$ and $49$ inclusive. Furthermore we decide to put $s$ red balls into urn $A$ and $50-s$ red balls into urn $B$. The number of blue balls in urn $A$ will then be $50-r-s$, and the number of blue balls in urn $B$ will then be $r+s$. Since all four numbers of balls have to be nonnegative we obtain the conditions
$$s\geq0, \quad s\leq 50-r,\quad s\leq 50,\quad s\geq -r\ .$$
As $r\geq0$ these conditions are fulfilled iff $0\leq s\leq 50-r$.

The probability $P$ to draw a red ball computes to
$$P={1\over2}\ {s\over 50-r}+{1\over2}\ {50-s\over 50+r}\ .$$
Keep $r$ fixed for the moment. Increasing $s$ by one produces a $$\Delta P={1\over2}\Bigl({1\over 50-r}-{1\over 50+r}\Bigr)&gt;0\ .$$
In order to maximize $P$ we should therefore give $s$ the maximal allowed value $50-r$. The resulting value of $P$ is then
$$P={1\over2}\ {50-r\over 50-r}+{1\over2}\ {50-(50-r)\over 50+r}={1\over2}+{1\over2}\Bigl(1-{50\over 50+r}\Bigr)\ .$$
This is maximal when $r$ is maximal, i.e., if $r=49$, and this leads to $s=1$. 

Therefore the optimal way to distribute the balls is putting one red ball into urn $A$ and all the other balls into urn $B$. The resulting probability $P$ of drawing a red ball is then about ${3\over4}$.
I've seen this mentioned in the context of job interview questions before.

The Gerrymandering solution was seen as correct.

There are probably other options, depending on how cheeky you're feeling.

For example:

If the urns are narrow, take advantage of serial correlation and tip the blue balls in first then the red on top. The probability of picking red is now significantly closer to one. Hey, they never said the contents would be randomly permuted?! So am I meant to put them in and then permute them myself rather than just pick randomly from the available (all or largely red) balls? I mean, my hand's made of meat, so I'd actually have to move them round by some sort of algorithm... and what's the seed? Oh, I picked that too, right?

OK, OK, maybe that's cheating... but do you want a candidate who thinks about stuff like serial correlation or someone who thinks everything is independent?! Blah, etc.