Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have initially $2n$ boxes and each of them contains initially 1 coin.

In each round, we select randomly 2 boxes, if both of the two boxes contain the same number of coins, for example $x$, replace them by 1 box with $x+1$ coins, otherwise, remove the one with the most coins.

After $2n-1$ rounds, only 1 box is left, the probability that the box has 2 coins is $p(2n)$

What is $\lim_{n \to \infty}p(2n)$ ?

The answer is $\frac{\sqrt{2}}{2}$.

I found this question on another forum and it fascinated me, but I don't know how to prove the answer.

share|improve this question
add comment

4 Answers

up vote 3 down vote accepted
+100

Here is a solution to the problem. Suppose that there are $N>0$ boxes to start with. Look at the boxes just before the last round, and color one black and the other white. If we move back in time, we can partition the boxes into those giving rise to the black box, which we also color black, and those giving rise to the white box, which we color white. For $n\ge 0$ and $k\in\{0,\dots,n\}$, let $p_{n,k}$ be the probability that, $n$ rounds before the last round, we have $k+1$ white boxes and $n+1-k$ black boxes. We prove by induction on $n$ that $p_{n,k}=1/(n+1)$, regardless of $k$. If $n=0$, this is obvious. Otherwise, observe that if we have $k+1$ white boxes $n$ rounds before the last, we must have had either $k$ white boxes and $n+1-k$ black boxes $n-1$ rounds before the last (case A), or $k+1$ white boxes and $n-k$ black boxes (case B). In case A, we must have chosen to combine two boxes into one of the $k$ white boxes in the preceding round, which will happen with probability $k/(n+1)$. In case B, we must have chosen to combine two boxes into one of the $n-k$ black boxes, which will happen with probability $(n-k)/(n+1)$. Therefore, $$ p_{n,k}=\frac{k}{n+1} p_{n-1,k-1} + \frac{n-k}{n+1} p_{n-1,k}, $$ and, by the induction hypothesis, this equals $1/(n+1)$, as desired.

Now, if we condition on a given partition of the boxes into white and black, the behavior of the white boxes is the same as if we had started the problem with only the white boxes, and similarly for the black boxes. Also, in the final round:

  • If we combine two boxes with 1 coin, we get a box with 2 coins.
  • If we combine a box with 1 coin with one with 2 or more coins, we get a box with 1 coin.
  • If we combine two boxes with 2 coins, we get a box with 3 or more coins.
  • If we combine a box with 2 coins with a box with 3 or more coins, we get a box with 2 coins.
  • If we combine two boxes with 3 or more coins, we get a box with 3 or more coins.

Therefore, if we let $q_N$, $r_N$, and $s_N$ be the probabilities that, starting with $N$ coins, we end up with a box with 1 coin, 2 coins, or 3 or more coins, we have the recurrence relations

$$q_N=\delta_{N1}+\frac{1}{N-1} \sum_{i+j=N, i\ge 1, j\ge 1} q_i (r_j+s_j)+(r_i+s_i)q_j, \qquad (1)$$ $$r_N=\frac{1}{N-1} \sum_{i+j=N, i\ge 1, j\ge 1} q_i q_j + r_i s_j+s_i r_j,\qquad (2)$$ $$s_N=\frac{1}{N-1} \sum_{i+j=N, i\ge 1, j\ge 1} r_i r_j + s_i s_j,\qquad (3)$$

where the sums are over the numbers $i$ and $j$ of white and black boxes we start with at the beginning.

It immediately follows by induction that, if $N$ is odd, $q_N=1$ and $r_N=s_N=0$, and, if $N$ is even, $q_N=0$ and $r_N+s_N=1$. This is because, as already mentioned, the parity of the number of boxes which contain 1 coin is preserved by each round. Therefore, from (2), for all $n>0$, $$r_{2n}=\frac{n}{2n-1}+\frac{1}{2n-1} \sum_{i+j=n, i\ge 1, j\ge 1} r_{2i} (1-r_{2j})+(1-r_{2i}) r_{2j}.\qquad (4)$$ It follows from this that, if $\lim_{n\to\infty} r_{2n}$ exists and equals $L$, say, then $L=\frac{1}{2}+L(1-L)$, so $L^2=\frac12$ and, since $L\ge 0$, $L=1/{\sqrt{2}}$. It only remains to prove that $\lim_{n\to\infty} r_{2n}$ exists.

