Maths Olympiad Prep

Library / /14 of 15

Algebra Difficulty 6.8 National Olympiad Prove it Philippines

Problem:

The numbers from 11 to 3636 can be written in a counterclockwise spiral as follows:

3130292827
3213121110
3314329
3415418
3516567
3617181920

In the figure above, all the terms on the diagonal beginning from the upper left corner have been enclosed in a box, and these entries sum up to 7676.

Suppose this spiral is continued all the way until 20152015, leaving an incomplete square. Find the sum of all the terms on the diagonal beginning from the upper left corner of the resulting (incomplete) square.

Solutions — 2

Solution 1

Solution:

The closest perfect square to 20152015 is 2025=4522025 = 45^2 which means that only the rightmost side will be incomplete while the required diagonal would still have a total of 4545 entries.

Looking at the values on the diagonal, we see that the numbers on the diagonal above 11 have a common second difference. This suggests that this sequence satisfies a quadratic function of the form f(n)=an2+bn+cf(n) = a n^2 + b n + c. Since f(1)=1f(1) = 1, f(2)=3f(2) = 3, f(3)=13f(3) = 13, solving a simple system of three equations gives us f(n)=4n210n+7f(n) = 4 n^2 - 10 n + 7, 1n231 \leq n \leq 23. On the other hand, the numbers on the diagonal below 11 also have a common second difference. This gives a sequence g(n)=dn2+en+fg(n) = d n^2 + e n + f with g(1)=1g(1) = 1, g(2)=7g(2) = 7, and g(3)=21g(3) = 21. By solving a similar system as above, we obtain g(n)=4n26n+3g(n) = 4 n^2 - 6 n + 3, where 1n231 \leq n \leq 23. Taking the sum of these two sequences of numbers, we have

n=123[f(n)+g(n)]=n=123(8n216n+10)=8n=123n216n=123n+n=12310=8[(23)(24)(47)6]16[(23)(24)2]+10(23)=30,406 \begin{aligned} \sum_{n=1}^{23}[f(n)+g(n)] & = \sum_{n=1}^{23}\left(8 n^2 - 16 n + 10\right) \\ & = 8 \sum_{n=1}^{23} n^2 - 16 \sum_{n=1}^{23} n + \sum_{n=1}^{23} 10 \\ & = 8\left[\frac{(23)(24)(47)}{6}\right] - 16\left[\frac{(23)(24)}{2}\right] + 10(23) \\ & = 30,406 \end{aligned}

Since 11 is counted twice, the required sum must be 30,4061=30,40530,406 - 1 = 30,405.

Solution 2

Solution:

Filling the square with a few more numbers enables us to see that the boxed numbers
1,3,7,13,21,31,,1981 1, 3, 7, 13, 21, 31, \ldots, 1981
satisfy the recurrence relation a1=1a_{1} = 1 and (nN) an+1=an+2n(\forall n \in \mathbb{N})\ a_{n+1} = a_{n} + 2n. The associated homogeneous recurrence relation is solved by an(h)1a_{n}^{(h)} \equiv 1. Testing a particular solution of the form an(p)=n(cn+d)a_{n}^{(p)} = n(c n + d), we see that c=1c = 1 and d=1d = -1. Therefore, the solution to the nonhomogeneous recurrence relation is an=n2n+1a_{n} = n^2 - n + 1. The last boxed number 19811981 corresponds to n=45n = 45. Therefore,
n=145(n2n+1)=454691645462+45=30,405 \sum_{n=1}^{45} \left(n^2 - n + 1\right) = \frac{45 \cdot 46 \cdot 91}{6} - \frac{45 \cdot 46}{2} + 45 = 30,405

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.