The third variant of the problem (where one prisoner is allowed to make one change, which can guarantee that every prisoner survives) is the one I heard first; I like that problem because it seems even more counter-intuitive, but also makes it easier to understand why it works.