18
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Possible duplicate of Last ball in the bag brainteaser $\endgroup$
    – f''
    May 23, 2016 at 12:03
  • 3
    $\begingroup$ @f'' This question is better than the possible duplicate : It gives the source of the puzzle, it is more general, better worded... $\endgroup$
    – Fabich
    May 23, 2016 at 12:36
  • $\begingroup$ @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 :) $\endgroup$
    – ABcDexter
    May 24, 2016 at 3:41

1 Answer 1

Reset to default
18
$\begingroup$

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.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Actually, I just changed something into bag and something into balls :) $\endgroup$
    – ABcDexter
    May 23, 2016 at 8:55
  • $\begingroup$ 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. $\endgroup$
    – ABcDexter
    May 23, 2016 at 9:06
  • $\begingroup$ Yeah, I wasn't blaming you for the obfuscation of the question. It's Dijkstra's fault. $\endgroup$
    – Gareth McCaughan ♦
    May 23, 2016 at 9:07
  • 1
    $\begingroup$ And Gries's book is very nice. $\endgroup$
    – Gareth McCaughan ♦
    May 23, 2016 at 9:07
  • 1
    $\begingroup$ Programming question: oh, that's funny. $\endgroup$
    – Gareth McCaughan ♦
    May 23, 2016 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.