１番についての質問ですが、直接証明で証明することは出来ましたが、S_i != S_j の時に除数の違いによるkの算出方法で条件分岐が多く証明が長くなりすぎてしまいます。対偶法や背理法も考えてみましたが、否定の処理で仮定がよくわからなくなってしまいます。
条件分岐を少なくする方法（剰余をどうまとめるか）、または対偶法や背理法での正しい仮定を教えてください
|
No.72455 - 2021/01/29(Fri) 05:43:56
| ☆ Re: 剰余 / ast | | | # いくつかtypoが見られるのは, これ自分で打ち込んで何かで出力したものってこと?
## たとえば lt と le の混同 (後者は等号付きの判定を別で用意したとか?)
## ほかにもたとえば io(S) の戻り値は boolean だから 6 行目 "=" のあとは "T iff" が入る?
# もし手打ちしたなら, 掲示板に直接テキスト入力してもらった方がやり取りの際の引用など考えると
# 利便性の面でいろいろありがたいのだけど (画像は画像で意味はあるとは思うけど)
きちんと書いてみてはいないが, S' は 1,0,3,0 の繰り返しなのだから, 4項ごとにブロックに区切って (高校数学式に言うと群数列とかいうやつ), i も j も mod 4 で考えれば k は j+(4-j mod 4)+(i mod 4) くらい (でいいかな?) をとればイケるのでは?
# 想定している方法は, (i の属するのがどのブロックでも) i番目の項の値 x は 1,0,3,0 のどれかなので,
# 意味があるのは i がそのブロックの頭から何個目かだけ.
# 同様に (j が何番目のブロックにあっても) 1,2,3,4 のうち適当な数を足して
# 次のブロックの先頭を検出すれば, そこから i 番目の項と同じ値 x は必ず i mod 4 項先にある.
この方法も十分直截的な証明だと思うし, 質問者さんの言ってる「直接証明」ってのがどういうものかよくわからないからアレだが……
# まあ, 4 で割って 2 あまるのと 4 で割り切れるのとどっちかはサボれる気がするし,
# また j<i のときはややこしいこと考えなくても k=i で十分だから, 結局は i=1,2,3,4 だけ調べても
# この場合は一般性を失わないということでいいと思うけど.
|
No.72462 - 2021/01/29(Fri) 09:42:46 |
|
