■

 やっぱC苦手だなあ（現役時代に他に得意なものもなかったわけですが）

難易度はとりあえず10段階で描こうと思います。最初は多分ガバガバ。

2018SLP C1

https://www.imo-official.org/problems/IMO2018SL.pdf

概要

nを3以上の整数とする。2*n個の正整数からなる集合Sであって、以下を満たすものが存在することを示せ：

任意のm=2,...,nに対してSの部分集合T_mであってT_mがm個の元からなり、T_mの元の総和がSの総和の半分になるものが存在する。

証明

S={1,1,1,1,2,2,...,2^(n-2),2^(n-2)}とする。このとき

T_m={2^(n-2),...,2^(n-m),2^(n-m)}ととればSが条件を満たすとわかる。

→解説を見たらどうやらdistinctという条件がつくらしい。ちゃんと書いて。（Setでそういう意味なのか？)

distinctでも構成の際の発想はおなじで、T_mの最後尾の元を二つの元に分解してT_(m+1)を構成する感じ。

(1,2,4-1,4,...,2^(n-1)-1,2^(n-1),2^n-1,x} (x=1項から2*n-4項までの和)

x=2^n-n-2となる。nがある程度大きいと2^(n-1)>n-1なのでxは2^(n-1)よりも大きくなり、既に存在する元と一致しない。n=3の時のみ、{1,2,3,4,7,3}となり、不適切なので以下のように構成する。

{1,2,3,4,5,9}(T_2={9,3},T_3={9,1,2})

感想

構成ゲー。後半が少々面倒だが、これは奇数項目をうまく大きくとればすぐに示せる。実際解説では３ベキを上手く使っていた。

後半部分はおいといて意外と競プロの役に立つんじゃないか？

難易度1

2018SLP C2(IMO2018 Problem 4)

概要

AさんとBさんが20*20のチェスボード上でゲームをしている。

Aさんが黒のナイトを、今までにおいた黒のナイトを攻撃しないように（＝距離√5はNG）空のマスにおき、Bさんは白のナイトを空のマスにおく。これを繰り返し、どちらかが置けなくなったら終了する。

Bさんの行動によらずAさんが少なくともK個の黒ナイトを置くことができるようなKの最大値を求めよ。

証明

K=100が最大値である。

まず、チェスボードの通り市松模様に塗る。同じ色同士は距離√5にならないのでAさんは同じ色に置き続ければ少なくとも20*20/4=100個おける。

K<=100を示す。

（Aさんがコマをおくと置けなくなる場所が0個以上発生するが、Bさんがうまく次の一手を塞ぐようにすると四個の組ごとに潰せる、と言ったことを示したい）

4*4のマス目に以下のように番号づけ（塗り分け）を行う。

1 2 3 4

3 4 1 2

2 1 4 3

4 3 2 1

Aさんがどこかに一つナイトを置くと同じ番号内の二つにAさんがナイトを置けなくなる。

残った一つにBさんがナイトを置けば、常に４つ以上Aさんがナイトをおけるマス目の候補が消える。20*20を4*4のマスに分解して上記の議論を行うことで、K<=100となる。

感想

競プロにもありそうっちゃありそうだけど証明の方が難しいタイプだから微妙か。もしくはインタラクティブ？

証明は解説と同様の手法だったが、他にも塗り分けはありそう。なぜかK=100の構成にとても苦戦した。

IMOの4番にしては難しい気がする。Shortlist上の問題文とIMOでの問題文で雰囲気が変わってておもしろい。チェスのくだりがなくなって問題は分かりやすいけど解くのは難しくなってるような。しかしちゃんとわかりやすくreviseしてるんですね。

難易度4