質問: 数学クイズ教えてください クイズを出題されました。継子立てというものでしょうか?解けません。 教えてください。 『1から100までの数が並んでいます。2から消し始めて4,6,・・・と 一つおきに数字を消していきます。最後尾まで行けば、最初に戻って続けます。 最後に残った数は何でしょう?』という問題です。たとえば、1から4なら 『2、4、3』と消えて最後は1が残り、1から5なら『2、4、1、5』と 消えて最後に3が残ります。 できれば一般化して1からnまでのときも教えていただければうれしいです。
回答: あちゃ、もう回答が出ているので、蛇足になります。 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.