Martin Dietzfelbinger has pointed out to me that this paper contains a
calculation error in the proof of Lemma 2, making the proof incorrect.
A nicer version of this proof, that doesn't involve tedious calculations
or Stirling's approximation, but that gives a weaker bound, can be
found here:
http://cg.scs.carleton.ca/~luc/cuckoo.pdf
Of course, other (correct) proofs are also available.