Hello, someone knows how can I prove the solution to this problem by induction?
Author: Manuel Blum, Awards Turing Award (1995).
- [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];