Can You Hash This Out?

A puzzle from The Ohio State University

Consider a data structure that uses
hashing to efficiently store and
retrieve integers. Prove that for any
hash table size greater than 2, even
the usually-reliable prime numbers,
“hash(x) = x^ 2” is a poor hash func-
tion. More specifically, prove that
there will always be an empty bucket.

—Dr. Bruce W. Weide and colleagues at The Ohio State University

Find the solution at: http://xrds.acm.org

Genetic Gastronomy

xkcd.com

A Great Time for PhDs in the Job Market

PhD Comics © Jorge Chan, used with permission Can you can do better? Bemusements would like your puzzles and mathematical games (but not Sudoku). Contact [e-mail] to submit yours!