Solutions to interesting problems with elegant and unintuitive methods

Question

I am looking to build a repertoire of olympiad type problems which have non-intuitive elegant solutions, If possible instead of a resource, I think problems would be the best. (i.e. select the best problem to post here).

The problem I like best that falls into this category is to prove that if a bigger rectangle has some smaller rectangles completely space filling inside it, and the small rectangles have at least one side of integer length, then we need to show that the big rectangle has at least one integer length.

The non-intuitive(to me) solution is to place each smaller rectangle on a checkerboard with side length of the pattern = 1/2. Then to note that each smaller rectangle must have an equal area of black and white. Then to prove that for any checkerboard to have an equal area of black and white, it must have one of the lengths of integer length.

Answer 1

The checkerboard and domino puzzle ( http://www.jimloy.com/puzz/dominos.htm) has an interesting, simple and elegant solution.

However, consider the generalization of this problem, where instead of removing squares at diagonal corners you remove one white square and one black square from anywhere on the board. When is it possible to tile such a reduced checkerboard?

The answer is that it is always possible to tile such a checkerboard, but the proof relies on a very elegant but non-obvious construction. I remember seeing the solution in Ross Honsberger's Mathematical Gems and it blew me away.

Answer 2

Here's what I thought was the cannonical example, but five minutes of internet search can't find a reference, so I must be misremembering some piece of it.

Suppose you have two mountain climbers. Each climber can move up or down the mountain as they choose (i.e. their height is not necessarily monotonically increasing or decreasing), but their height as a function of time is continuous and differentiable (i.e. they can't magically hop from one place to another).

Now suppose A descends from the summit at 6 AM and reaches the base at 6 PM. The next day, B starts ascending at 6 AM and reaches the summit at 6 PM. Will there be some time at which they were both at the same height? For example, if they both moved at the same rate, then at 12 PM they would both be halfway up. But they don't necessarily need to go at the same speed, nor are they even required to always move in the same direction, so we can't guarantee they'll meet at 12.

The "trick" is to plot them as two lines on a graph. Since they're continuous and differentiable, they must intersect somewhere, which implies that there must be some time that they're at the same height.

Answer 3

All good riddles satisfy your requirements. This riddle is excellent since the statement and the solution are both easy, but the solution is quite non-obvious.