Chapter 5.3, Problem 43ES

Define a game as follows: You begin with an urn that contains a mixture of white and black balls, and during the game you have access to as many additional white and black balls as you might need. In each move you remove two balls from the urn without looking at their colors. If the balls are the same color, you put in one black ball. If the balls are different colors, you put the white ball back into the um and keep the black ball out. Because each move reduces the number of balls in the urn by one, the game will end with a single ball in the urn. If you know how many white balls and how many black bails are initially in the urn, can you predict the color of the ball at the end of the game? [This exercise is based on one described in “Why correctness must be a mathematical concern" by E. W. Dijkstra, www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD720.html.]
H a. Map out all possibilities for playing the game starting with two balls in the urn, then three balls, and then four balls. For each case keep track of the number of white and black balls you start with and the color of the hall at the end of the game.
H b. Does the number of white balls seem to be predictive? Does the number of black balls seem to be predictive? Make a conjecture about the color of the ball at the end of the game given the numbers of white and black balls at the beginning.
c. Use mathematical induction to prove the conjecture you made in part (b).