I was impressed when I first saw the algorithm for reservoir sampling and its proof. It is the typical "brain teaser" type puzzle with an extremely simple solution. I think it definitely belongs to the book, both the one for algorithms as well as for mathematical theorems.

As for the book, the story goes that when Erdös died and went to heaven, he requested to meet with God. The request was granted and for the meeting Erdös had only one question. "May I look in the book?" God said yes and led Erdös to it. Naturally very excited, Erdös opens the book only to see the following.

Theorem 1: ...
Proof: Obvious.

Theorem 2: ...
Proof: Obvious.

Theorem 3: ...
Proof: Obvious.