## Saturday, May 10, 2014

### Problem

A bag has 20 blue and 14 red balls.Each time you randomly take two balls out of the bag.(Assume each ball has equal probability of being taken).You do not put the two balls back.Instead,if both balls are of same color,you add a blue ball to the bag;if they have different color,red ball is put in the bag.Assume that you have infinite supply of red and blue balls,if you keep on repeating this process ,what will be color of last ball left in the bag.Will the case remains same if we have 13 red balls????

Hint:
Analyze the number of balls remaining after each withdraw

Solution:
Since we are adding only 1 ball after withdrawing 2 balls, eventually all balls would be withdrawn.

If you start with r red balls and b blue balls here is what can happen:

1) Both red: Now you have r-2 red and b+1 blue balls
2) Both blue: Now you have r red and b-1 blue balls
3) 1 red and 1 blue: Now you have r red and b-1 blue balls.

Notice that case 2) and case 3) produce same final result and can be combined.

Also notice that parity of red balls don't change (i.e. if there are even number of red balls to start with, we will have even number at end vice-versa). This means if we have odd number of red balls to start with we will have 1 in end else 0.

Whenever two balls are withdrawn, the number of blue balls remaining change by 1 (either increases or decreases) whereas the number of red balls remaining change by 2. Since, the number of red balls initially is 14; there will always be even number of red balls remaining after each withdraws of balls. Hence, the last ball to be withdrawn would be blue.

Similarly, if the number of red balls initially is 13, there would be odd red balls remaining every time. Hence, the last ball to be withdrawn would be red.