2018 IMO #3

An anti-Pascal triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it. For example, the following array is an anti-Pascal triangle with four rows which contains every integer from 1 to 10. 

Does there exist an anti-Pascal triangle with 2018 rows which contains every integer from 1 to 1+2+...+2018?

Solution 1

The answer is $\boxed{\text{no}}$. 

Consider any anti-Pascal triangle with $n$ rows.

Let $a_k$ and $b_k$ denote the maximum and minimum number in row $k$.

Clearly, $a_{k-1} \leqslant a_k-b_k$ for all $k$, so $a_k \geqslant a_{k-1}+b_k$ for all $k$.

Summing this for $k=2,\ldots,n$ and noting that $a_1=b_1$, we have

$$a_n \geqslant b_1 + b_2 +\cdots + b_n.$$

Now for the sake of contradiction, suppose there exists an anti-Pascal triangle with $2018$ rows containing every integer from $1$ to $1+2+\cdots +2018$.

Then, we will have

$$a_{2018} \geqslant b_1 + b_2 +\cdots + b_{2018}\geqslant 1+2+\cdots +2018.$$

However, $1+2+\cdots+2018$ is precisely the maximum possible value of $a_{2018}$, so all the inequalities above are equalities, and so for each $k\geqslant 2$,

(i) $a_k$ and $b_k$ are consecutive elements of the triangle, and

(ii) $a_{k-1}$ lie directly above $a_k$ and $b_k$.

Hence all numbers $a_k$ and $b_k$ are in a "strand" of width $1$ unit from top to bottom of the triangle.

In particular, it is possible to find a sub-triangle with $\left\lceil\frac{2018-2}{2}\right\rceil=1008$ rows not containing any of $\{1,2,\ldots,2018\}$.

Re-defining $a_k$ and $b_k$ again for this sub-triangle, we have

$$a_{1008} \geqslant b_1 + b_2 +\cdots + b_{1008} \geqslant 2019 + 2020 +\cdots +3026 > \frac{2018\cdot 2019}{2}$$ which is clearly impossible. Hence, there are no anti-Pascal triangles with $2018$ rows containing every integer from $1$ to $1 + 2 + 3 + \dots + 2018$, as desired. $\square$

Solution 2

Let $b_k$ and $s_k$ be the maximum and minimum number in row $k$. Then $ { s_1, s_2, \dots, s_{2018} }$ is a permutation of ${1, 2, \dots, 2018}$. Call these the small numbers. Let $N=1+2+\dots+2018$. Call the numbers $N, N-1, \dots, N-2018$ big numbers.

Claim 1: There are at most 1010 big numbers on the bottom row

If two big numbers are consecutive on a row, they have a small number above them. There is only one small number in the second row from the bottom, so besides two all big numbers on the bottom row are at least one apart i.e. there are at most $\frac{2018}{2} + 1$ of them.

Claim 2: There are at most 2 big numbers on any row above the bottommost one

If a big number appears in a row above the bottom one, it's the difference of the two below it. So there must be a small number below it. There is only one small number on each row, so there can be at most 2 big numbers on each row above the bottommost.

Claim 3: After 100 rows from the bottom there are no more big numbers.

Suppose row#1 was the bottommost. Then $b_{100} \le N - \sum^{100}_{i=1} i < N - 2018$. Note that $b_{100}$ is the largest number in all the rows above #100, so we don't have any big numbers from there on.

Thus we can fit at most $1010+2 \cdot 100$ big numbers so we can't make room for all of them and thus it is impossible to have an anti pascal triangle of size 2018, as desired. $\square$