SLP 2017 Cうめ - Ktya’s blog

問題:
https://www.imo-official.org/problems/IMO2017SL.pdf

SLP 2017 C1

概要

二つの辺の長さが奇数である長方形Rを、各辺の長さが整数となる長方形に分割する（分割後の長方形の辺はRのどれかの辺と平行になることを使ってよい）。
この時、分割後の長方形の中で、Rの各辺との距離がすべて奇数もしくはすべて偶数になるものが存在することを示せ。

証明

長方形をA*Bのグリッドだと思い、各マスを長方形Rの一番左上が黒となるように市松模様に塗る。代位の長方形の切断は、
Rを分割した後の長方形のうち、四すみの色の構成について考えると、(黒,白)=(4,0),(2,2),(0,4)のみである（これはビットで考えた時にで考えた時に左上xor左下xor右上xor右下=0となることから従う)
分割後の長方形について、「Rの各辺との距離が全て奇数もしくは全て偶数」であることと「四すみの色が同色」であることは同値である。
これは「（分割後の長方形の）二つの辺の長さが奇数である」という命題を間に挟めばすぐに示される。

分割後の長方形の中で、Rの各辺との距離がすべて奇数もしくはすべて偶数になるものが存在しないと仮定する。
一つ前の同値な命題により、分割後の長方形の中で、四すみの色が同色のものが存在しないと言うことになり、これは分割後の長方形の四すみは全て黒と白が２つずつ存在することになる。
一方、四すみの色の構成が(黒,白)=(2,2)の時、辺のどちらかは偶数なるため、面積は偶数になる。したがって、分割後の長方形は全て面積が偶数になり、それらを足し合わせたRの面積も偶数となる。
しかしRの各辺は奇数なのでRの面積は奇数となるので矛盾。したがって、分割後の長方形の中で、Rの各辺との距離がすべて奇数もしくはすべて偶数になるものが存在する。

感想

塗り分け、分類、言い換え、適切な指標（今回は面積）とよくあるテクをふんだんに使う感じで解ける。多分うまく帰納法を瀬一定してやっても解ける。
競プロ風にするにはプラスアルファの要素が欲しいか。

SLP 2017 C2

概要

nを正整数として、n個の文字a、n個の文字b、n個の文字cからなる長さ3nの文字列をカメレオン文字列と呼ぶことにする。
任意のカメレオン文字列Xに対してあるカメレオン文字列Yであって、XからYに文字列の互換で変形するのに3*(n^2)/2以上のステップがかかるものが存在することを示せ。

証明

(方針としてはある同じ文字を寄せて計算する)
カメレオンXに対して、n個の文字aの左から見た位置を $a_1,\lodts ,a_n$ とおく。また、 $S=\sum a_i$ とおく。
これらを全て左端に寄せるのにかかる操作数は最小で $S-(n+1)n/2$ 、全て右端に寄せるのにかかる操作数は最小で $(3n+1)n-S-(n+1)n/2$ となり、この二つの和は $2n^2$ なので、片方は $n^2$ 以上となる。等号が成立するのは $S=n(3n+1)/2$ の時である。したがって、操作がかかる方に寄せれば $n^2$ 回かかる。残った文字列を同じ方向に寄せるとき、bの座標の和をTとおくと、bを寄せるコストは $T-n(n+1)/2$ 、cを寄せるコストは $n(2n+1)-T-n(n+1)/2$ となるので、先ほど同様に和をとると $n^2$ となるため、どちらかは $n^2/2$ 以上となる。これらを足し合わせて $\frac{3n^2}{2}$ となる。

感想

方針の見当がつきにくい。
証明も少し正確性に欠けるものになっている（転倒数の議論の辺）
近いセッティングの転倒数計算の問題は作れそうだしたくさんありそう。

SLP 2017 C3

概要

9個の箱に数字を書く操作をする。最初にはどの箱にも何も数字が書かれていない。操作は以下のどちらかを選ぶ。
①2ベキを何も書いていない箱に書き込む
②同じ数の書かれている箱のペアに対して、片方を2倍の数にし、もう片方の数字を消す。
この時、1個の箱に2^nが書かれていて残りの箱には何も書かれていない　と言う状態にするのに必要な操作の回数の最大値を求めよ。

証明

後日更新