A magician has a bag with B black balls and W white balls. He also has a large supply of white balls and black balls outside the bag.

At every step, the magician removes two balls from the bag chosen uniformly at random and tosses them away. If the colors of these two balls were identical, he puts one white ball in the bag, otherwise he puts a black ball in the bag.

Given B and W, what are the chances that the last ball left in the bag is white?

At StackExchange in May 2020. The puzzle is attributed to E W Dijkstra; it's mentioned in a book by David Gries (which book?)

The last ball is black iff B is odd.

(Boring) Explanation: Instead of black and white balls, let's imagine black and white warriors. At successive time steps, two warriors — chosen arbitrarily — fight with each other.

1. When two black warriors fight, they kill each other and a new white warrior comes into being magically :)
2. When two white warriors fight, exactly one dies; the other survives.
3. When a white warrior and a black warrior fight, the white warrior dies; black survives.

As time progresses,

(A) What's happening to black warriors? They are getting knocked out in pairs! If B is even, all black warriors die. If B is odd, exactly one black warrior survives.

(B) What's happening to white warriors? Either a white warrior dies or a new white warrior appears. But new white warriors appear exactly ⌊B/2⌋ times. Other than that, white warriors are simply dying one by one. Do any white warriors eventually survive? That depends on outcome of (A) and the special ability possessed by black warriors to eliminate white warriors when they fight. Therefore, if a black warrior survives (which happens when B is odd), no white warrior survives and vice versa.

Slick Explanation: Let 0 denote the color white. Let 1 denote the color black. At any step, the color of the replacement ball is determined by the XOR of 0's and 1's corresponding to the colors of the two balls drawn from the bag. Overall, the magician is simply computing the XOR over all 1's and 0's corresponding to black and white balls in the bag. How magical is that? :)