No.2ベストアンサー
- 回答日時:
証明はしていませんが、N個の数が並んでいるときには
まず、
N=2^n+m (nは取りうる最大のもの、m<2^n)
というように表すと、 2m+1 が残る数になります。
例えば、質問のように1から100までの場合
100=2^6+36
なので、2×36+1=73 となります。
m=0、すなわち N=2^n の形のときに1が残るのは
常に偶数個が残り続けることから1が残ることがわかりますが、
一般解の証明は専門の方に譲ります。
ありがとうございます。500のときと1000のときの解も聞かれて
いたので、さっそく解をメールしたら、相手が驚いていました。もちろん
gooで聞いたとは言っていません。
ところでguiterさんって、『guitar』ではないのですね。すみません、
余計なことでした。
No.3
- 回答日時:
あちゃ、もう回答が出ているので、蛇足になります。
a:1~nまであるとして(n≧1)、2,4, ....という風に消していくとすると、
n=(2^m)+k (0≦k<(2^m))
と書いたとき、最後に残るのは(2k+1)番目です。
これをA(m,k)=2k+1と書くことにします。ここで(2^m)とはn以下の最大の「2の冪乗」です。特に、n=(2^m) のときには必ず1番が残ります。
b:また1~nまであるとして(n>1)、1,3,.....という風に消していくとすると、n=(2^m)+k (0≦k<(2^m))と書いたとき、k=0なら(2^m)番目, k>0なら(2k)番目が最後に残ります。この答をB(m,k)と書くことにします。特に、n=2^m のときには必ずn番が残ります。
以下証明です。
まず、n=1の場合にはaが成り立ちます。これは自明。
次にm≧1の場合に
命題P(m):「A(m,k)=2k+1, B(m,0)=(2^m), B(m,k)=2k(k≠0のとき)」
が成り立つことを帰納法で証明しましょう。
@STEP 1: P(1)を示します。n=(2^m)+k (0≦k<(2^m))とします。
すなわちm=1, k=0またはk=1の場合です。
k=0...A(1,0)=1, B(1,0)=2 (n=2個なので)
k=1...A(1,1)=3, B(1,1)=2 (n=3個なので)
以上から
P(1):「A(1,k)=2k+1, B(1,0)=2, B(1,k)=2k(k≠0のとき)」
が示されました。
@STEP 2: P(m-1)が成り立つとし、n=(2^m)+k (0≦k<(2^m))とします。
{A(m,k)=2k+1の証明}
このn=(2^m)+k (0≦k<(2^m))個の列から偶数番目を消す。
残りをr個とし、このr個に改めて1,2,....と番号を振ると
(A1) kが偶数のとき:r=(2^(m-1))+k/2 となる。
次に消すのは残りのうちの2番目なので a の場合に該当し、最後に
A(m-1,k/2)=2(k/2)+1=k+1番
が残る。これはもとのn個の列の中では2k+1番目ですから、A(m,k)=2k+1。
(A2) kが奇数のとき:r=(2^(m-1))+(k+1)/2 となる。
次に消すのは残りのうちの1番目なので b の場合に該当し、kは奇数でk≠0。よって最後に
B(m-1,(k+1)/2)=2((k+1)/2)=k+1
番が残る。これはもとのn個の列の中では2k+1番目ですから、A(m,k)=2k+1。
以上からA(m,k)=2k+1が示されました。
{B(m,0)=(2^m), B(m,k)=2k(k≠0のとき)の証明}
このn=(2^m)+k (0≦k<(2^m))個の列から奇数番目を消す。
残りをr個とし、このr個に改めて1,2,....と番号を振ると
(B0) kが0のとき:r=2^(m-1)となる。
次に消すのは残りのうちの1番目なので b の場合に該当し、k=0だから最後に
B(m-1,0)=(2^(m-1))番
が残る。これはもとのn個の列の中では2r=n番目ですから、B(m,0)=(2^m)。
(B1) kが0でない偶数のとき:r=(2^(m-1))+k/2 となる。
次に消すのは残りのうちの1番目なので b の場合に該当します。k≠0なので最後に
B(m-1,k/2)=2(k/2)=k番
が残る。これはもとのn個の列の中では2k番目ですから、B(m,k)=2k。
(B2) kが奇数のとき:r=(2^(m-1))+(k-1)/2 となる。
次に消すのは残りのうちの2番目なので a の場合に該当し、最後に
A(m-1,(k-1)/2)=2((k-1)/2)+1=k番が残る。
k番はもとのn個の列の中では2k番目ですから、B(m,k)=2k。
以上から、B(m,0)=(2^m), B(m,k)=2k(k≠0のとき)が示されました。
従って、P(m-1)が成り立つとすればP(m)が成り立ちます。
というわけで、(ちょっと手抜きしてますが)一応Q.E.D.
なんと、stomachmanさんからも解をいただけるとは光栄です。ご丁寧な
証明をありがとうございました。ただ、わたしの理解の範囲を越えてい
るかもしれません。ゆっくり読ませていただきます。ありがとうござい
ました。
No.1
- 回答日時:
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 数学(数列) 二番の問題 模範解答では 二種類の一般項を出す→掛け合わせる→それをΣ計算する だった 4 2023/04/10 21:31
- Excel(エクセル) Excel 文字列が数値に変更できない 4 2022/12/07 06:08
- 事件・事故 2014年3月18日に乗員乗客239人が乗った航空機が消えた「マレーシア航空370便墜落事故」 (そ 5 2023/08/28 03:56
- 数学 高校数学の質問です 文字を消去したり、置き換えたりしたら、残った文字に範囲がつくかどうか調べるという 4 2023/05/03 18:18
- 数学 至急!!大学2年の女子です。この高校レベルの問題が分からないので教えてください!お願いしますm(_ 2 2022/11/11 22:10
- バラエティ・お笑い クイズ番組 2 2023/06/09 19:58
- 離婚 離婚した人のSNS 3 2023/01/26 11:41
- 所得・給料・お小遣い 現在私が勤めてる会社の給与について客観的にみてどうか教えていただきたいです。 今年23歳になるもので 4 2022/08/31 18:38
- 数学 高校数学Aについての質問です。 あたりくじ2本を含む8本のくじがあるとき、 1本引いて当たりかどうか 3 2022/10/11 15:38
- その他(結婚) 現在私が勤めてる会社の給与について客観的にみてどうか教えていただきたいです。 今年23歳になるもので 4 2022/08/31 18:54
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「証明証」と「証明書」はどう...
-
(4^n)-1が3の倍数であることの...
-
0.9999…=1がわからない
-
数学の「証明」のときなどの接...
-
3,4,7,8を使って10を作る
-
証明終了の記号。
-
どっちと思いますか
-
三角形の合同条件
-
じゃらんで旅行予約をしたので...
-
夫が亡くなった後の義理家族と...
-
素数の性質
-
なぜ独身だと養子が持てないの...
-
コラッツ予想が証明できた
-
素数の平方根は無理数である。
-
直角三角形の性質
-
3の倍数であることの証明
-
素数の積に1を加算すると素数で...
-
姻族関係終了届で継子とも縁切...
-
有理数が可算無限であることの証明
-
数学の等周定理、等周問題と呼...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
証明終了の記号。
-
図形の証明は、日常で役立ちま...
-
数学の証明問題で、「証明終了」...
-
直角三角形の性質
-
大学の二次試験で・・・
-
3,4,7,8を使って10を作る
-
素数の性質
-
円周率=∞の証明
-
「証明証」と「証明書」はどう...
-
(4^n)-1が3の倍数であることの...
-
なぜ独身だと養子が持てないの...
-
群論に関して, 明らかとしか思...
-
よって・ゆえに・したがって・∴...
-
Wikipedia って便利ですね。 よ...
-
素数の積に1を加算すると素数で...
-
夫が亡くなった後の義理家族と...
-
再婚、奨学金
-
婿養子です、妻と離婚して妻の...
-
正解が一つとは限らない数学の...
おすすめ情報