AMC
22日目を担当します. どの方の記事も面白かったのでそれに見合うだけの記事になるよう頑張ります!
12/21
https://note.com/rankturnip/n/n4d79241fbbd0
いくつか案があったのですが整数じゃない単発記事にしました. 競技数学の特に難しめのC分野でよく使える証明方法の紹介です. Constructive induction(構成的帰納法)と勝手に名付けましたがもしかしたら既に別の名前がついているかもしれないです.
Constructive inductionとは?
その名の通り構成をしながら帰納法を回すという証明方法です. まずは早速例題を見てみましょう.
とする. 縦マス横マスのうちいくつかのマスを選びつずつ石を置く. どのマスにも石が高々つしか置けないとき, 最大で何個の石をおけるか.
この問題を愚直に帰納法で解こうとするとあまり上手く行きません. というのも, 一番右の列の石の置き方によってそれより左の部分(帰納法の仮定を用いたい部分)に制限がかかってしまうからです. (奇数のときも左上と右下を考えればだと分かりますが, 多分気のせいです.)
このようなとき, 実は次の方法で帰納法を回すことができます.
- 問題の主張に「最大値(最小値)を与える構成は〇〇だけである」という主張を加える.
- 上の命題を帰納法で示すが, 最大値を求めるのは簡単に行くことが多い.
- 構成の一意性(意性)を言う. 多くの場合は帰納法の仮定の構成を用いない場合の矛盾を言い, 構成を用いる場合のでの構成を全てあげることで上手くいく.
実際にこの手順で例題を解いてみましょう
1. 問題の主張に構成を追加する.
この問題の場合, の場合は行目と行目にすべて置いた場合, の場合はそれに加えて列目と列目にすべて置いた場合が構成になりそうです. これを加えます. この命題を☆とおきます. のときの成立も確認しておきましょう.
2. 強くした帰納法の仮定を用いて最大値を求める
のときに☆が成立しているとし, のときを考えます(). 個の構成は行目と行目に置けばよいので, 個以上置けないことを示します.
左列は帰納法の仮定から最大で個しか置けず, 一番右の列は高々個しか置けないので, 個置くにはそれぞれ最大限置く必要があります. 実はこの時点で, 帰納法の仮定に構成を列挙していたことから全部のマスの埋め方が完全に決まってしまうのです. ここで, 帰納法の仮定であった構成を思い出すと...
右列で条件に反することが分かります. に対して最大値はと分かりました!
3. 構成の一意性(意性)を言う
これで証明が完成すればハッピーなのですがそううまくいくはずはありません. 帰納法の仮定に構成の一意性を加えた以上でも構成の一意性を言う必要があります. 多くの場合の"個の部分"での構成を用いるかで場合分けをし, 用いない場合矛盾を言う流れになります.
さて, 今からまでの仮定がある状況での構成を考えましょう.
左列をの構成にしない場合
左列では高々個しか置けないため, 一番右の列に個置く必要があります. このとき, 右列には置けないため, の場合は全体で高々個しか置けません(ここではの仮定を用いています). の場合は列目と列目に置く構成があります.
左列をの構成にする場合
一番右の列に個置く必要がありますね. の構成を実際にしてみると条件を満たすのは右上と右下の箇所に置くものだけが条件を満たすと分かります. また, の場合は左列の構成が通りありますが, 上つと下つ置いた方のみ適することも確認できます.
の場合の考え方
なんとなく証明の流れはつかめましたでしょうか?Constructive inductionは, 構成が単純, 少ない, または帰納的に構成できる(言い換えるとの状況がの状況を"含んでいる")という条件下で絶大な威力を発揮します. 帰納的構成→構成的帰納法というイメージです.
この後SLP2020→SLP2021(春合宿)の順でネタバレを含みます!!!!!!!!!!
例1
Constructive inductionが使える問題を問紹介します. いずれもIMO2番級相当(主観)の問題です.
SLP2020C4
をフィボナッチ数列とし, を整数とする. どのに対してもあるが存在してとなるような, 整数からなる集合の要素数の最小値を求めよ.
Constructive inductionを使って解いてみましょう. 解説は常体で書きます.
0. 準備
言葉とか.
- の元を小さい順にとし, とする(差だけが本質的).
- 実験すると上記のを固定したときに条件を満たすが存在する最大のはであると考えられる.
- さらにの構成はのとき, の構成ができているときの構成は「またはをとして残りの部分にの構成を埋め込む」だけっぽそう. かなりシビアだし.
- 上記の状態をハッピーと呼ぶことにする.
- 問題の条件はを連続するの合計で書けることと言い換えられる. そのような方法が複数通りあった場合でも適当に通り選び, がのそれで用いられている場合, はの構成要素であるということにする.
1. 問題の主張を強める
問題を構成を追加した以下のように書き換える. また, 集合の要素数で帰納法を回した方が回りやすそうなのでその部分も書き換える.
集合の要素数がのとき, 条件を満たすが存在する最大のはである. かつ, の構成はハッピーなものだけである.
のときは明らかであることに注意する.
2. 最大値を求める構成がハッピーなものだけであることを示す
今回はまとめて考えたほうが分かりやすかったのでまとめて考える. の場合の主張を仮定しての主張を示そう. ハッピーならなので最大値は以上である.
ここで少し変わった場合分けをする.
1. すべてのについてあるが存在してがの構成要素であるとき
たちの総和は高々である(演習:なぜ?). しかし, この状況下ではを表すことができないためが最大値をとることはない.
2. あるが存在して任意のについてがの構成要素でないとき
そのようなものを一つ選び, そこを消してたちを添え字の小さいほうから添え字を詰めてを作ることで, 帰納法の仮定が使えるようになる. 今, 個のたちでからまで表現できているのでこれら個はハッピーであることが分かる. さらに, ハッピーであるものの構成からであることが分かる(そうでないとを表現している""が途中で分断されてしまう). 今, 対称性よりの場合を考えると, が最大値を取る場合はよりはのいずれの構成要素でもあるので,
がどちらも成立する. からまではハッピーなのでそれらの総和は, がわかり, 最大値がであること, そのときからもハッピーであることが言えた!
ここから言い換えた命題を示すことができ, そこから元の問題の最小値はだと分かる.
例2
SLP2021A3(2022春P4)
を整数としたとき, の最小値を求めよ. ただし, はからまでの並べ替えである.
0. 準備
- まずは最小値の予想. のとき, の構成でが作れることが分かる. 最適っぽい構成なのでこれが最小っぽそう.
- しかも最小値を取る構成は多分これだけな気がする.
- 上の構成を-ハッピーと呼ぶことにする.
- 以外以外のときはのときの最適っぽさからおそらくになりそう.
- のときをConstructive inductionで示せそう.
1. 問題の主張を強める
の場合をConstructive inductionで示す.
問題に構成を追加して
を整数としたとき, の最小値はであることを示せ. さらに, 最小値を与える構成は-ハッピーなものに限ることを示せ. ただし, はからまでの並べ替えである.
とする. のときは明らかである.
2. 最小値を求める
での主張を仮定してでの最小値がであることを示そう. -ハッピーならなので最小値はそれ以下である.
1. からまでが-ハッピーでないとき
からまでのなかで番目に小さいものの値をで置きなおす操作「最適化」を行うことを考える. 最適化によってどのも増加しないので, も増加しない. さらに, -ハッピーでない組を最適化したのち-ハッピーになった場合, -ハッピーの構成から, 最適化する前の組に対してのは以上であることがわかる.
いま, 最適化をしたのち仮定の対偶をもちいることでなので不適.
2. からまでが-ハッピーであるとき
なるを考えれば全体で和は以上なのでok.
3. 構成の一意性を言う
のときの最小値を与えるものが-ハッピーのみであることを示そう.
1. からまでが-ハッピーでないとき
仮定の対偶からなのでとなる必要がある. 特に, からまでのどこかにが登場する必要がある.
ここで, からまでに最適化を行うことを考える. 最適化したあと-ハッピーかどうかで場合分けをする.
最適化前になるについて最適化前と最適化後のの差分を考えると以上減少している(-ハッピーのときはどのもかなので, それぞれについて考えればok). 従って, となり不適.
最適化後はどのも以下であることに注意すれば, 最適化前になるについて最適化前と最適化後のの差分を考えると以上減少している. また, 仮定の対偶より最適化後について なので最適化前はとなりこちらも不適.
2. からまでが-ハッピーであるとき
なのでとなる必要がある. いま, はになり得ないのでがで他はすべてであることが分かる. ここから, はとなるほかなく, 以降同様にがいずれもであることが分かる. 最後に残ったがとなり, このときたしかに-ハッピーである.
これでConstructive inductionが完成した. 最後に以外の形を示せば元の問題を解ける.
4. がの形以外の場合
以下の最大のべきをとする. 最小値がであることを示す.
構成はからまでは-ハッピーでそれ以降はとすればok.
評価はからまでが-ハッピーかどうかで場合分けする.
1. からまでが-ハッピーでないとき
最適化→構成の一意性の対偶よりなのでok
2. からまでが-ハッピーであるとき
なるを考えることで全体ではなのでok
以外パートはConstructive inductionを使用していないので構成の一意性を示す必要はありません(実際一意でない).
以上より最小値はである.
最小値を求めるのと構成の一意性を同時に示しても手間はあまり変わらないです.
まとめ
今回は強力な帰納法, Constructive inductionを紹介しました. 実践では上で見たようにConstructive induction+もう一工夫, というようになることが多いです. 使える状況がやや特殊なのと, 通常の方法に比べ手数が多くなるという欠点はありますが, うまく回ると気持ちいいのでどんどん使っていきましょう!
ところで, この記事を書くとき「構成的」という言葉の英訳をかにするか時間くらい悩んでいました. 明日はじゅんにーさんの記事ということで楽しみです!!