プロが教えるわが家の防犯対策術!

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

『1から100までの数が並んでいます。2から消し始めて4,6,・・・と
一つおきに数字を消していきます。最後尾まで行けば、最初に戻って続けます。
最後に残った数は何でしょう?』という問題です。たとえば、1から4なら
『2、4、3』と消えて最後は1が残り、1から5なら『2、4、1、5』と
消えて最後に3が残ります。

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

A 回答 (3件)

証明はしていませんが、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が残ることがわかりますが、
一般解の証明は専門の方に譲ります。
    • good
    • 1
この回答へのお礼

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

お礼日時:2001/03/10 02:25

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



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.
    • good
    • 0
この回答へのお礼

なんと、stomachmanさんからも解をいただけるとは光栄です。ご丁寧な
証明をありがとうございました。ただ、わたしの理解の範囲を越えてい
るかもしれません。ゆっくり読ませていただきます。ありがとうござい
ました。

お礼日時:2001/03/10 02:26

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



参考URL:http://web2.incl.ne.jp/yaoki/week115.htm
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/03/09 20:34

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!