Official

E - Aim High Editorial by PCTprobability


\(N \le 4\) の場合、構築可能です。その手順を説明します。

まず、\(y = -2,-3\) の部分を取りだして \(y=-3\) の駒を以下のように操作します。(数字は \((x,y)\) に存在する駒の個数です。)

操作前

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
操作後
1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

次に、\(y=-1,-2\) の部分で同じような操作を行います。

操作前

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1
操作後
1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

同様に \(y=-1,0\) の部分で行います。

操作前

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 1
操作後
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

さて、これで \(y = 0\) の部分に駒が \(2\) 個ある点を連続して \(14\) 個用意出来ました。これを用いて以下のように操作を行います。まず、\(x=1,2,3,4,5\) の部分の操作の流れを示します。

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 2 2 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
1 1 1 1 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
1 0 1 1 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
1 0 0 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
1 0 0 0 2

\(x=12,11,10,9,8\) の部分も同様に(これを左右反対にした操作)行います。そして最後 \(x=5,6,7,8\) の部分で以下のように操作をします。

0 0 0 0
0 0 0 0
1 0 0 1
0 0 0 0
2 2 2 2
0 0 0 0
0 0 0 0
1 0 0 1
0 2 2 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 1 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

これで \(y = 4\) の点に駒を置くことが出来ました。さて、\(y\) 座標が \(5\) 以上の点に駒を置くことが出来ないことを示します。

ここで、目標の点を \(p = (5,k)\) とします。そして、それぞれの駒のポテンシャルを \(p\) へのマンハッタン距離を \(d\) として \(x^d\) とします。この時、距離が \(d,d+1\) の駒を利用して操作をするとこの \(2\) 個の駒が消えて距離 \(d-1,d,d+1,d+2\) の駒のいずれかが出現します。このときポテンシャルの増減は \(x^{d-1} - x^d - x^{d+1},-x^{d+1},-x^d,x^{d+2} - x^{d+1} - x^d\) となります。ここで、\(x = \frac{\sqrt{5} - 1}{2}\) とすると操作によって盤面全体の駒のポテンシャルの総和が増えないことが確認できます。

最終的に \(p\) に駒が置かれる必要がありますが、\(y\) 座標が非正の点に駒が \(1\) 個ずつ置かれていたとしてもポテンシャルの総和は \(x^5\sum_{i \ge 0} x^i(1 + \sum_{j \ge 1} 2x^j) = x^5\sum_{i \ge 0} x^i(2x + 3) = x^5(x + 2)(2x + 3) = 1\) となります。よって、初期状態のポテンシャルは \(1\) 未満となるので目標は達成不可能です。

posted:
last update: