You have a jar with 20 black balls and 16 white balls. At each step,

1. You remove two balls.

2. If the two balls are of the same color, you add a black ball. Otherwise you add a white ball.

You repeat these steps until there is only 1 ball remaining in the jar. What is the color of the remaining ball?

As a follow-up question, suppose you start with 100 black balls and 93 white balls. What is the color of the remaining ball?

- via Algorithmic puzzles

Black for 20/16

White for 100/93

Noye: I did this with a simulation and am surprised at latter answer.

Waiting for pure math solution.

Click here for solution.

1. 2 white: In this case, we replace 1 black ball, so we now have x+1 black balls, and y-2 white balls.

2. 2 black: In this case, we replace 1 black ball, so we have x-1 black balls and y white balls.

3. 1 white and 1 black: In this case, we replace a white ball, thus we effectively have x-1 black balls and y white balls.

Thus, in each step, we either remove a black ball, or we replace 2 white balls by 1 black ball irreversibly until only 1 ball is left. Therefore, each white ball is equivalent to 2 black balls. Thus if there are an odd number of white balls, the last ball is white, and if there is an even number of white balls, the last ball is black.

The parity of the number of white balls never changes.

Lizard: This is beautifully and simply put. Thank you.

Very elegant solution, Lizard. Thanks