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