MathLabs

第3题

反帕斯卡三角形是一个等边三角形数组:除最底行的数以外,每个数都等于其正下方两个数之差的绝对值。下面是一个包含从 1 到 10 的每个整数的四行反帕斯卡三角形: 42657183109\begin{array}{ccccccccccc} &&&&4&&&&\\ &&&2&&6&&&\\ &5&&7&&1&&&\\ 8&&3&&10&&9 \end{array} 是否存在一个 2018 行的反帕斯卡三角形,使其包含从 1 到 1+2+⋯+20181+2+\cdots+2018 的每个整数?
第 2/6 步:构造闪电路径
d=∣u−v∣⟹d→max⁡{u,v},pi+1=pi+qid=|u-v|\quad\Longrightarrow\quad d\to\max\{u,v\},\qquad p_{i+1}=p_i+q_i
详细分析

对底行以外的每个数 d,向其两个子数 u、v 中较大的一个画箭头。由于 d 是二者之差的绝对值,被选中的子数就是 d 加上另一个子数。因此沿任何有向路径,每一步都严格增加一个旁边的数。箭头始终向下,所以它们形成在底行结束的有向路径。