SLP 2017 Cうめ その2
SLP 2017 C4 (IMO 2017 Problem 5)
概要
Nを2以上の整数とする。互いに背の高さが異なるN(N+1)人の人が一列に並んでいる。N(N+1)がどのように並んでいても、ここからN(N-1)人退場して残った2N人について以下が成立するようにできることを示せ。
(2N人の中で)2k-1番背の高い人と2k番目に背の高い人が隣り合う。(k=1~N)
証明
N(N+1)人を最初からN+1人ずつに分ける。各グループをG_1~G_Nと名前をつける。
ここで、より強く以下の条件を付加して示す。
条件:選択する2N人は各グループから二人ずつ選択しなくてはならない。
帰納法を用いる。
N=2の時、身長の高い3人のうち2人が属する方のグループで該当する2人を選択し、残ったグループには身長の低い人が2人以上いるので、そこから2人選択すれば良い。
N>2の時、身長の一番高い人から順に属するグループを調べていき、初めて所属グループが被った人のペアを考え、それぞれa番目,b番目(b>a)に身長が高いとする。(それぞれAさん、Bさんと呼ぶ）
この2人を選び、Bさんよりも身長の高い人および選んだ2人の所属グループに属する人を全員退場させる。さらに、この退場において退場者が1人もいないグループがある場合、グループ内で一番背の高い人を退場させる。
今、AさんとBさんの選び方から、この選び方で各グループからはちょうどひとりずつ退場している状態であるため、N人のグループがN-1個あることになる。また、残った人は全員Bさんよりも身長が低いことになるため、帰納法により示される。
