# A classical combinatorial puzzle

It is a classical puzzle by Edsger Dijkstra. Not quoting the original problem but changing it into bag and balls, the puzzle is:

A bag contains some black and white balls. The following process is to be repeated as long as possible (assuming that we have infinite supply of black and white balls).

• Randomly select two balls from the bag. If they are the same color, throw them out, but put an extra black ball in.
• If they are different colors, place the white one back into the bag and throw the black one away.

As you can see that each iteration of the process reduces the number of balls in the bag by one. Also, repetition of the process must terminate with exactly one ball in the bag. The question is:

What, if anything, can be said about the color of the final ball based on the number of white balls and the number of black balls initially in the bag.

• Possible duplicate of Last ball in the bag brainteaser – f'' May 23 '16 at 12:03
• @f'' This question is better than the possible duplicate : It gives the source of the puzzle, it is more general, better worded... – Fabich May 23 '16 at 12:36
• @f'' You might say that this puzzle is also a possible duplicate, but I have tried to remain original by posting the author of the puzzle and you can read the comments on the accepted answer that it was from a good book :) – ABcDexter May 24 '16 at 3:41

What can be said is that

the parity of the number of white balls never changes. Therefore, if there is an odd number of white balls initially then the last ball in the bag must be white; if an even number, the last ball must be black.

The way the puzzle is stated is, I think, deliberately unclear. You could equivalently (and more transparently) say: at each step you either remove one black ball, or remove two white and add one black. This also makes it a little more explicit that

at each step the parity of the number of black balls changes, which of course it must since you're removing one ball each time and the white parity is invariant.

(Of course the two statements aren't quite equivalent if for some reason you care about probabilities, since in the original version you remove two balls at random and let that determine which of the two things you do; but the puzzle itself is interested only in the worst case.)

• Actually, I just changed something into bag and something into balls :) – ABcDexter May 23 '16 at 8:55
• Anyways, your answer is absolutely correct. The original problem is called The coffee can problem, i read it in a book called Science of Programming by David Gries. Also, please have a look at this question. – ABcDexter May 23 '16 at 9:06
• Yeah, I wasn't blaming you for the obfuscation of the question. It's Dijkstra's fault. – Gareth McCaughan May 23 '16 at 9:07
• And Gries's book is very nice. – Gareth McCaughan May 23 '16 at 9:07
• Programming question: oh, that's funny. – Gareth McCaughan May 23 '16 at 9:08