6

Constructive induction(仮)の紹介!!

1142
0

  AMC 22日目を担当します. どの方の記事も面白かったのでそれに見合うだけの記事になるよう頑張ります!

12/21 https://note.com/rankturnip/n/n4d79241fbbd0

 いくつか案があったのですが整数じゃない単発記事にしました. 競技数学の特に難しめのC分野でよく使える証明方法の紹介です. Constructive induction(構成的帰納法)と勝手に名付けましたがもしかしたら既に別の名前がついているかもしれないです.

Constructive inductionとは?

 その名の通り構成をしながら帰納法を回すという証明方法です. まずは早速例題を見てみましょう.

n2とする. 縦3マス横nマスのうちいくつかのマスを選び1つずつ石を置く. どの2×2マスにも石が高々2つしか置けないとき, 最大で何個の石をおけるか.

 この問題を愚直に帰納法で解こうとするとあまり上手く行きません. というのも, 一番右の列の石の置き方によってそれより左の部分(帰納法の仮定を用いたい部分)に制限がかかってしまうからです. (奇数のときも左上2×(n1)/2と右下2×2を考えれば2nだと分かりますが, 多分気のせいです.)
 このようなとき, 実は次の方法で帰納法を回すことができます.

  1. 問題の主張に「最大値(最小値)を与える構成は〇〇だけである」という主張を加える.
  2. 上の命題を帰納法で示すが, 最大値を求めるのは簡単に行くことが多い.
  3. 構成の一意性(n意性)を言う. 多くの場合は帰納法の仮定の構成を用いない場合の矛盾を言い, 構成を用いる場合のn=k+1での構成を全てあげることで上手くいく.

実際にこの手順で例題を解いてみましょう

1. 問題の主張に構成を追加する.

 この問題の場合, n3の場合は1行目と3行目にすべて置いた場合, n=3の場合はそれに加えて1列目と3列目にすべて置いた場合が構成になりそうです. これを加えます. この命題を☆とおきます. n=2のときの成立も確認しておきましょう.

2. 強くした帰納法の仮定を用いて最大値を求める

 n=kのときに☆が成立しているとし, n=k+1のときを考えます(k2). 2(k+1)個の構成は1行目と3行目に置けばよいので, 2(k+1)+1=2k+3個以上置けないことを示します.
 左k列は帰納法の仮定から最大で2k個しか置けず, 一番右の列は高々3個しか置けないので, 2k+3個置くにはそれぞれ最大限置く必要があります. 実はこの時点で, 帰納法の仮定に構成を列挙していたことから全部のマスの埋め方が完全に決まってしまうのです. ここで, 帰納法の仮定であった構成を思い出すと...
 右2列で条件に反することが分かります. n=k+1に対して最大値は2(k+1)と分かりました!

3. 構成の一意性(n意性)を言う

 これで証明が完成すればハッピーなのですがそううまくいくはずはありません. 帰納法の仮定に構成の一意性を加えた以上n=k+1でも構成の一意性を言う必要があります. 多くの場合n=k+1の"k個の部分"でn=kの構成を用いるかで場合分けをし, 用いない場合矛盾を言う流れになります.
 さて, 今n=2からn=kまでの仮定がある状況でn=k+1の構成を考えましょう.

k列をn=kの構成にしない場合

 左k列では高々2k1個しか置けないため, 一番右の列に3個置く必要があります. このとき, 右2列には置けないため, k+14の場合は全体で高々2(k1)+3=2k+1個しか置けません(ここではn=k1の仮定を用いています). k+1=3の場合は1列目と3列目に置く構成があります.

k列をn=kの構成にする場合

 一番右の列に2個置く必要がありますね. n=kの構成を実際にしてみると条件を満たすのは右上と右下の2箇所に置くものだけが条件を満たすと分かります. また, k+1=4の場合は左3列の構成が2通りありますが, 上3つと下3つ置いた方のみ適することも確認できます.

!FORMULA[63][694944891][0]の場合の考え方 k+1=9の場合の考え方


 なんとなく証明の流れはつかめましたでしょうか?Constructive inductionは, 構成が単純, 少ない, または帰納的に構成できる(言い換えるとn=k+1の状況がn=kの状況を"含んでいる")という条件下で絶大な威力を発揮します. 帰納的構成→構成的帰納法というイメージです.


この後SLP2020→SLP2021(春合宿)の順でネタバレを含みます!!!!!!!!!!

 

