FC2ブログ

98年後期数学問3(2)

証明のミスに気づいてブレイクダンスしてる

問題
98koukitoi3_1.gif
98koukitoi3_2.gif
98koukitoi3_3.gif

オセロのコンポーネントがあるか分かりやすい。
要は端に白のコマ置いてその隣をひっくり返すか、コマとコマの間に白のコマ置いてその両脇をひっくり返すかの操作をするということ。

解けたら小学生並みの感想を復活させよう。自分で証明のミスを見つけるのの難しいことよ。
予備校が難しい方法で難しい概念が必要な模範解答を作成→難問と評判になる→難問と聞いて解く前に諦める→模範解答を見る→模範解答で使ってる概念が理解できない→神格化される
ってルートを辿ってる気がするんだよなぁ。ネットに落ちてる解答は見ても正直意味わからん。

単に対偶の問題だし出題者の意図もそれな気がするんだよなぁ。
と思ってた時期が私にもありました



解答に当たって
「n個の頂点をもつ図6のような棒状のグラフが可能グラフとなる」ことを「全白可能」と表す。
1回の操作を1手と表す。例:3回操作を行った後を3手先と表す。


解答(というか考えたこと)
常套手段としてまず小さいnで考える。
n=1→できる。自明。
n=2→できない。自明。
n=3→できる。自明。
n=4,6→コンポーネントを使って少し試行すればできる。コンポーネントなしでも簡単。
n=5→少し大変だけど、n=5で全白になる1手前の状態3通り(●○○○、●●○○、○●●○)を書き出し、n=3で可能な状態3通り(○○○、●○○、○●●)を書きだすと、n=3からn=4への手がないことが分かる。
で、ここからn=3m+2だとダメなんじゃないかなーと考えられる。
よって、「n=3m,n=3m+1の場合全白可能」「n=3m+2の場合全白不可能」を示すことを考える。
ここまでは手を動かすだけで、次の1歩に10分くらいヘドバンしてた気がする。

「n=3m+2でダメということは3手先に何か意味があるのでは?具体的にはn=lで全白可能ならn=l+3で全白可能なのでは?」
と閃いて3手先を考えてみたところうまくいった。
n=lで全白の時、
l:○○…○
l+1:○○…●○(右端に○を挿入)
l+2:○○…●●○(右端に○を挿入)
l+3:○○…○○○○(右から3番目に○を挿入)
という手順を踏むことによってできる。
「n=1,3で全白可能」と「n=lで全白可能ならn=l+3でも全白可能」より、数学的帰納法を使って、
「n=3m,n=3m+1の場合全白可能」が示せる。あとは「n=3m+2の場合全白不可能」の方。
ここでまた詰まって次の1歩のために10分くらいブレイクダンスしてた気がする。

今度は閃きではなく論理で。
「n=2で全白不可能である。」が与えられてるので、「n=lで全白不可能ならばn=l+3で全白不可能である。」
を示せば、「n=3m+2の場合全白不可能」が示せる。
これの対偶を取って、
「n=l+3で全白可能ならn=lで全白可能である。」
を示せば良い。
これは↑のl→l+3を逆にたどればよい。
(ここに証明のミス。これはn=lで全白可能→n=l+3で全白可能のルートを示しただけであり、「n=lでは全白可能ではないが、3手でうまく●をひっくり返して全白可能になる」という可能性を考えていない。逆にたどるだけでは対偶を示すのに不十分。)
示せた。よって「n=3m+2の場合全白不可能」が示された。
(m=3n+2を満たすmのどれか1つでも全白可能ならそのmから3ずつ引いて行って最終的にm=2になっても全白可能ということになる。しかし、m=2では全白不可能なので矛盾する。よってm=3n+2を満たすmは全て全白不可能である。)

以上より「n=3m,n=3m+1の場合全白可能」「n=3m+2の場合全白不可能」が示された。
よって求める条件は「n=3mまたは3m+1(mは0以上の整数)」である。
証明終了。


