Source: Variant of a sub-problem in my seminar presentation on "Security Attacks on RSA" . Very interesting (and difficult) algorithms problem.
Problem: An array of length n+1 is populated with integers in the range [1, n]. Find a duplicate integer (just one, not all) in linear time with O(1) space. The array is read-only and may not be modified.
Update(20/01/10): Solution (from Gurmeet Singh Manku's blog) posted in comments!!