If we multiply each side of (4) by $(2n-1)x^{2n}$ and sum over $n$, we get $$ x \frac{\partial \phi}{\partial x}-\phi=\frac{x^2}{(1-x^2)^2}+ 2\phi(\frac{x^2}{1-x^2}-\phi), $$ where $\phi=\sum_{n\ge 1} r_{2n} x^{2n}.$ This differential equation can be simplified by setting $$ x=\frac{1-t}{1+t},\qquad \phi = \theta (t-t^{-1}), $$ and then becomes, after dividing through by $(t-t^{-1})^2$, $$ \frac{t}{2} \frac{\partial \theta}{\partial t}=\frac{1}{16}-2\theta^2. $$ This is separable and can be integrated to $$ \theta=-\frac{1}{4\sqrt{2}} \frac{1-Ct^{\sqrt{2}}}{1+Ct^{\sqrt{2}}} $$ for a constant $C$, so $$ \phi=\frac{x}{\sqrt{2}(1-x^2)} \frac{ (1+x)^{\sqrt{2}}-C(1-x)^{\sqrt{2}} }{ (1+x)^{\sqrt{2}}+C(1-x)^{\sqrt{2}}.} $$ Since the coefficients of 1 and $x$ in $\phi$ must vanish, we must have $C=1$. Let $z_0:=(1-\exp \pi i/\sqrt{2})/(1+\exp \pi i/\sqrt{2})\approx -2.018i $. $\phi$ is then analytic in the complex plane with $(-\infty,-1]\cup[1,\infty)\cup\{\pm z_0\}$ removed, and we have $$ \phi=\frac{1}{2\sqrt{2}(1-x)}(1+O(x-1)) \qquad \hbox{near $x=1$,} $$ $$ \phi=\frac{1}{2\sqrt{2}(1+x)}(1+O(x+1)) \qquad \hbox{near $x=-1$.} $$ Then, by singularity analysis, $$ r_{2n}=[x^{2n}]\phi=\frac{1}{\sqrt{2}}+O(\frac{1}{n}). $$ This completes the solution.

share|improve this answer
    
How do you make that last conclusion? "Then, by singularity analysis, r2n=[x2n]ϕ=1/√2+O(1n)." –  wnvl Jan 27 '12 at 16:09
    
I used Theorem VI.5 in Flajolet and Sedgewick's book Analytic Combinatorics (algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html). The idea is that the coefficients of $\phi$ will be dominated by contributions coming from the singularities of $\phi$ nearest to the origin, which are at $\pm 1$. Near each singularity, $\phi$ can be approximated as shown above, so $[x^{2n}]\phi$ should be close to the sum of $[x^{2n}](2\sqrt{2}(1-x))^{-1}$ and $[x^{2n}](2\sqrt{2}(1+x))^{-1}$. –  David Moews Jan 27 '12 at 22:36
    
Interesting book to solve this kind of problems. –  wnvl Jan 28 '12 at 0:14
add comment

Because you care about only the probability of the remaining box having 2 coins you can look a simpler process with the same answer. Instead of tracking the exact number of coins in each box, you can just track whether the box has 1 coin, 2 coins, or 3+ coins. Call these red, green, and blue boxes respectively. Then consider the process where all boxes start red, and each round a random pair of boxes is replaced by a single new box. The replacement rule is (red, red)->blue; (red, green)->red; (red, blue)->red; (green, green)->blue; (green, blue)->green; (blue, blue)->blue. Then the question is to find the limit as $n \to \infty$ of the probability that the last remaining box is green.

Edit: Also note that the parity of boxes with a single coin is conserved.

share|improve this answer
add comment

Because the parity of boxes with a single coin is conserved, it is impossible that the process ends with a box with one coin in it. So the minimum number of coins in the final box is 2.

In fact, if at any time in the process, if each box has at least m coins in it, then the parity of the boxes with m coins is conserved. So if at any time, each box has at least m coins in it, the final box has at least m+1 coins in it.

share|improve this answer
add comment

Continueing with the idea of @none.

Let a=number of boxes with 1 coin b=number of boxes with 2 coins c=number of boxes with more than 2 coins

We can describe the current state of the system using a column vector.

$$\begin{bmatrix} a\\ b\\ c \end{bmatrix}$$

Possible next states are

(1) two boxes with 1 coin selected

$$\begin{bmatrix} a-2\\ b+1\\ c \end{bmatrix}$$

(2) a boxes with 1 coin and 2 coins selected

$$\begin{bmatrix} a\\ b-1\\ c \end{bmatrix}$$

(3) a boxe with 1 coin and >2 coins selected

$$\begin{bmatrix} a\\ b\\ c-1 \end{bmatrix}$$

(4) two boxes with 2 coins selected

$$\begin{bmatrix} a\\ b-2\\ c+1 \end{bmatrix}$$

(5) a boxes with 2 coins and >2 coins or two boxes with >2 coins selected

$$\begin{bmatrix} a\\ b\\ c-1 \end{bmatrix}$$

It is not difficult to express the transition probability as a function of a, b and c. But how should I continue from there?

share|improve this answer
1  
Case (3) should be $\left[ \matrix{a\cr b\cr c-1\cr}\right]$ –  Robert Israel Jan 24 '12 at 20:34
    
You are right. I updated my post. –  wnvl Jan 24 '12 at 20:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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