An urn contains an unknown number of white and black balls (but more than one).
logic/invariants/djikstras.urn
Problem
An urn contains an unknown number of white and black balls (but more than one). You extract two balls from the urn. If they are of the same color, you put a black ball back into the urn, otherwise you put a white ball back into the urn. Under what conditions will the last ball in the urn be black?
Show solution
The trick is to note that you are never changing the parity of the number of white balls in the urn. If you picked out two black, you put a black back; two white, you put a black back; one white and one black, you put a white back. Thus if the original number of white balls was even, the last ball will be black, otherwise it will be white.