-PR-
解決
済み

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

  • すぐに回答を!
  • 質問No.49741
  • 閲覧数201
  • ありがとう数12
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 87% (42/48)

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

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

できれば一般化して1からnまでのときも教えていただければうれしいです。
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル10

ベストアンサー率 51% (86/168)

証明はしていませんが、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が残ることがわかりますが、
一般解の証明は専門の方に譲ります。
お礼コメント
adagio

お礼率 87% (42/48)

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

その他の回答 (全2件)

  • 回答No.1
レベル9

ベストアンサー率 38% (12/31)

これ参考になるでしょうか?でもちょっと答えが違うかな ...続きを読む
これ参考になるでしょうか?でもちょっと答えが違うかな
お礼コメント
adagio

お礼率 87% (42/48)

すみません。それは、わたしも検索して見つけましたが、設定条件が違いました。
投稿日時 - 2001-03-09 20:34:34
  • 回答No.3
レベル14

ベストアンサー率 57% (1014/1775)

あちゃ、もう回答が出ているので、蛇足になります。 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 ...続きを読む
あちゃ、もう回答が出ているので、蛇足になります。

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.
お礼コメント
adagio

お礼率 87% (42/48)

なんと、stomachmanさんからも解をいただけるとは光栄です。ご丁寧な
証明をありがとうございました。ただ、わたしの理解の範囲を越えてい
るかもしれません。ゆっくり読ませていただきます。ありがとうござい
ました。
投稿日時 - 2001-03-10 02:26:48
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