Collected over several years by Peter Winkler, of Bell Labs, dozens of elegant, intriguing challenges are presented in Mathematical Puzzles.
The answers are easy to explain, but without this book, devilishly hard to find.
Creative reasoning is the key to these puzzles. No involved computation or higher mathematics is necessary, but your ability to construct a mathematical proof will be severly tested--even if you are a professional mathematician.
For the truly adventurous, there is even a chapter on unsolved puzzles.