↑の証明にはミスがあるので別のやり方で考える。
mod3で考える。○○○=nullである。あらゆる状態に対して、全白の状態に操作するために2個以上ある●を1個以下にすることを考ると、
●●=○○○=null
●○●=●●○○=○○
●○○●=●○●○○=○○○○=○
●○○○●=●●=null
……
となる。
この処理を続けていき、●の数を1以下にすると、全ての状態は
null、○、●、○●、○○●、○●○、○○●○、○○●○○のいずれかに分類できる。
さらに
○●=null
○○●=○○○○=○
○●○=○○○●=●
となることから
null、○、●に分類できる。●=○○なので、null、○、○○に分類できる。
null、○、○○へ操作1or2を行うと、null→○、○→○●=null、○○→○●○=○○or●○●=○○となるため、いくら操作を行っても、○ and nullと○○は隔絶されている。
このうち初期条件によりnull、○のみが許容されている。
ここで、(a)○○○⇒nullの妥当性、(b)…●●…→●…………●→○○…………○○と、●●を外側から白にするする手順によってこの分類が崩れないことを示す必要がある。
(a)は○○○が操作に介入する場合、●○○○●→●●○○○○○○のように、手数を3n手増やす。よってmod3の世界ではnullと扱って良い。操作に介入しない場合はmod3で考えているため○○○=nullとして扱って良い。
(b)は(○×n)●●(○×m)とし、m+n(mod3)を考える。外側から白にするために必要な手数はm+n+2なので、(○×n)●●(○×m)=(○×2(m+n+2))である。m+n=0の場合右辺=○、m+n=1の場合右辺=null、m+n=2の場合右辺=○○となる。これは●●を内側から白にする場合と同じである。よって、●を○にするのに内側から変えるのと外側から変えるので場合分けしなくて良い。

こんな感じでいけるか。
・mod3で考える
・●を○に変える操作をしていく
・(mod3で考えるため)○○○=nullとする
・○ or nullに分類される状態にどういう操作をしても○ or nullに分類される。○○の方も然り同じ。
といったところ。
結構ややこしいゾ。クッソ難しい整数問題やクッソ複雑な計算がない分まだマシだと思うんだけどな。


というわけで、
・n=1~6であたりをつける
・3手先を考える
・対偶をとる
・3手前を考える
の手順で示せてしまった。保存量とか群論とか知らない子です。
クッソ難問なんでこれがただの勘違いで証明不十分の可能性もあるって言うかその場合に指摘してもらうために書いたわけなんですが、これでいいなら対偶以外数学使わずに解いてるんですよね、これ。

感想
・題材がオセロっぽいし、「3手先」って概念が出てくるしボドゲっぽいなぁと思いました(小並感)。
・ゲーマーだから「3手先」を使った解法思いついたって話なのかもしれないけど、少なくともネットに落ちてる解法よりは高校生っぽいし出題者の想定解に近いと思うんですよ。
・「対偶使って必要十分示す問題が最難ってのが分からない。適当に調べただけでも94東工大前期問4とか、これより遥かに難しい問題あると思うんですが。」って思いました(小並感)。
・「大学レベルの数学使って解くとクッソ難しいけど、オセロみたいに考えると対偶とるだけで簡単に解けるよ」って問題だとしたら数学の問題なのに数学使わない方が簡単に解けるわけで、大学レベルの数学知ってると逆に足枷になりかねんわけで皮肉きいてる。
・ただし受験生当時はドミニオンもアグリコラもスペースアラートも知らないくらいボドゲやってなかったし、対偶とるとか意識してなかったしで、この解法を思いつけた可能性は非常に低いと言わざるを得ない。
とか思ってた時期が私にもありました。



補足
以下にネットで見つけた解答例2つを上げておきます。両方とも大学で挫折した数学力じゃ理解できませんでした。
Marriage Theorem 新居(http://d.hatena.ne.jp/MarriageTheorem/20100324/1269362813)
東大カリスマ塾長浜田一志公式ブログ(http://ameblo.jp/miraclemaster/entry-10876823332.html)
スポンサーサイト



コメントの投稿

非公開コメント

プロフィール

やおや

Author:やおや
苦痛の存在しない、平静な心の生活

最新記事
最新コメント
月別アーカイブ
カテゴリ
検索フォーム