『◯と●の帰納法』

最近、数学的帰納法の新しい（と思われる）応用の証明法について知見を得ました。具体例を挙げて説明します。長いですが、ご容赦ください。
９８年度の某大学の数学の試験でグラフ理論についての問題が史上最難ではないか、と一部で話題になりました。御存知の方も多いと思われますので、詳しい説明は端折りますが、◯と●を頂点として、線でつないでグラフを作っていきます。それには一定のルールが課されます。例えば、◯１個からスタートした場合、それに◯を１個ずつ加えていくのですが、２個以上になったら、数珠繋ぎ状につなぐだけでなく、◯同士の間に挿入することもできるし、垂直に枝状につなぐこともできる。そして、付加した場合は、された◯が●に、挿入した場合は、その両隣の２個の◯が●に変わります。いったん、●に変わっても、そこに再度◯が加わるとまた◯に戻るというルールです。●スタートの場合も、同様に、◯を加えていくと●が◯に、または◯が●に変わるというものです。
そこで、◯のみが直線状に、つまり鎖のようにずっと並ぶグラフが形成される条件として、頂点の個数nが3kまたは3k+1が必要十分条件であることを証明せよ、というのが問題として提示されます。（実際は、必要十分条件は何か、ということですが、内容としてはこうなります）
3k+2で◯オンリーになるためには、●スタートにする必要があるということで、◯スタートの場合、途中から、●スタートと同じパターンで○が並ぶことはない（二つのスタートのパターンが交わることはない）となることを証明することになります。
それで、証明なのですが、まず、◯スタートで数個、数十個実際にやってみて、上記の条件が成り立っていることを確認。次に、個数n=kで、どんなパターンで頂点が並んでいても条件が成り立っていると仮定し、しかし、n=k+1にする、つまり◯１個を加えると●スタートのパターンになってしまう、即ち、◯スタートと●スタートのパターンが交わってしまった、またはそんな状況があり得るとします。
そこで、そのグラフの適当なところから◯１個を外します。当然、その◯がつながっていた頂点の色は変わります（１つ前の色に戻る）が、nがk+1からkに戻るわけですから、また◯スタートのみのパターンに戻ることになる。そこで、再度、◯を戻すとまた●パターンと共通の並び方になるとなりますが、外す◯は適当に任意でよいから、これは、どんな◯の挿入や付加を行っても、両パターンが交わることを意味する。これが可能になるためには、n=kの段階で、すでに◯スタートと●スタートのパターンが交わっていなければならない。しかし、それは仮定に反するから、n＝k+１でも条件は成り立っているとせねばならない。よって、◯スタートの場合、任意のnで◯スタートと●スタートのパターンが交わることはないとなる、というものです。
非常に長々と書いてしまいましたが、要点は、この証明が正しいかどうかではないのです。
要は、こんな帰納法の応用が証明方法として通用するのだろうか、ということが疑問なのです。
論理的には（と言っても、論理学に詳しいわけではありませんが）矛盾と言えるほどの難点は見つからないのですが、帰納法とは普通、n=kのとき成り立つと仮定し、k+1のときも成り立つことを示して、一般のnで成り立つことを証明する方法でしょう？しかし、ここではn=k+1のとき、成り立たないとすると、n=kで成り立つとした仮定に反するという背理法的な使い方をしているし、一度k+1からkに戻ることもやっている。逆行帰納法とでもいうべきやり方は確か、一般の相加相乗平均の証明でも使われていますが、今回のような使い方はどうなのか？
疑問です。

No.2 回答者： puyo3155 回答日時： 2023/04/19 21:32

前半は正直、何を言っているのかわからないので、後半だけ。

＞n=kのとき成り立つと仮定し、k+1のときも成り立つことを示して、一般のnで成り立つことを証明する方法でしょう？

違いますよ。

n=kのとき成り立つと仮定し、k+1のときも成り立つことを示し、n=1で、実際成り立つことから、全部のnについて成り立つとする。

手法です。なので

＞しかし、ここではn=k+1のとき、成り立たないとすると、n=kで成り立つとした仮定に反するという背理法的な使い方をしているし、一度k+1からkに戻ることもやっている。逆行帰納法とでもいうべきやり方は確か、一般の相加相乗平均の証明でも使われていますが、今回のような使い方はどうなのか？

の意味も、正直よくわかりませんが、数学的帰納法の、ｎ＝１で成り立つことと合わせ技にしてｎ全部で成り立つ道が、このやりかたから全く見えないので、数学的帰納法でもなんでもないように思えます。

No.1 回答者： mimon01 回答日時： 2023/04/19 21:15

数学の素人が発見したと自称する物は、100%18世紀以前に発見されていますので、あなたが書いた内容を読んでいません。

過去の文献を調査してください。