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. The following is a four-row anti-Pascal triangle containing every integer from 1 through 10:

\begin{array}{ccccccccccc} &&&&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

Step 2 of 6: Build the lightning paths

Previous step Next step

d=|u-v|\quad\Longrightarrow\quad d\to\max\{u,v\},\qquad p_{i+1}=p_i+q_i

Detailed analysis

For every entry d outside the bottom row, draw an arrow to the larger of its two children u and v. Since d is their absolute difference, the chosen child is d plus the other child. Thus, along any directed path, the value strictly increases by the sibling value at each step. The arrows always go downward, so they form directed paths ending in the bottom row.