例1

 Constructive inductionが使える問題を2問紹介します. いずれもIMO2番級相当(主観)の問題です.

SLP2020C4

F0=0,F1=1,Fn+2=Fn+Fn+1をフィボナッチ数列とし, n2を整数とする. どのk=2,3,,nに対してもあるx,ySが存在してxy=Fkとなるような, 整数からなる集合Sの要素数の最小値を求めよ.

Constructive inductionを使って解いてみましょう. 解説は常体で書きます.

0. 準備

 言葉とか.

  • Sの元を小さい順にs1,s2,sm+1とし, ai=si+1siとする(差だけが本質的).
  • 実験すると上記のmを固定したときに条件を満たす(ai)が存在する最大のn2mであると考えられる.
  • さらにn=2mの構成はm=1のときa1=1, m=kの構成ができているときm=k+1の構成は「a1またはak+1F2k+1として残りの部分にm=kの構成を埋め込む」だけっぽそう. かなりシビアだし.
  • 上記の状態をハッピーと呼ぶことにする.
  • 問題の条件はFkを連続するaiの合計で書けることと言い換えられる. そのような方法が複数通りあった場合でも適当に1通り選び, aiFkのそれで用いられている場合, aiFkの構成要素であるということにする.

1. 問題の主張を強める

 問題を構成を追加した以下のように書き換える. また, 集合の要素数で帰納法を回した方が回りやすそうなのでその部分も書き換える.

 集合の要素数がm+1のとき, 条件を満たす(ai)が存在する最大のn2mである. かつ, n=2mの構成はハッピーなものだけである.

 m=1のときは明らかであることに注意する.

2. 最大値を求める構成がハッピーなものだけであることを示す

 今回はまとめて考えたほうが分かりやすかったのでまとめて考える. m=kの場合の主張を仮定してm=k+1の主張を示そう. ハッピーならn=2k+2なので最大値は2k+2以上である.
 ここで少し変わった場合分けをする.

1. すべてのaiについてあるj=2,,2kが存在してaiFjの構成要素であるとき

 aiたちの総和は高々F2++F2k=F2k+22である(演習:なぜ?). しかし, この状況下ではF2k+2を表すことができないためnが最大値をとることはない.

2. あるaiが存在して任意のj=2,,2kについてaiFjの構成要素でないとき

 そのようなものai0を一つ選び, そこを消してaiたちを添え字の小さいほうから添え字を詰めて(bi)i=1kを作ることで, 帰納法の仮定が使えるようになる. 今, k個のbiたちでF2からF2kまで表現できているのでこれらk個はハッピーであることが分かる. さらに, ハッピーであるものの構成からi0=1,k+1であることが分かる(そうでないとF2kを表現している"b1++bk"が途中で分断されてしまう). 今, 対称性よりi0=k+1の場合を考えると, nが最大値を取る場合はよりak+1F2k+1,F2k+2のいずれの構成要素でもあるので,

  • ak+1F2k+1
  • a1++ak+1F2k+2

がどちらも成立する. a1からakまではハッピーなのでそれらの総和はF2k, ak+1=F2k+1がわかり, 最大値がn=2k+2であること, そのときa1からak+1もハッピーであることが言えた!


 ここから言い換えた命題を示すことができ, そこから元の問題の最小値はn2+1だと分かる.

例2

SLP2021A3(2022春P4)

n1を整数としたとき, i=1naiiの最小値を求めよ. ただし, (ai)i=1n1からnまでの並べ替えである.

0. 準備

  • まずは最小値の予想. n=2m1のとき1;3,2;7,4,5,6;;2m1,2m1,2m1+1,2m2+2,,2m2, の構成でmが作れることが分かる. 最適っぽい構成なのでこれが最小っぽそう.
  • しかも最小値を取る構成は多分これだけな気がする.
  • 上の構成をm-ハッピーと呼ぶことにする.
  • 2m1以外以外のときは2m1のときの最適っぽさからおそらくlog2n+1になりそう.
  • 2m1のときをConstructive inductionで示せそう.

1. 問題の主張を強める

 n=2m1の場合をConstructive inductionで示す.
問題に構成を追加して

N=2m1(m1)を整数としたとき, i=1Naiiの最小値はmであることを示せ. さらに, 最小値を与える構成はm-ハッピーなものに限ることを示せ. ただし, (ai)i=1N1からNまでの並べ替えである.

