SLP Cうめ

SLP

SLP 2018 C4(IMO 2018 Problem 3)

概要

「反パスカル三角形」を、正三角形上に配置された数字であって、隣り合う数の差の絶対値が上の数になっているものと定める。
2018行からなる反パスカル三角形であって1~1+...+2018の全ての数を一回ずつ使う物は存在するか。

証明

題意の反パスカル三角形が構成できると仮定する。
まず、一番上の行の数字をx_1とし、x_iに対してx_(i+1)を「x_iの直下にある数のうち大きい方」と定める。
逆に、x_iに対してx_(i+1)でない方（小さい方）をy_iとする。このとき、x_(i+1)=x_i+y_iとなるので、x_2018=x_1+y_1~y_2017の和　となる。今、x_2018<=1+...+2018で、2018個の異なる数字の和なのでx_1+y_1~y_2017の和>=1+...+2018となる。
したがってx_1,y_1,…y_2017は1~2018の並べ替えになる。
続いて、x_2018,y_2017の書かれていた位置を2018行目の左からk,k+1番目であるとすると、1~k-1を底辺とする正三角形T1と、k+2~2018を底辺とする正三角形T2がとれ、これらは記入された数が全て異なる反パスカル三角形である。T1かT2のどちらかは一辺が1008以上であり、前半と同じ議論をすると、底辺に異なる1008(以上)の和で表せる数bが存在する。一方、1~2018はT1にもT2にも含まれないため、bは（2019~3016の和）以上になることが言える。これは計算すると1+...+2018より大きくなるので矛盾。

感想

迷走しまくって解ける気配がなかったので解説を見た。
上から順にわかる部分を追いかけると比較的ストレートに示せるタイプであった。
解説見るとすごく簡単に見えるが、迷走しやすさが尋常じゃないのがこの問題の特徴っぽい。実際IMOでもあまり解かれなかったらしい。
後半の不等式のガバガバ具合が証明しにくさの一因か。（nの二乗の係数が違うレベル）
この通りの構成ゲーとしては発展しなさそうだけど使う数字の制限を緩めて個数を聞く感じにしたら競プロにもある感じだろうか？