Math Olympiad problem (Oct 6), nice and not obvious

[blah_blah]

[ QUOTE ]
It actually takes the fun out of it, discovering that you need to learn a whole slew of previously inaccessible theories in order to compete at an international level. The questions are often so difficult that you need that kind of inside knowledge to have a chance.

[/ QUOTE ]

Is this really surprising? Of course IMO problems are very difficult, and of course it helps to know a lot of theory. A lot of theory arises out of finding solutions to difficult problems, i.e. galois theory for analyzing the roots of polynomial equations, and, well, the entire theory of combinatorics is essentially an exercise in developing powerful tools to deal with preexisting problems. For example, when Green and Tao proved that there are arithmetic progressions of arbitrary length in the primes using sophisticated tools from fourier analysis and ergodic theory, did they take the 'fun' out of the problem?

I used to compete in the olympiads (never went to IMO) and did fairly well on the putnam (a couple of top 200s), and I certainly can't speak for everything but I found that developing a framework to solve entire classes of difficult problems was much more fun than developing ad hoc solutions to a single problem. I know a lot of IMO gold medalists and even a couple of Putnam Fellows and while they certainly are incredibly bright and able to come up with the occasional brilliant, seemingly impossible solution, a lot of what makes them so talented is just that they have a much bigger bag of tricks and are very good at seeing just which trick to pull out of the bag at a given time.

[pzhon]

This is a well-known problem. For example, it was the subject of a paper by Stan Wagon in which he gave 14 proofs, including the 1-line calculus proof.

S. Wagon, "Fourteen proofs of a result about tiling a rectangle." Amer. Math. Monthly 94 (1987):601-617.

Incidentally, there have been several other proofs found.

