Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The nicer solution is to define the *area of $[x_1,x_2]\times [y_1,y_2]$ as $((x_2)-(x_1))((y_2)-(y_1))$, where $(z)$ is the fractional part of $z$. Prove that *area is additive (extend all segments to lines parallel to the sides of the big rectangle). QED –  Yuval Filmus Mar 11 '11 at 23:44
8  
Intuition is in the eye of the beholder. Anything can seem intuitive with the right background. –  Qiaochu Yuan Mar 11 '11 at 23:47
1  
Yet another solution is to consider the integral of $sin(2\pi x)sin(2\pi y)$ over your big rectangle. This is equal to the sum of the integrals over all of the little rectangles, and thus is zero (Since all of the little rectangles have at least one side of integer length.) From this we can conclude that the big rectangle also has a side of integer length. –  Albert Steppi Mar 12 '11 at 0:06
    
There are lots of books collecting contest-type problems and solutions: some of these are encyclopedic (i.e., all Putnam problems from year X to year Y) and some choose problems according to type, difficulty, technique of solution, elegance (in someone's opinion) and so forth...Could you explain what you want to do that is not already contained in this large literature? –  Pete L. Clark Mar 12 '11 at 0:16
1  
All three of the solutions are really just variations on the same idea: Produce a function on rectangles which is additive and maps a rectangle to zero if and only if the rectangle has a side of integer length. When I was first told about the solution I gave, I found it unintuitive, but now I find all three of the solutions pretty intuitive. –  Albert Steppi Mar 12 '11 at 15:41
show 5 more comments

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
another awesome example :) –  picakhu Mar 12 '11 at 0:19
    
Due to a lack of other questions, I'll choose yours as the best. –  picakhu Mar 14 '11 at 4:52
add comment

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.

share|improve this answer
3  
This is a common problem, and I feel that that is intuitive. I just think of two people moving one from top to bottom, and one bottom to top, obviously they will meet. if they take the same road. I am looking for problems where the question is not obvious, and neither is the solution. (there may be obvious solutions of-course) –  picakhu Mar 11 '11 at 23:36
    
@picakhu: Fair enough. I suppose my intuition is not up to par :-) –  Xodarap Mar 12 '11 at 2:37
add comment

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.

share|improve this answer
    
This is nice... –  picakhu Mar 12 '11 at 0:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.