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.
Does there exist an anti-Pascal triangle with $k=2018$ rows which contains every integer from $1$ to $N=1 + 2 + 3 + \dots + 2018$?
Proposed by Morteza Saghafian, Iran
==================================
By the way, this turned out to be a known result. See another solution and a sharper result from Taiwan more than 40 years ago!
Solution:
We show that anti-Pascal triangle with $k\geq 25$ rows doesn't exist.
Proof:
We prove by contradiction. Consider an anti-Pascal triangle $T$.
Terminology
-We number the rows of $T$ such that row $i$ has exactly $i$ numbers.
-A number is small if it is less than or equal to $k$.
-A number is big if it is greater than or equal to $N-k$.
-Numbers $a$ and $b$ are the parent and delta of number $c$, respectively, if $a$ and $b$ are immediately below $c$ and $a=b+c$.
Remark A big number's delta must be small.
Intuition: Smaller numbers spread evenly across the rows of $T$.
Lemma Each row $i$ has exactly one small number $m_i$.
Consider the number in the top row and the chain of deltas as we traverse $T$ from it to parent at each step until arriving at the bottom row. We got $k$ distinct numbers that sum up to no more than $N=1+\ldots+k$, so these deltas must all be small.
Lemma In each row $i$, $m_i$ is right next to $M_i$, the largest number in row $i$. $M_{i-1}+m_i=M_i$. All numbers in $(M_{i-1},M_i)$ are in row $i$ or below.
We attempt to place numbers from bottom to top rows. Suppose $m_i$ and $M_i$ have been placed in row $i$ . Where can $M_i-1$ be if it's not $M_{i-1}$? It has to be right above something larger, which are all in row $i$ or below by induction. If it's in row $i-1$ it must be right above $M_i$, though row $i$ has only one small number so $M_i-1=M_{i-1}$, contradiction. Similarly, all else in $(M_{i-1},M_i)$ couldn't be in row $i-1$ or above.
Intuition: Too many big numbers have to go to bottom rows, leading to contradiction.
The left hand side is the number of big numbers and they all have to be in row $k-n$ or below. The bottom row can have at most $\lceil\frac{k+1}{2}\rceil$ big numbers while each of the $n$ rows right above can have no more than two, because all these big numbers must have a small number as delta right below.
Note that $\frac{1}{2}n(n+1)\leq m_k+m_{k-1}+\ldots+m_{k-n+1}=M_k-M_{k-n}\leq N-(N-k)=k$, which is impossible for $k\geq 25$.
Q.E.D.
