数学クイズ教えてください

質問

クイズを出題されました。継子立てというものでしょうか？解けません。
教えてください。

『１から１００までの数が並んでいます。２から消し始めて４，６，・・・と
一つおきに数字を消していきます。最後尾まで行けば、最初に戻って続けます。
最後に残った数は何でしょう？』という問題です。たとえば、１から４なら
『２、４、３』と消えて最後は１が残り、１から５なら『２、４、１、５』と
消えて最後に３が残ります。

できれば一般化して１からｎまでのときも教えていただければうれしいです。

回答No.2

guiter · ベストアンサー

証明はしていませんが、Ｎ個の数が並んでいるときには
まず、
Ｎ＝２＾ｎ＋ｍ　（ｎは取りうる最大のもの、ｍ＜２＾ｎ）
というように表すと、　２ｍ＋１　が残る数になります。

例えば、質問のように１から１００までの場合
１００＝２＾６＋３６
なので、２×３６＋１＝７３　となります。

ｍ＝０、すなわち　Ｎ＝２＾ｎ　の形のときに１が残るのは
常に偶数個が残り続けることから１が残ることがわかりますが、
一般解の証明は専門の方に譲ります。

お礼

ありがとうございます。５００のときと１０００のときの解も聞かれて
いたので、さっそく解をメールしたら、相手が驚いていました。もちろん
gooで聞いたとは言っていません。
ところでguiterさんって、『guitar』ではないのですね。すみません、
余計なことでした。

回答No.3

stomachman

あちゃ、もう回答が出ているので、蛇足になります。

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以下の最大の「２の冪乗」です。特に、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 となる。
　次に消すのは残りのうちの２番目なので 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 となる。
　次に消すのは残りのうちの１番目なので 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)となる。
　次に消すのは残りのうちの１番目なので 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 となる。
　次に消すのは残りのうちの１番目なので 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 となる。
　次に消すのは残りのうちの２番目なので 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

kunimaru3

これ参考になるでしょうか？でもちょっと答えが違うかな

参考URL：

http://web2.incl.ne.jp/yaoki/week115.htm

お礼

すみません。それは、わたしも検索して見つけましたが、設定条件が違いました。