[Soln] 2014 Singapore MO (Open Rd 1) Problem 21

2014 SMO (Open-Rd1) 21. Let a_1, a_2, a_3, \dots, a_{2001}, \dots be an arithmetic progression such that a_1^2 + a_{1001}^2 \leq 10. Find the largest possible value of the following expression:

a_{1001} + a_{1002} + a_{1003} + \dots + a_{2001}.

A good starting point is to use definitions to introduce auxiliary variables which could help to shed light on the problem. In this problem, we are talking about an arithmetic progression (AP), hence a natural starting point would be to describe it in the usual way. Let a be the first term of the AP and d be the common difference of the AP. We then have to rewrite the conditions and expression to be found in terms of a and d.

After some algebraic manipulation, we can restate the problem:

Restatement 1. Find the largest possible value of

1001a + 1501500d

subject to the condition a^2 + (a+1000d)^2 \leq 10.

This doesn’t look too good. The numbers in the expression are rather monstrous, and in the given condition, it’s not clear how a can vary if d is fixed, and vice versa. (This would not have been the case if the condition was linear. For example, if the condition was a + 3d \leq 10, then we know that if d increases by 1, a must decrease by 3.)

Let’s take a step back and look at the problem again. What are the elements that are important? In the given condition, the important terms are a_1 and a_{1001}. The sum which we are supposed to compute can be simplified as it’s an AP:

\begin{aligned} a_{1001} + a_{1002} + a_{1003} + \dots + a_{2001} &= (a_{1001} + a_{2001}) + (a_{1002} + a_{2000}) + \dots \\  &= 2a_{1501} + 2a_{1501} + \dots \\  &= 1001a_{1501}. \end{aligned}

So actually, there are only 3 important terms: a_1, a_{1001} and a_{1501}. We can consider the AP that consists of just the 1st, 501st, 1001st, 1501st, … terms of \{ a_i \} to simplify the problem. If we let \alpha and \beta be the first term and common difference of this new AP, then we can rewrite the original problem as follows:

Restatement 2. Find the largest possible value of

1001(\alpha + 3\beta)

subject to the condition \alpha^2 + (\alpha + 2\beta)^2 \leq 10.

Compared to Restatement 1, the coefficients are smaller, but it’s still not clear how to use the constraint. Playing around with the condition, one might consider expanding it:

\begin{aligned} 2\alpha^2 + 4\alpha\beta + 4\beta^2 &\leq 10, \\  \alpha^2 + 2\alpha\beta + 2\beta^2 &\leq 5, \\  (\alpha + \beta)^2 + \beta^2 &\leq 5. \end{aligned}

The last step just seemed like a natural thing to do: try to group terms that look like expansions of squares into squares. Now we have restatement 3:

Restatement 3. Find the largest possible value of

1001(\alpha + 3\beta)

subject to the condition (\alpha + \beta)^2 + \beta^2 \leq 5.

Restatement 3 is practically the same as Restatement 2, but now I realise that I can link the terms in the constraint more directly to the terms in the expression I want to maximise: if I let x := \alpha + \beta and y := \beta, then I have Restatement 4:

Restatement 4. Find the largest possible value of

1001(x + 2y)

subject to the condition x^2 + y^2 \leq 5.

Restatement 4 is much easier to analyse. First, clearly x and y should be non-negative. (Say x is negative. Then replacing the value of x with -x does not change the value of the LHS of the constraint but increases the value of 1001(x+2y).)

Second, it is clear that the largest possible value of 1001(x+2y) happens when x^2 + y^2 = 5. (If x^2 + y^2 < 5, then we can slowly increase the value of x till equality holds.)

With the second insight, we can write x = \sqrt{5-y^2}. Finally, we have Restatement 5:

Restatement 5. Find the largest possible value of

1001(\sqrt{5-y^2} + 2y).

There are a number of ways to tackle this, but I’d say that every math olympiad student should have some rudimentary understanding of calculus. The problem can be finished off by taking the first derivative of the above, setting it to zero, and solving for y.

Alternatively, one could try to obtain some symmetry in the terms (ignoring the 1001 coefficient):

\sqrt{5-y^2} + 2y =\sqrt{5-y^2} + 2\sqrt{y^2}

Then, using the AM-QM inequality and some fiddling about, one could get

\begin{aligned} \sqrt{5-y^2} + 2\sqrt{y^2} &= \sqrt{5-y^2} + \sqrt{\frac{y^2}{4}} + \sqrt{\frac{y^2}{4}} + \sqrt{\frac{y^2}{4}} + \sqrt{\frac{y^2}{4}} \\  &\leq 5 \sqrt{\frac{5-y^2 + \frac{y^2}{4} +\frac{y^2}{4} +\frac{y^2}{4} +\frac{y^2}{4}}{5}} \\  &= 5.\end{aligned}

(But really, you are much better off using calculus.)

Hence, the maximum possible value for the expression is 1001 × 5 = 5005. The answer is 5005.

Advertisements
This entry was posted in Grade 12, Singapore and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s