Maths Olympiad Prep

Library / /102 of 105

Algebra Difficulty 7.3 National Olympiad, round 2 Prove it JBMO

Problem:

Positive integers are put into the following table

1361015212836
2591420273544
48131926344353
71218253342
1117243241
1623
\ldots
\ldots

Find the number of the line and column where the number 2015 stays.

Solution

Solution:

We shall observe straight lines as on the next picture. We can call these lines diagonals.

1361015212836
2591420273544
48131926344353
71218253342
1117243241

Figure 1

On the first diagonal is number 11.
On the second diagonal are two numbers: 22 and 33.
On the third diagonal are three numbers: 44, 55 and 66.
On the nn-th diagonal are nn numbers. These numbers are greater than (n1)n2\frac{(n-1)n}{2} and not greater than n(n+1)2\frac{n(n+1)}{2}.
On the first nn diagonals are 1+2+3++n=n(n+1)21+2+3+\ldots+n=\frac{n(n+1)}{2} numbers.
If mm is in the kk-th row, ll-th column and on the nn-th diagonal, then it is m=(n1)n2+lm=\frac{(n-1)n}{2}+l and n+1=k+ln+1=k+l. So, m=(k+l2)(k+l1)2+lm=\frac{(k+l-2)(k+l-1)}{2}+l.
We have to find such numbers nn, kk and ll for which:
(n1)n2<2015n(n+1)2n+1=k+l2015=(k+l2)(k+l1)2+l \begin{gathered} \frac{(n-1)n}{2}<2015 \leq \frac{n(n+1)}{2} \\ n+1=k+l \\ 2015=\frac{(k+l-2)(k+l-1)}{2}+l \end{gathered}
From (1), (2), (3):
n2n<4030n2+n    n=63, k+l=64, 2015=(642)(641)2+l n^2-n<4030 \leq n^2+n \implies n=63,\ k+l=64,\ 2015=\frac{(64-2)(64-1)}{2}+l
So 2015=2016+l2015=2016+l so l=20152016=1l=2015-2016=-1 (but this is not possible, so check calculation).
Actually, (642)(641)2=2016\frac{(64-2)(64-1)}{2}=2016, so l=20152016=1l=2015-2016=-1.
But (63)(62)2=1953\frac{(63)(62)}{2}=1953, 64632=2016\frac{64\cdot 63}{2}=2016.
So 2015=1953+l2015=1953+l, l=20151953=62l=2015-1953=62.
So k+l=64k+l=64, l=62l=62, so k=2k=2.

Therefore, 20152015 is located in the second row and 6262-th column.

Firstly, we can see that the first elements of the columns are triangular numbers. If aia_{i} is the first element of the line ii, we have ai=i(i1)2a_{i}=\frac{i(i-1)}{2}.
The second element of the first row is obtained by adding to the first element 22.
The second element of the second row is obtained by adding to the first element 33.
And so on, then the second element on the nn-th row is obtained by adding to the first element n+1n+1.
Then the third element of the nn-th row is obtained by adding n+2n+2, and the kk-th element of it is obtained by adding kk.
Since the first element of the nn-th row is (n1)n2+1\frac{(n-1)n}{2}+1, the second one is (n1)n2+1+(n+1)=n(n+1)2+2\frac{(n-1)n}{2}+1+(n+1)=\frac{n(n+1)}{2}+2.
The third one n(n+1)2+1+(n+2)=(n+1)(n+2)2+3\frac{n(n+1)}{2}+1+(n+2)=\frac{(n+1)(n+2)}{2}+3, so the kk-th one should be (n+k2)(n+k1)2+k\frac{(n+k-2)(n+k-1)}{2}+k.

(n+k2)(n+k1)2+k=2015n2+n(2k3)+k2k4028=0 \frac{(n+k-2)(n+k-1)}{2}+k=2015 \Leftrightarrow n^2+n(2k-3)+k^2-k-4028=0
To have a positive integer solution, (2k3)24(k2k4028)=161218k(2k-3)^2-4\left(k^2-k-4028\right)=16121-8k must be a perfect square.
From 161218k=x216121-8k=x^2, it is noticed that the maximum of xx is 126126 (since k>0k>0).
Simultaneously, xx is odd, so x125x\leq 125.
161218k=x21252+4968k=x216121-8k=x^2 \Leftrightarrow 125^2+496-8k=x^2
So 4968k=0496-8k=0, from that k=62k=62.
From that we can find n=2n=2.
So 20152015 is located on the second row and 6262-th column.

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.