Fussy's Diary

今日、8 月 2 日は「パンツの日」だそうです。語呂合わせでそうなったらしいです。あと、6 月 2 日が「カレーの日」で 7 月 2 日が「うどんの日」だから 8 月 2 日は「カレーうどんの日」。さらにこれも語呂合わせで「ハーブの日」でもあるようです。いったい、そんな日を決めて何をすればいいのでしょうか。

「数学問題集」からこんな問題をチョイス。相変わらずの逃避行動。

-----

■ 3000 枚のカードに 1 から 3000 まで番号が書かれており、1 を一番上として番号順に積み重なっている。『一番上のカードを一番下に挿入し、次に一番上になったカードを捨てる』 という作業を繰り返したとき、最後に残るカードの数字は何か（コマ大数学科第 6 回ヨセフスの問題・改）

最初の操作は、1 を一番下 ( 3000 の下 ) に挿入して 2 を捨てることになります。次は 3 を下に挿入して 4 を捨てる... ということを繰り返した結果、偶数のカードは全て捨てられることになり、3000 番のカードを捨てれば 1 が再び一番上になります。この時点で、カードは奇数が 1 から順に並んだ状態となります。1 を一番下に挿入して一番上に現れるカードは 3 で、これが捨てられます。以下、5 を下に挿入して 7 を捨てる... ということを繰り返した結果、4n + 1 ( n ≥ 0 ) のカードだけが残った状態で再び 1 が一番上になります。以下、次のようにカードが残ることになります。

一巡目終了 : 2n + 1 が残り、1 が一番上になる。残りの枚数は 1500 枚。
二巡目終了 : 4n + 1 が残り、1 が一番上になる。残りの枚数は 750 枚。
三巡目終了 : 8n + 1 が残り、1 が一番上になる。残りの枚数は 375 枚。

四巡目からは残りの枚数が奇数になります。このとき、四巡目が終了した時点で捨てられるカードが逆転する現象が発生します。四巡目は 16n + 1 が残って 16n + 9 が捨てられる事になりますが、末尾のカードを一番下にしたときに現れるカードは 1 であり、次に捨てられるのはこのカードで、その後に現れるカードは 1 に 16 を加算した 17 です。従って、

四巡目終了 : 16n + 1 が残り、17 が一番上になる。残りの枚数は 187 枚。

となります。1 を捨てたので、端数は消えることに注意してください。つまり、奇数なら増分を加算すればいいので、これを繰り返せば

五巡目終了 : 32n + 1 が残り、17 + 32 = 49 が一番上になる。残りの枚数は 93 枚。
六巡目終了 : 64n + 1 が残り、49 + 64 = 113 が一番上になる。残りの枚数は 46 枚。
七巡目終了 : 128n + 1 が残り、113 が一番上になる。残りの枚数は 23 枚。
八巡目終了 : 256n + 1 が残り、113 + 256 = 369 が一番上になる。残りの枚数は 11 枚。
九巡目終了 : 512n + 1 が残り、369 + 512 = 881 が一番上になる。残りの枚数は 5 枚。
十巡目終了 : 1024n + 1 が残り、881 + 1024 = 1905 が一番上になる。残りの枚数は 2 枚。
十一巡目終了 : 2048n + 1 が残り、1905 が一番上になる。残りの枚数は 1 枚。

よって、最後に残るのは 1905 となります。アルゴリズムとしては、

1. 増分 add を 2、最後に残る番号 head を 1 で初期化する。
2. 枚数を 2 で割り、1 余ったら head に add を加算する。
3. add に 2 を掛ける。
4. 枚数が 1 になるまで 1 から 3 の操作を繰り返す。

ということになります。以下に、実際に配列を使って操作を繰り返す場合と、上記アルゴリズムを使った場合のサンプル・プログラムを示しておきます( C++ で STL を使ってます)。

unsigned int size = 3000; // カードの枚数

// 配列 (vector) を使って実際に操作する

std::vector<unsigned int> data( size );
for ( unsigned int i = 0 ; i < data.size() ; ++i )
data[i] = i + 1;

while ( data.size() > 1 ) {
unsigned int i = data[0];
data.erase( data.begin() );
data.push_back( i );
data.erase( data.begin() );
}
std::cout << data[0] << std::endl;

// 枚数を使ったアルゴリズム

unsigned int add = 2;
unsigned int head = 1;
while ( size > 1 ) {
if ( size & 1 ) head += add;
size /= 2;
add *= 2;
}
std::cout << head << std::endl;