2
$\begingroup$

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.

  • 0
    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). QED2011-03-11
  • 8
    Intuition is in the eye of the beholder. Anything can seem intuitive with the right background.2011-03-11
  • 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.2011-03-12
  • 0
    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?2011-03-12
  • 0
    @Pete: I know there are books out there. But there must be some question/solution that just stays in your mind because you did not see the elegant solution that was written up. I just want people to post their most favorite of these. @QY: I understand, and thats why its what you found unintuitive. Not what everyone agrees is unintuitive. I would have never thought of the checkerboard.2011-03-12
  • 0
    @picakhu: it seems to me like you didn't answer my question. There are books which collect problems that the authors at least have found elegant and unintuitive. This is very subjective, so you or I might or might not agree. But once again: what do you want that is not already in the literature?2011-03-12
  • 0
    @pete: sorry about that, what I mean to say is that not everything written by an author is always intended to be elegant and unintuitive. I mean their aim is to sell their book. Which means they need some traditional approaches. Sometimes, creative solutions may be discovered by trial and error and missed by the author. I am looking for fairly involved problems, of about putnam level, but with solutions at about middle-school or high school level. Like the question that I posted can be a putnam level question, but the answer is a middle school answer.2011-03-12
  • 0
    @pete: the two solutions additional posted above are also easy and nice, but they lack the "wow" element(in my opinion). The reason being that they are very mathematical. Unlike my favorite method which is creative in that it involves coloring in a non-obvious way.2011-03-12
  • 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.2011-03-12
  • 0
    @Albert: That is the point. I am not looking for all the possible solutions you found unintuitive, just one that you would have never thought of before you saw the solution. In hindsight all methods are "obvious".2011-03-12

3 Answers 3

2

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.

  • 0
    another awesome example :)2011-03-12
  • 0
    Due to a lack of other questions, I'll choose yours as the best.2011-03-14
1

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.

  • 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)2011-03-11
  • 0
    @picakhu: Fair enough. I suppose my intuition is not up to par :-)2011-03-12
1

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.

  • 0
    This is nice...2011-03-12