数列の操作による左端の変化
- 1からn(nは2以上の自然数)の数列において、左端の数を逆順にする操作を有限回行うと、必ず左端は1になることを証明します。
- この問題について、鳩ノ巣原理を用いて証明する方法や数学的帰納法を利用する方法を試みましたが、うまくいきませんでした。
- ご教授いただける方がいらっしゃいましたら、解決方法を教えていただきたいです。
- ベストアンサー
例えば、1から8までの整数を一つずつ使った……
この問題を考えて欲しいです！！ 例えば、1から8までの整数を一つずつ使った数列があるとする どんな並び方でも、左から数えて左端の数の分だけ順番を逆にする操作を有限回行うと、必ず左端は1になる たとえば 56712348なら 21765348 12765348 41387652なら 83147652 25674138 52674138 47628138 26748138 62748138 18472638 という風に、必ず左端が1になって、操作は終了する このことは、1からn(nは2以上のしぜんすう)の場合にも同じことがいえ、必ず左端が1になる これを証明しろ という問題です！ いろいろ考えてみたのですが、全然わからないです…… たとえば、1がk番目にある時、 k以上の数が必ず、k番目より前に存在することは、鳩ノ巣原理によって示ます また数学的帰納法とかをつかってアプローチしてみましたが、イマイチ上手く行きません！ わかる方、ご教授お願いします！！
- colocolocololon
- お礼率79% (87/109)
- 数学・算数
- 回答数3
- ありがとう数3
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
＞上限が2^(n-1)になることがわかりません…… 2^(n-1)ではなくて、2^n-1です。 最大値は、すべての桁が一致している場合で、 2^0+2^1+2^2+・・・+2^(n-1)＝2^n-1
その他の回答 (2)
- nag0720
- ベストアンサー率58% (1093/1860)
数列から整数への対応を次のように定義する。 i番目がiであるとき、2^(i-1)として、すべての位置の値を合計する。 例えば、 41387652は、3番目と6番目が一致しているので、2^2+2^5=36 83147652は、4番目と6番目が一致しているので、2^3+2^5=40 25674138は、8番目だけが一致しているので、2^7=128 52674138は、2番目と8番目が一致しているので、2^1+2^8=130 始めの数列に対応する整数をa[0]、 k回操作にした数列に対応する整数をa[k]として新たな数列a[0],a[1],a[2],・・・・,a[m]を作ると、 a[m]の下限は0、上限は2^n-1である。 数列a[m]は単調増加数列で、上限があることから、数列a[m]の項数は有限となる。 よって、逆順にする操作も有限となる。
お礼
上限が2^(n-1)になることがわかりません…… Σじゃなくてですか？ あと、なぜ単調増加になるのでしょう？
補足
単調増加になる理由はわかりました！！ 二進法みたいなもんですね！！
- nacci2014
- ベストアンサー率35% (200/569)
数学的な証明はわかりませんが 必ず１になる理屈としては１が 左側にきた時にだけ番号交換がないからおしまいは 必ず１であるってことじゃない その他の数学は 必ず数字の入れ替えが発生しますので
お礼
それはそうですが、もしかしたら循環することも考えられます 要するに、必ず有限回の操作で操作が終わるとは限らなじゃないですか 概念的にはその説明で、題意が真であることはわかりますが、それが数学的な説明になりえますでしょうか？
関連するQ&A
- 整数の選択
アルゴリズムに関する質問です． n個の相異なる整数が配列 A[1..n] に格納されていて，その配列の中からk番目に小さい整数を選ぶ問題のアルゴリズムを考えています．kは 1<=k<=n を満たす自然数であり，この選択問題は O(n) で解けるものです． ヒープを使ったりして考えたのですがうまくいきません．どなたかこのアルゴリズムを教えてください．よろしくお願いします．
- ベストアンサー
- その他（プログラミング・開発）
- Ｐ(０), Ｐ(１),Ｐ(２),・・・, Ｐ(ｎ)が整数ならば、全ての整数ｋに対してＰ(ｋ)は整数
『ｎを自然数, Ｐ(ｘ)をｎ次の多項式とする。Ｐ(０), Ｐ(１),Ｐ(２),・・・, Ｐ(ｎ)が整数ならば、全ての整数ｋに対してＰ(ｋ)は整数であることを証明せよ。』 数学的帰納法で解けるらしいのですが、分かりません。どなたか教えてください。
- ベストアンサー
- 数学・算数
- 数学の問題 私の答え 合ってますか？
数列（an ）初項a1 から第 ｎ項までの和をSnとあらわす。 この数列が、 （ｎ＋２ ）ａｎ＝３Sn を満たす。 数列 ａｎの初項ａ１が整数である時、Snは、整数であることを示せ。 この問題で、 （ｎ＋２ ）ａ(ｎ)＝３S(n) （ｎ＋１ ）ａ(ｎ-1)＝３S(ｎ-1) n≧２ からａｎを求めて、 (n＋２)ａｎ =3Sn (n+1)ａｎ-1=3Sn-1(ｎ≧２） これから a(n)-a(n-1)=3a(n) a(n)=-1/2a(n-1) 以下 数学的帰納法を用いて n=2 a(2)=-1/2a(1) 整数 n=k a(k) =-1/2a(k-1) コレを整数と仮定すると n=k+1 a(k+1)=-1/2a(k) a(k)が整数なので、a(k+1)も整数 数学的帰納法により すべての自然数で、ａ(ｎ)は、整数。 よって、 Sn＝Σａｋ＝ａ１（１－（ー１/２）＾ｎ ）/１－（－１/２） コレで、Snも整数であることが示せた これは、正解でしょうか？？？ お願いします。
- ベストアンサー
- 数学・算数
- 数学的帰納法~整数であることの証明
数学的帰納法の初歩(?)の質問です。 問。ｎは自然数とする。２数ｘ，ｙの和、積がともに整数のとき、ｘ^n＋ｙ^n整数であることを、数学的帰納法によって証明せよ。 という問題なのですが、解説に i)n=1,n=2のときに成り立つことを示す ii)n=k,n=k-1であると仮定して、n=k+1のときにも成り立つことを示す とありました。 また、注がついており、 『x^(k+1)+y^(k+1)=(x^k+y^k)(x+y)-xy{x^(k-1)+y^(k-1)}である』とありました。 なぜ『』だからi)でn=2を、ii)でn=k-1を書かないといけないのですか？ お願いします。
- ベストアンサー
- 数学・算数
- 数A 整数の性質
kを２以上の整数とする。２からkまでの整数のうち、kと互いに素であるものの個数をNとする。 例えば、k=５とすると２から５までの整数のうち、５と互いに素であるものは２、３、４で あるから、N=３である。 （１）k=７のとき、Nを求めよ。また、k=１４のとき、Nを求めよ。 （２）pを７でない素数とする。k=７pのとき、Nを求めよ。 （３）p、qはともに素数であり、p＜qとする。k=pqのとき、N=１１を満たすp、qの組（p、q）をすべて 求めよ。 この問題があまり分かりません。解答・解説を見ても分かりませんでした。 分かる方がいれば、解説まで教えて下さい。 宜しくお願いします。
- 締切済み
- 数学・算数
- 整数問題の質問です。
3で割ると1余り、5で割ると3余る2桁の最大の数を求めよ。という問題で、解説は、 3で割ると1余り、5で割ると3余る数の1つをaとおくと、a=3m+1 a=5n+2（m,nは整数）と表せる。3m+1=5n+3より、3m=5n+2 n=0,1,-1のうち、5n+2が3の倍数になるのはn=-1で、このときm=-1よってa=-2 求める数は15k-2（kは整数）と表せるので k=6のとき88となる。 となっているのですが、わからないことが２つあります。１つ目は、どうして n=0,1,-1にしたのかということで、２つ目は、a=2だとどうして求める数が15k-2（kは整数）になるのかということです。教えて下さい。
- ベストアンサー
- 数学・算数
- 高校レベルの整数問題です
正の整数mを10進法で表したときの各桁の数の2乗の和をf(m)とする。 (1)mの桁数が4以上なら、f(m)の桁数はmの桁数より小さいことを示せ。 (2)数列a(n)をa(1)=m,a(n+1)=f(a(n))と定める。数列a(n)はある項以降は同じ数の並びの繰り返しとなることを示せ。 この問題ですがどこから手をつければいいのかさっぱりわかりません。 どなたか教えていただけないでしょうか
- 締切済み
- 数学・算数
- 帰納法と背理法の注意点について
「nを正整数とする。(2^n) + 1は１５で割り切れないことを示せ。」という問題です。 解答は帰納法で解くのではなく、nを具体化していくと１５で割ったあまりが3,5,9,2・・・のパターンで推移していくのを証明すればいい問題なのですが、これに対して私は帰納法と背理法をミックスして以下のように解こうと思ったのですがだめですか。 (2^n) + 1は１５で割り切れると仮定し、それを帰納法で表す。 n=1のとき3となり15で割り切れない。 n=kのとき１５で割り切れると仮定する。つまり (2^k) + 1=15m ⇔2^k=15m-1・・・(1)が成り立つと仮定する。 (1)より (2^k+1)=2(15m-1) =15・2m - 2 となり矛盾する。よって(2^n) + 1は１５で割り切れない・・・(終） どこかおかしそうな気がするのですが、結論として帰納法は帰納法単独でしか使えないのでしょうか。この問題は帰納法単独だけでは「(2^n) + 1は１５で割ると１３余る数ではない」ということしか証明できないので困ります。 よろしくおねがいします。
- ベストアンサー
- 数学・算数
お礼
わかりました！ ありがとうございます！