|
uchinyan |
|
#26134
＞証明としては、これ以外のループがないことを示さないといけないんだけど、今は時間がないし、難しいのかな．．．？ あは、アホみたいに簡単でした。要するに、 すべての自然数 n は、題意の操作によって、3 を含むループ又は 11 を含むループに入る。 ことを示せばOKです。#26134で既に証明は終わっているといってもいいですが、 ちゃんとした証明は、例えば、数学的帰納法を使って次のようにやればいいでしょう。 まず、n が偶数の場合、奇数になるまで 2 で割ることを繰り返すことによってループが生じることはなく、奇数の場合に帰着します。 n が奇数の場合、n <= 11 のときは、3 を含むループ又は 11 を含むループに入っているので、明らか。 n >= 13 の場合、今、n-2 以下の奇数で成立すると仮定します。すると、n-1 は偶数なので、この仮定は n-1 以下で成立するとしてOKです。 すると、奇数の場合の操作 n+11 で偶数になり (n+11)/2 となりますが、n >= 13 では (n+11)/2 < n なので、 帰納法の仮定によって、(n+1)/2 は、3 を含むループ又は 11 を含むループに入ります。 n -> n+11 -> (n+11)/2 ではループは生じないので、結局、n も3 を含むループ又は 11 を含むループに入ります。 これで、証明できました。 なお、有名なコラッツ予想を思い出しました。 n 奇数：n -> 3n+1, n 偶数：n -> n/2 を繰り返すと、すべて、1 になる。 この場合は、(3n+1)/2 = n + (n+1)/2 なので、単純に減少することはなく、格段に難しくなります。 今回は、奇数の場合の n の係数が 1 なのがポイントですね。 |
|
ネコの住む家
11月10日（木） 10:57:49
MAIL:uchi@sco.bekkoame.ne.jp 26136 |