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.