MathLabs

第3問

anti-Pascal 三角形とは、最下段の数を除き、各数がその真下にある二つの数の差の絶対値であるような正三角形状の数の配列である。次は 1 から 10 までのすべての整数を含む 4 段の anti-Pascal 三角形である。 42657183109\begin{array}{ccccccccccc} &&&&4&&&&\\ &&&2&&6&&&\\ &5&&7&&1&&&\\ 8&&3&&10&&9 \end{array} 1 から 1+2+⋯+20181+2+\cdots+2018 までのすべての整数を含む 2018 段の anti-Pascal 三角形は存在するか。
ステップ 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 ともう一方の子の和である。したがって有向路では各段で隣の数だけ値が厳密に増加する。矢印は常に下向きなので、有向路は最下段で終わる。