Here is an example of another proof (included in Wagon's paper), which I think was mentioned the last time this question came up on the 2+2 forums. Without loss of generality, assume each tile has precisely one integral dimension. Otherwise, we can break it into two pieces which have that property. Create a (multi)graph whose vertices are the vertices of the tiles, and with one edge for each integer length side of a tile. The corners have degree 1, and all other vertices have even degree. This means that if you start at one corner, the origin, and erase edges as you traverse them, you get stuck at another corner, (0,length), (width,0), or (width,length). Your displacement from the original corner was by integral steps, so the ending point has integer coordinates, and so at least one of the length and width must be an integer.

The same combinatorial proof shows that you can't partition a rectangle with irrational dimensions into finitely many tiles with one rational dimension.

The calculus proof requires some adaptation. In some sense, it was based on one frequency. Using all rational frequencies and all integrals leads to the tensor product R/Q (x) R/Q, and then the result is immediate. Tiling follows the rules of tensor products, the sum of 0s is 0, and the only way a (x) b is 0 is if a or b is rational. (There are simpler adaptations, such as rescaling to clear the denominators, but I like this one.)

That might seem pretty far from the original calculus proof, but some change is necessary. The calculus proof not only shows that you can't partition a rectangle with nonintegral sides into finitely many tiles with one integer dimension, it also shows that you can't do so with infinitely many tiles. The analogous statement is false for tiles with one rational side, as you can partition any rectangle into infinitely many tiles with one rational side.

[pzhon]

[ QUOTE ]

People can apply any method they want, but I thought there was a rule that an acceptable problem must have the property that calculus is not the easiest method for solving the problem.

[/ QUOTE ]
Actually, if you solve one of the plane geometry problems by using a coordinate system, you generally do not get full credit. I don't like that, or the plane geometry problems, because I detest that dead-end branch of mathematics.

One of the Romanian competitors gave me a manuscript which had the basic ideas used to create many of the problems on plane geometry, inequalities, etc. If you don't go through that type of training, you are at a huge disadvantage.

[pzhon]

[ QUOTE ]
the best imo candidates probably have a much stronger algebra and combinatorics background than typical ph.d students in these fields, for example.

[/ QUOTE ]
The ones I know, who won silver and gold medals (including one who got his Ph.D. in algebra later), didn't have anything close to the background in algebra or combinatorics of a Ph.D. student at a good school when they got their medals. Usually, there is a huge difference between the superficial elementary knowledge that you need to solve simple problems and the tools you need to solve open problems.

Do you really expect the high school students know much about p-groups or representation theory or the Golay code?

While most Ph.D. students are not at good schools, and start with less than ideal backgrounds, that's not the normal interpretation of your suggestion.

[Enrique]

[ QUOTE ]
[ QUOTE ]

People can apply any method they want, but I thought there was a rule that an acceptable problem must have the property that calculus is not the easiest method for solving the problem.

[/ QUOTE ]
Actually, if you solve one of the plane geometry problems by using a coordinate system, you generally do not get full credit. I don't like that, or the plane geometry problems, because I detest that dead-end branch of mathematics.


[/ QUOTE ]

This is false. If it is complete you get full credit in the International Mathematical Olympiad. The problem is that if it is not complete, then you usually don't get any partial credit.

[Enrique]

[ QUOTE ]
[ QUOTE ]
the best imo candidates probably have a much stronger algebra and combinatorics background than typical ph.d students in these fields, for example.

[/ QUOTE ]
The ones I know, who won silver and gold medals (including one who got his Ph.D. in algebra later), didn't have anything close to the background in algebra or combinatorics of a Ph.D. student at a good school when they got their medals. Usually, there is a huge difference between the superficial elementary knowledge that you need to solve simple problems and the tools you need to solve open problems.

Do you really expect the high school students know much about p-groups or representation theory or the Golay code?

While most Ph.D. students are not at good schools, and start with less than ideal backgrounds, that's not the normal interpretation of your suggestion.

[/ QUOTE ]

If you see the list of Fields medals in the last 20 years, a big bunch of them have medals in the IMO. Perelman (solver of the Poincare conjecture and Fields Medal 2006) got a gold medal (perfect score) in 1982. Tao got a gold medal in the IMO. Timothy Gowers, fields medal 1998 was a gold medal in 1981. There are more.

I agree that they don't know the stuff you mention while in high school, but they usually get it very fast and many are quite successful in research.

[pzhon]

[ QUOTE ]
[ QUOTE ]

Actually, if you solve one of the plane geometry problems by using a coordinate system, you generally do not get full credit. I don't like that, or the plane geometry problems, because I detest that dead-end branch of mathematics.


[/ QUOTE ]

This is false. If it is complete you get full credit in the International Mathematical Olympiad. The problem is that if it is not complete, then you usually don't get any partial credit.

[/ QUOTE ]
The grading is highly subjective, and there are often disagreements.

<ul type="square">
Leader: “Your argument is absurd. In a mathematical proof you do not have to mention all the things which need not be considered.”
Co-ordinator: “You do have to mention them when their exclusion is central to the argument.”
Leader: “No you don’t, you just exclude them.”
Co-ordinator “What mark are you asking for?”
Leader: “6.”
Co-ordinator “It is worth 1.”[/list]
Here is a quote from another report:
<ul type="square">
Then we find that we have a difference of opinionconcerning David Fidler’s script. The co-ordinators do not believe that hehas given a proof at all, whereas we believe that he has given the best proofof any of our students. It is worth explaining what David has done. He tookthe geometrical configuration in question, and drew some extra lines. Theeffect of the extra lines is to make a figure which has an axis of symmetry (theoriginal configuration was not symmetrical). The existence of this symmetryenables one to read off the required result. This was geometry in the spirit ofFelix Klein and Henri Poincare. I thought we would all stand up and hug forthe joy of it all, but the co-ordinators take another view. This is not propergeometry they say. No triangles are mentioned. No angles are calculated.One of them says ‘I am here to defend Euclid’. We appeal to the problem captain who, fortunately, is more sympathetic to methods popularized after330 BC, and David gets his 3/7.[/list]
There was a specific case, perhaps in the mid 90s, where complete solutions were given 6 out of 7 points because they used an "ugly" coordinate system. Perhaps my use of the word "generally" was misleading. I'm not sure. However, you expect to get a higher score for the same results if you use methods the judges like, and I generally find them to be biased toward plane geometry.

I'd like to point out that the basic geometry of the complex plane was not understood until the 1800s. z|-&gt;conjugate(1/z) is inversion through the unit circle, and the beautiful and fundamental properties of circle inversion were not know through most of the thousands of years of study of plane geometry.

[Enrique]

You cite two examples, I agree with you that they are terrible. I was a judge two years ago, and I think that at least in my table the coordinators and my team agreed on everything. But I agree that grading is hard (specially because of the different languages).

There is a long debate about how to disperse the points before starting grading (like, if he gets to this equation he gets 2 points). I've been in many sessions and never have seen a criterion that takes the coordinate system into account, it is considered a 0 or 7 point approach. Nonetheless, the 7 is considered. One of the Mexican competitors did a problem in 1998 with a coordinate system approach. He didn't finish the computation because he was down to determine the determinant of a matrix (to compute the area of something) and ran out of time. The graders judged that the step he missed was trivial and was granted all points.

In the IberoAmerican Mathematical Olympiad. One of the Mexican competitors did a solution using centers of gravity, an idea that springs from physics. It heavily relies on vectors and physics ideas. The grader read a lot and it took her 6 hours to be able to determine if it was 7 or 0. A funny anecdote is that when she saw the competitor she gave him a finger.

I have read about olympiad competitions that stress the "no coordinate approach" but the IMO and the IberoAmerican don't have that approach, at least not when they have capable graders (which I guess it is not always easy to find, since it is a thankless, difficult job).

An example of when I graded, was that a student from Israel had a beautiful solution that no one had foreseen. When my partner and me graded it, we gave him a 0. It seemed like nonsense. Once the paper was traduced and the argument was explained by the coordinators, I asked another coordinator to follow the solution to see if I had missed anything. After 2 hours of reading, rereading, we decided the strange solution that involved high-level combinatorics was correct and we gave him the 7 points.