IMO 2018 · Problem 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.

\[ \begin{array}{ccccccc} &&&4&&&\\ &&2&&6&&\\ &5&&7&&1&\\ 8&&3&&10&&9 \end{array} \]

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

Official text of the problem. Official problem paper (PDF)

Answer

No.

Solution

Put \(n=2018\) and \(N=n(n+1)/2\). Suppose such a triangle exists. It has exactly \(N\) entries, so its entries are precisely \(1,2,\ldots,N\), each occurring once.

Number the rows from top to bottom. Let \(m_r\) and \(M_r\) denote the minimum and maximum entries in row \(r\). Every entry in row \(r-1\) is the absolute difference of two entries in row \(r\), so \[ M_{r-1}\le M_r-m_r \qquad (2\le r\le n). \] Since \(M_1=m_1\), summing gives \[ m_1+m_2+\cdots+m_n\le M_n\le N. \] But the row minima are \(n\) distinct positive integers, so \[ m_1+m_2+\cdots+m_n\ge 1+2+\cdots+n=N. \] Thus equality holds, and the row minima are exactly \(1,2,\ldots,n\), in some order. Because every entry occurs only once, each row contains exactly one entry at most \(n\). Call these entries small.

Call an entry large if it belongs to \[ \{N-n+1,N-n+2,\ldots,N\}. \] There are exactly \(n=2018\) large entries. We will bound how many the triangle can contain.

First, all large entries lie in the bottom \(64\) rows. Indeed, iterating the inequality for row maxima gives \[ M_r\le M_n-\sum_{j=r+1}^{n}m_j \le N-\sum_{j=r+1}^{n}m_j. \] If there are at least \(64\) rows below row \(r\), their distinct positive minima have sum at least \[ 1+2+\cdots+64=2080>2018=n. \] Consequently \(M_r<N-n\), so row \(r\) contains no large entry.

Second, every row other than the bottom row contains at most two large entries. To see this, let a large entry \(v\) have children \(x>y\). Then \[ v=x-y,\qquad y=x-v\le N-(N-n+1)=n-1. \] Thus every large entry has a small child. The next row contains exactly one small entry, and a given entry can be a child of at most two entries in the row above. This proves the bound.

Finally, partition the bottom row into its \(1009\) consecutive disjoint pairs. If both entries of a pair are large, their absolute difference is at most \(n-1\); hence the entry immediately above that pair is small. Different pairs give different entries in the row above, which contains only one small entry. Therefore at most one pair contains two large entries, and the bottom row contains at most \[ 1009+1=1010 \] large entries.

There are only \(63\) other rows among the bottom \(64\) rows. The total number of large entries is therefore at most \[ 2\cdot63+1010=1136<2018, \] contradicting the existence of all \(2018\) large entries. Hence the required triangle does not exist.

The solution was checked against the official IMO shortlist solutions.