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

[sirio11]

I really like this problem:

A rectangle is partitioned into several smaller rectangles. Each of the smaller rectangles has at least one side of integer length. Prove that the big rectangle has at least one side of integer length.

Good luck

[bigpooch]

This was posted here awhile ago (with a neat solution).

I think the most interesting thing about the problem is
that it can be generalized to n>=2 dimensions in a very nice
way: if there are at least m (where 1<=m<=n-1) of the
dimensions of each n-dimensional subparallelepiped are of
integer length, this must also be true of the "containing"
parallelepiped.

[blah_blah]

ugh your problems are so boring and i'm drunk right now so i will write my answer unspoilered.

integrate exp(2\pi i (x+y)) over all the rectangles. on one hand a simple computation shows that it is zero iff a given rectangle has an integer side length, and on the other hand the sum of the (line) integral(s) over all the little rectangles is equal to the (line) integral over the big rectangle, and each of the little rectangles integrate to zero, so the big rectangle integrates to zero as well, and hence has an integral side length, which is precisely the desired result.

[sirio11]

Dude, the Olympiad is for high school students, so you can't integrate exp(2\pi i (x+y)) over all the rectangles.

[blah_blah]

there was a problem on this years IMO that people applied the combinatorial nullstellensatz to, I hardly think a bit of integration (note: this isn't contour integration!) is beyond the grasp of most students. Of course there is the checkerboard solution and whatnot.

also i apologize for being a dick in my last post. in particular this is one of my favorite problems as well, but i haven't found most of your previous problems very compelling.

[thylacine]

blah_blah said:[ QUOTE ]
ugh your problems are so boring and i'm drunk right now so i will write my answer unspoilered.

integrate exp(2\pi i (x+y)) over all the rectangles. on one hand a simple computation shows that it is zero iff a given rectangle has an integer side length, and on the other hand the sum of the (line) integral(s) over all the little rectangles is equal to the (line) integral over the big rectangle, and each of the little rectangles integrate to zero, so the big rectangle integrates to zero as well, and hence has an integral side length, which is precisely the desired result.

[/ QUOTE ]


sirio11 said:[ QUOTE ]
Dude, the Olympiad is for high school students, so you can't integrate exp(2\pi i (x+y)) over all the rectangles.

[/ QUOTE ]



blah_blah said:[ QUOTE ]
there was a problem on this years IMO that people applied the combinatorial nullstellensatz to, I hardly think a bit of integration (note: this isn't contour integration!) is beyond the grasp of most students. Of course there is the checkerboard solution and whatnot.

also i apologize for being a dick in my last post. in particular this is one of my favorite problems as well, but i haven't found most of your previous problems very compelling.

[/ 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.

So I am wondering: Am I right about there being such a rule? Or did there used to be such a rule and it changed? Where exactly did this problem come from? And is there a solution easier than the above `calculus' solution?

[blah_blah]

there is an easier solution which is also elementary, but I like my (it's not 'mine' in any reasonable sense) solution more. Embed the rectangles in a checkerboard where each square has a side length of 1/2. Each rectangle has a side of integer length iff the black area within the rectangle is equal to the white area, and the result immediately follows.

i don't know if there is an explicit calculus rule, and even if there is it's not particularly significant - the olympiads of many countries contain calculus problems (romania, for example), and even if they do not the imo level candidates certainly are well versed in those techniques and many others. the best imo candidates probably have a much stronger algebra and combinatorics background than typical ph.d students in these fields, for example.

[thylacine]

I see. Square wave instead of sine wave.

I'm sure I heard of the calculus rule (for IMO problems) from someone who knew, but it might have changed.

[sirio11]

thy,

I was a juror in the IMO 2 years ago and certainly there wasn't any calculus rule or any set of knowledge you couldn't use for that matter. Still I'm not totally sure if there's a written rule for the problems chosen from the short list.

Blah is right and some Olympians (especially those from the stronger countries) are well versed in subjects well above high school level. But I for one think this kind of kill the spirit of the competition, since sometimes the ones who solve the problems are the ones with the most experience and training and not necessarily the most creative and intelligent ones; unless you think the most intelligent students on Earth use to be born in China for some strange reason.

I've always preferred problems with elementary solutions and minimal knowledge and maximal creativity required. The elementary solution presented by Blah is a beautiful example, it's exquisite and I feel a great pleasure anytime I find solutions like that one.

Of course I don't have a clue about the math level and interest for these problems in this forum, that's the reason I use to choose "easy" problems. But it's not that hard to post pretty difficult problems just to impress the elite.

[Phil153]

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.

I really like this question. I have a feeling there should be an answer simple/clear enough to explain to a 10 year old, but I haven't found it yet.