CazadorDivino's blog

Prove by induction
By CazadorDivino, history, 6 years ago, In English

Hello, someone knows how can I prove the solution to this problem by induction?

Author: Manuel Blum, Awards Turing Award (1995).

  1. [Manuel Blum] Imagine a jar containing a number of white balls and black balls. Suppose also that you have an unlimited supply of white balls out of the jar. Now repeat the following procedure as long as it makes sense: remove two balls from the jar; if the two have the same color, put a white ball in the jar; if the two have different colors, put a black ball in the jar. What color is the last ball left in the jar?
int n = size(A);
	while(n>1){
		a = getball(A);
		b = getball(A);
		if(a == b)
			setball(white);
		else
			setball(black);
		n = update(A);
	}
	return A[1];
  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
← Rev. 8   Vote: I like it +22 Vote: I do not like it

Note that the answer to the base case when n = 1 is the color of the only ball that exists in the jar. If n > 1, let the initial number of black balls and the initial number of white balls in the jar be b and w, respectively, where b + w = n, and b, w ≥ 0. The initial state of the jar can be described by the state vector x(0) = [b w]. There are two possible different state-transitions:

  1. If b ≥ 2 and two black balls are selected, then x(1) = [(b - 2) (w + 1)].
  2. If ( w ≥ 2 and two white balls are selected ) or ( b ≥ 1 and w ≥ 1 and different balls are selected ), then x(1) = [b (w - 1)].

The number of balls in the jar after any of these two transitions is n - 1, and the number of the balls in the jar at state x(i) in general, where 0 ≤ i ≤ n - 1, is n - i. It is guaranteed that any state transition in any iteration does not change the odd/even parity of the number of black balls in the jar, and flips the odd/even parity of the number of white balls in the jar. As the final state of the jar with one ball left is either x(n - 1) = [1 0] or x(n - 1) = [0 1], the color of the last ball left in the jar can be determined by the odd/even parity of the initial number of black balls in the jar. If b is even, then the color is white, as the final state is guaranteed to be x(n - 1) = [0 1] regardless of the parity of the initial number of white balls in the jar, and regardless of the colors of the pair of balls chosen in each of the (n - 1) iterations. Otherwise, the color is black.**** Finally note that this odd/even parity rule applies to the base case n = 1 as well.

→ Reply