What is a good Olympiad problem?

It must be easy to state and understand but difficult to solve. The solution should not require any prerequisites but cleverness. Indeed, once the solution is known, the solver may enjoy its simplicity and/or condemn himself for not being able to solve it! A high school student should not be at a disadvantage as compared to a professional mathematician.

Example:
What is the maximum number of terms in a sequence with the property that every 7-sum (sum of 7 consecutive terms) is negative but every 11-sum is positive? }

It is an earnest request to at least understand (the difficulty of) the problem before looking up at the (Tinkle see-n-smile) solution at the end of the post.

The problem is a gem for another reason. It employs the oft-used trick in Maths to count the same objects in two different ways and come up with interesting results. I have seen such a counting method in a proof of the Quadratic Reciprocity (the recipe of which goes, Gauss’ Lemma \to Eisenstein’s Lemma \to lattice-point counting), another in computing the famous 2-sum \sum_{n=1}^{\infty} \frac{1}{n^2} by evaluating the same integral, (cf. Fubini) and in obtaining different basic combinatorial formulae.

More on this later.

___________________________________________________________

Solution to the above problem:

a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 < 0
a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 < 0
\vdots
a_{11} + a_{12} + a_{13} + a_{14} + a_{15} + a_{16} + a_{17} < 0

Answer: 16

For those who did not understand even after staring at this picture for 300 seconds, click here for an explanation.
____________________________________________________________

Advertisements