とする. m=1のときは明らかである.

2. 最小値を求める

 m=kでの主張を仮定してm=k+1での最小値がk+1であることを示そう. k+1-ハッピーならk+1なので最小値はそれ以下である.

1. a1からa2k1までがk-ハッピーでないとき

 a1からa2k1までのなかでi番目に小さいものの値をiで置きなおす操作「最適化」を行うことを考える. 最適化によってどのaiも増加しないので, i=12k1aiiも増加しない. さらに, k-ハッピーでない組を最適化したのちk-ハッピーになった場合, k-ハッピーの構成から, 最適化する前の組に対してのi=12k1aiik+1以上であることがわかる.
 いま, 最適化をしたのち仮定の対偶をもちいることでi=12k1aiik+1なので不適.

2. a1からa2k1までがk-ハッピーであるとき

 ai=2k+11なるiを考えれば全体で和はk+1以上なのでok.

3. 構成の一意性を言う

 m=k+1のときの最小値k+1を与えるものがk+1-ハッピーのみであることを示そう.

1. a1からa2k1までがk-ハッピーでないとき

 仮定の対偶からi=12k1aiik+1なのでi=2kNaii=0となる必要がある. 特に, a1からa2k1までのどこかに2k+11が登場する必要がある.
 ここで, a1からa2k1までに最適化を行うことを考える. 最適化したあとk-ハッピーかどうかで場合分けをする.

  • 最適化でk-ハッピーになった場合

 最適化前にai=2k+11なるiについて最適化前と最適化後のaiiの差分を考えると2以上減少している(k-ハッピーのときはどのaii01なので, それぞれについて考えればok). 従って, i=12k1aiik+2となり不適.

  • 最適化でk-ハッピーにならなかった場合

 最適化後はどのai2k1以下であることに注意すれば, 最適化前にai=2k+11なるiについて最適化前と最適化後のaiiの差分を考えると1以上減少している. また, 仮定の対偶より最適化後について i=12k1aiik+1なので最適化前はi=12k1aiik+2となりこちらも不適.

2. a1からa2k1までがk-ハッピーであるとき

 i=12k1aii=kなのでi=2kNaii=1となる必要がある. いま, a2k2k0になり得ないのでa2k2k1で他はすべて0であることが分かる. ここから, a2k+12kとなるほかなく, 以降同様にa2k+2,a2k+3,がいずれもai=i1であることが分かる. 最後に残ったa2k2k+11となり, このときたしかにk+1-ハッピーである.


 これでConstructive inductionが完成した. 最後に2m1以外の形を示せば元の問題を解ける.

4. n2m1の形以外の場合

 n+1以下の最大の2べきを2mとする. 最小値がm+1であることを示す.
 構成はa1からa2m1まではm-ハッピーでそれ以降は(a2m,a2m+1,,an)=(n,2m,2m+1,,n1)とすればok.
 評価はa1からa2m1までがm-ハッピーかどうかで場合分けする.

1. a1からa2m1までがm-ハッピーでないとき

 最適化→構成の一意性の対偶よりi=12m1aiim+1なのでok

2. a1からa2m1までがm-ハッピーであるとき

 ai=nなるi(2m)を考えることで全体ではi=1naiim+1なのでok

 2m1以外パートはConstructive inductionを使用していないので構成の一意性を示す必要はありません(実際一意でない).


 以上より最小値はlog2n+1である.


 最小値を求めるのと構成の一意性を同時に示しても手間はあまり変わらないです.

まとめ

 今回は強力な帰納法, Constructive inductionを紹介しました. 実践では上で見たようにConstructive induction+もう一工夫, というようになることが多いです. 使える状況がやや特殊なのと, 通常の方法に比べ手数が多くなるという欠点はありますが, うまく回ると気持ちいいのでどんどん使っていきましょう!
 ところで, この記事を書くとき「構成的」という言葉の英訳をConstitutiveConstructiveにするか1時間くらい悩んでいました. 明日はじゅんにーさんの記事ということで楽しみです!!

投稿日:20221221
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

りぼーす
りぼーす
142
30268

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. Constructive inductionとは?
  2. 1. 問題の主張に構成を追加する.
  3. 2. 強くした帰納法の仮定を用いて最大値を求める
  4. 3. 構成の一意性($n$意性)を言う
  5. 例1
  6. 例2
  7. まとめ