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.

A box contains $731$ black balls and $2000$ white balls. The following process is to be repeated as long as possible.

(1) arbitrarily select two balls from the box. If they are of the same color, throw them out and put a black ball into the box. (We have sufficient black balls for this).

(2) if they are of different colors, place the white ball back into the box and throw the black ball away.

What will happen at last? Will the process stop with a single black ball in the box or a single white ball in the box or with an empty box?

I am unable to decide how to start and in which direction? should we apply probability or what?

share|improve this question
    
Hint: you could model this process by master equations quite easily analogous to reaction processes, as a stochastic dynamical process. See for instance Ornstein-Uhlenbeck processes. –  al-Hwarizmi Jul 17 '13 at 17:15
    
Could you please elaborate or give a link to understand? –  Nimit Jul 17 '13 at 17:28
    

3 Answers 3

up vote 6 down vote accepted

First, the number of balls in the box decrease by one at each step. Suppose $B(t)$ and $W(t)$ are the number of black and white balls present after $t$ steps. Since we start with $B(0)+W(0)=2731$ and $B(t+1)+W(t+1)=B(t)+W(t)-1$, we have that $B(2730)+W(2730)=1$. At this point we can no longer continue the process. So at this end, there is either a white ball or a black ball left.

Notice that the number of white balls present at any time is even. For instance, suppose we have just done step $t$. If we choose two black balls, then $B(t+1)=B(t)-1$ and $W(t+1)=W(t)$. If we choose a white ball and a black ball, then $B(t+1)=B(t)-1$ and $W(t+1)=W(t)$. If we choose two white balls, then $B(t+1)=B(t)+1$ and $W(t+1)=W(t)-2$. Necessarily, since $W(0)$ is even, it stays even throughout the process.

Hence $W(2730)=0$ and $B(2730)=1$. Even though what happens throughout the process is random, by parity, the process must end with only one black ball left.

share|improve this answer
    
I wrote a program that simulates this problem, and after millions of runs, I always ended up with a black ball. +1 –  Josué Molina Jul 17 '13 at 17:06
    
Here is the program, if interested: gist.github.com/molinaw1/6022501 –  Josué Molina Jul 17 '13 at 17:13
1  
@JosuéMolina I was about to ask for the program. It helped. Thank you. :) –  Nimit Jul 17 '13 at 17:22
    
Here is python program to simulate it. I also end up with black ball. github.com/dilawar/algorithms/blob/master/gs_tifr/… –  Dilawar Sep 24 '13 at 16:00

Doing this for small values of the number of balls quickly reveals the pattern. It turns out the total number of balls always decreases by one, and the number of white balls always keeps the same parity. So we necessarily pass through a state with a single ball, and as the number of white balls is always even, this last ball must be black.

share|improve this answer

Let $B$ and $W$ denote the number of black and white balls respectively in the box. Note that the two operation affect the state of the system as:

\begin{align} (B,W) \rightarrow (B-1,W) \\ (B,W) \rightarrow (B+1,W-2) \end{align}

Every operation decreases the number of balls by 1. Considering the state transition diagram, if we start with an even number of white balls our final ball with be black, otherwise if we start with an odd number of white balls ($W$) the final ball will be white. One can establish that by checking simple cases like $(3W,2B)$ and ($3W,3B$). With ($731B,2000W$), the final ball will be $B$.

share|improve this answer

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.