Constructive induction(仮)の紹介！！
AMC 22日目を担当します. どの方の記事も面白かったのでそれに見合うだけの記事になるよう頑張ります！
12/21$\rightarrow$ https://note.com/rankturnip/n/n4d79241fbbd0
いくつか案があったのですが整数じゃない単発記事にしました. 競技数学の特に難しめのC分野でよく使える証明方法の紹介です. Constructive induction(構成的帰納法)と勝手に名付けましたがもしかしたら既に別の名前がついているかもしれないです.
Constructive inductionとは？
その名の通り構成をしながら帰納法を回すという証明方法です. まずは早速例題を見てみましょう.
$n\ge2$とする. 縦$3$マス横$n$マスのうちいくつかのマスを選び$1$つずつ石を置く. どの$2\times2$マスにも石が高々$2$つしか置けないとき, 最大で何個の石をおけるか.
この問題を愚直に帰納法で解こうとするとあまり上手く行きません. というのも, 一番右の列の石の置き方によってそれより左の部分(帰納法の仮定を用いたい部分)に制限がかかってしまうからです. (奇数のときも左上$2\times (n-1)/2$と右下$2\times2$を考えれば$2n$だと分かりますが, 多分気のせいです.)
このようなとき, 実は次の方法で帰納法を回すことができます.
- 問題の主張に「最大値(最小値)を与える構成は〇〇だけである」という主張を加える.
- 上の命題を帰納法で示すが, 最大値を求めるのは簡単に行くことが多い.
- 構成の一意性($n$意性)を言う. 多くの場合は帰納法の仮定の構成を用いない場合の矛盾を言い, 構成を用いる場合の$n=k+1$での構成を全てあげることで上手くいく.
実際にこの手順で例題を解いてみましょう
1. 問題の主張に構成を追加する.
この問題の場合, $n\neq3$の場合は$1$行目と$3$行目にすべて置いた場合, $n=3$の場合はそれに加えて$1$列目と$3$列目にすべて置いた場合が構成になりそうです. これを加えます. この命題を☆とおきます. $n=2$のときの成立も確認しておきましょう.
2. 強くした帰納法の仮定を用いて最大値を求める
$n=k$のときに☆が成立しているとし, $n=k+1$のときを考えます($k\ge2$). $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$列では高々$2k-1$個しか置けないため, 一番右の列に$3$個置く必要があります. このとき, 右$2$列には置けないため, $k+1\ge4$の場合は全体で高々$2(k-1)+3=2k+1$個しか置けません(ここでは$n=k-1$の仮定を用いています). $k+1=3$の場合は$1$列目と$3$列目に置く構成があります.
左$k$列を$n=k$の構成にする場合
一番右の列に$2$個置く必要がありますね. $n=k$の構成を実際にしてみると条件を満たすのは右上と右下の$2$箇所に置くものだけが条件を満たすと分かります. また, $k+1=4$の場合は左$3$列の構成が$2$通りありますが, 上$3$つと下$3$つ置いた方のみ適することも確認できます.
![!FORMULA[63][694944891][0]の場合の考え方](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2F20221221223040.png?alt=media)
なんとなく証明の流れはつかめましたでしょうか？Constructive inductionは, 構成が単純, 少ない, または帰納的に構成できる(言い換えると$n=k+1$の状況が$n=k$の状況を"含んでいる")という条件下で絶大な威力を発揮します. 帰納的構成→構成的帰納法というイメージです.
この後SLP2020→SLP2021(春合宿)の順でネタバレを含みます！！！！！！！！！！
例1
Constructive inductionが使える問題を$2$問紹介します. いずれもIMO2番級相当(主観)の問題です.
$F_0=0, F_1=1, F_{n+2}=F_n+F_{n+1}$をフィボナッチ数列とし, $n\ge2$を整数とする. どの$k=2,3,\cdots,n$に対してもある$x,y\in S$が存在して$x-y=F_k$となるような, 整数からなる集合$S$の要素数の最小値を求めよ.
Constructive inductionを使って解いてみましょう. 解説は常体で書きます.
0. 準備
言葉とか.
- $S$の元を小さい順に$s_1, s_2, \cdots s_{m+1}$とし, $a_i=s_{i+1}-s_i$とする(差だけが本質的).
- 実験すると上記の$m$を固定したときに条件を満たす$(a_i)$が存在する最大の$n$は$2m$であると考えられる.
- さらに$n=2m$の構成は$m=1$のとき$a_1=1$, $m=k$の構成ができているとき$m=k+1$の構成は「$a_1$または$a_{k+1}$を$F_{2k+1}$として残りの部分に$m=k$の構成を埋め込む」だけっぽそう. かなりシビアだし.
- 上記の状態をハッピーと呼ぶことにする.
- 問題の条件は$F_k$を連続する$a_i$の合計で書けることと言い換えられる. そのような方法が複数通りあった場合でも適当に$1$通り選び, $a_i$が$F_k$のそれで用いられている場合, $a_i$は$F_k$の構成要素であるということにする.
1. 問題の主張を強める
問題を構成を追加した以下のように書き換える. また, 集合の要素数で帰納法を回した方が回りやすそうなのでその部分も書き換える.
集合の要素数が$m+1$のとき, 条件を満たす$(a_i)$が存在する最大の$n$は$2m$である. かつ, $n=2m$の構成はハッピーなものだけである.
$m=1$のときは明らかであることに注意する.
2. 最大値を求める$\cdot$構成がハッピーなものだけであることを示す
今回はまとめて考えたほうが分かりやすかったのでまとめて考える. $m=k$の場合の主張を仮定して$m=k+1$の主張を示そう. ハッピーなら$n=2k+2$なので最大値は$2k+2$以上である$\cdots\star$.
ここで少し変わった場合分けをする.
1. すべての$a_i$についてある$j=2,\cdots,$$2k$が存在して$a_i$が$F_j$の構成要素であるとき
$a_i$たちの総和は高々$F_2+\cdots+F_{2k}=F_{2k+2}-2$である(演習:なぜ？). しかし, この状況下では$F_{2k+2}$を表すことができないため$n$が最大値をとることはない.
2. ある$a_i$が存在して任意の$j=2,\cdots,$$2k$について$a_i$が$F_j$の構成要素でないとき
そのようなもの$a_{i_0}$を一つ選び, そこを消して$a_i$たちを添え字の小さいほうから添え字を詰めて$(b_i)_{i=1}^{k}$を作ることで, 帰納法の仮定が使えるようになる. 今, $k$個の$b_i$たちで$F_2$から$F_{2k}$まで表現できているのでこれら$k$個はハッピーであることが分かる. さらに, ハッピーであるものの構成から$i_0=1, k+1$であることが分かる(そうでないと$F_{2k}$を表現している"$b_1+\cdots+b_k$"が途中で分断されてしまう). 今, 対称性より$i_0=k+1$の場合を考えると, $n$が最大値を取る場合は$\star$より$a_{k+1}$は$F_{2k+1}, F_{2k+2}$のいずれの構成要素でもあるので,
- $a_{k+1}\le F_{2k+1}$
- $a_1+\cdots+a_{k+1}\ge F_{2k+2}$
がどちらも成立する. $a_1$から$a_k$まではハッピーなのでそれらの総和は$F_{2k}$, $a_{k+1}=F_{2k+1}$がわかり, 最大値が$n=2k+2$であること, そのとき$a_1$から$a_{k+1}$もハッピーであることが言えた！
ここから言い換えた命題を示すことができ, そこから元の問題の最小値は$\left\lceil\dfrac{n}2\right\rceil+1$だと分かる.
例2
$n\ge1$を整数としたとき, $\displaystyle\sum^{n}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor$の最小値を求めよ. ただし, $(a_i)_{i=1}^n$は$1$から$n$までの並べ替えである.
0. 準備
- まずは最小値の予想. $n=2^m-1$のとき$1; 3, 2; 7, 4, 5, 6;\cdots;2^m-1, 2^{m-1}, 2^{m-1}+1, 2^{m-2}+2,\cdots, 2^m-2$, の構成で$m$が作れることが分かる. 最適っぽい構成なのでこれが最小っぽそう.
- しかも最小値を取る構成は多分これだけな気がする.
- 上の構成を$m$-ハッピーと呼ぶことにする.
- $2^m-1$以外以外のときは$2^m-1$のときの最適っぽさからおそらく$\lfloor \log_2 n\rfloor+1$になりそう.
- $2^m-1$のときをConstructive inductionで示せそう.
1. 問題の主張を強める
$n=2^m-1$の場合をConstructive inductionで示す.
問題に構成を追加して
$N=2^m-1(m\ge1)$を整数としたとき, $\displaystyle\sum^{N}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor$の最小値は$m$であることを示せ. さらに, 最小値を与える構成は$m$-ハッピーなものに限ることを示せ. ただし, $(a_i)_{i=1}^N$は$1$から$N$までの並べ替えである.
とする. $m=1$のときは明らかである.
2. 最小値を求める
$m=k$での主張を仮定して$m=k+1$での最小値が$k+1$であることを示そう. $k+1$-ハッピーなら$k+1$なので最小値はそれ以下である.
1. $a_1$から$a_{2^k-1}$までが$k$-ハッピーでないとき
$a_1$から$a_{2^k-1}$までのなかで$i$番目に小さいものの値を$i$で置きなおす操作「最適化」を行うことを考える. 最適化によってどの$a_i$も増加しないので, $\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor$も増加しない. さらに, $k$-ハッピーでない組を最適化したのち$k$-ハッピーになった場合, $k$-ハッピーの構成から, 最適化する前の組に対しての$\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor$は$k+1$以上であることがわかる.
いま, 最適化をしたのち仮定の対偶をもちいることで$\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge k+1$なので不適.
2. $a_1$から$a_{2^k-1}$までが$k$-ハッピーであるとき
$a_i=2^{k+1}-1$なる$i$を考えれば全体で和は$k+1$以上なのでok.
3. 構成の一意性を言う
$m=k+1$のときの最小値$k+1$を与えるものが$k+1$-ハッピーのみであることを示そう.
1. $a_1$から$a_{2^k-1}$までが$k$-ハッピーでないとき
仮定の対偶から$\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge k+1$なので$\displaystyle\sum^{N}_{i=2^k}\left\lfloor\frac{a_i}{i}\right\rfloor=0$となる必要がある. 特に, $a_1$から$a_{2^k-1}$までのどこかに$2^{k+1}-1$が登場する必要がある.
ここで, $a_1$から$a_{2^k-1}$までに最適化を行うことを考える. 最適化したあと$k$-ハッピーかどうかで場合分けをする.
- 最適化で$k$-ハッピーになった場合
最適化前に$a_i=2^{k+1}-1$なる$i$について最適化前と最適化後の$\left\lfloor\dfrac{a_i}{i}\right\rfloor$の差分を考えると$2$以上減少している($k$-ハッピーのときはどの$\left\lfloor\dfrac{a_i}{i}\right\rfloor$も$0$か$1$なので, それぞれについて考えればok). 従って, $\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge k+2$となり不適.
- 最適化で$k$-ハッピーにならなかった場合
最適化後はどの$a_i$も$2^k-1$以下であることに注意すれば, 最適化前に$a_i=2^{k+1}-1$なる$i$について最適化前と最適化後の$\left\lfloor\dfrac{a_i}{i}\right\rfloor$の差分を考えると$1$以上減少している. また, 仮定の対偶より最適化後について $\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge k+1$なので最適化前は$\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge k+2$となりこちらも不適.
2. $a_1$から$a_{2^k-1}$までが$k$-ハッピーであるとき
$\displaystyle\sum^{2^k-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor=k$なので$\displaystyle\sum^{N}_{i=2^k}\left\lfloor\frac{a_i}{i}\right\rfloor=1$となる必要がある. いま, $\left\lfloor\dfrac{a_{2^k}}{2^k}\right\rfloor$は$0$になり得ないので$\left\lfloor\dfrac{a_{2^k}}{2^k}\right\rfloor$が$1$で他はすべて$0$であることが分かる. ここから, $a_{2^k+1}$は$2^k$となるほかなく, 以降同様に$a_{2^k+2}, a_{2^k+3},\cdots$がいずれも$a_i=i-1$であることが分かる. 最後に残った$a_{2^k}$が$2^{k+1}-1$となり, このときたしかに$k+1$-ハッピーである.
これでConstructive inductionが完成した. 最後に$2^m-1$以外の形を示せば元の問題を解ける.
4. $n$が$2^m-1$の形以外の場合
$n+1$以下の最大の$2$べきを$2^m$とする. 最小値が$m+1$であることを示す.
構成は$a_1$から$a_{2^m-1}$までは$m$-ハッピーでそれ以降は$(a_{2^m}, a_{2^m+1}, \cdots, a_n)=(n, 2^m, 2^m+1,\cdots,n-1)$とすればok.
評価は$a_1$から$a_{2^m-1}$までが$m$-ハッピーかどうかで場合分けする.
1. $a_1$から$a_{2^m-1}$までが$m$-ハッピーでないとき
最適化→構成の一意性の対偶より$\displaystyle\sum^{2^m-1}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge m+1$なのでok
2. $a_1$から$a_{2^m-1}$までが$m$-ハッピーであるとき
$a_i=n$なる$i(\ge2^m)$を考えることで全体では$\displaystyle\sum^{n}_{i=1}\left\lfloor\frac{a_i}{i}\right\rfloor\ge m+1$なのでok
$2^m-1$以外パートはConstructive inductionを使用していないので構成の一意性を示す必要はありません(実際一意でない).
以上より最小値は$\lfloor \log_2 n\rfloor+1$である.
最小値を求めるのと構成の一意性を同時に示しても手間はあまり変わらないです.
まとめ
今回は強力な帰納法, Constructive inductionを紹介しました. 実践では上で見たようにConstructive induction+もう一工夫, というようになることが多いです. 使える状況がやや特殊なのと, 通常の方法に比べ手数が多くなるという欠点はありますが, うまく回ると気持ちいいのでどんどん使っていきましょう！
ところで, この記事を書くとき「構成的」という言葉の英訳を$Constitutive$か$Constructive$にするか$1$時間くらい悩んでいました. 明日はじゅんにーさんの記事ということで楽しみです！！