事件の発端

「ナミダ偏にムズカシイ」と書くといわれる灘中。
その灘中学校の算数の入試問題として、次の問題が掲示板に紹介されました。

問題１　　１から64までの数字を書いた64枚のカードを
円周上に小さい順に連続して時計回りに並べる。
最初に1のカードを取り除き、時計回りに、1つおきにカードを取り除いていく。
残りのカードが1枚になるまで続けると最後に残るのはどのカード？

なかなか面白い問題です。掲示板は一時異様な熱気に包まれました。
いえ、そう思ったのは僕だけで、実は「こんにゃく問答」だったのかもしれませんが。
ま、ひとつ。ここは異文化交流だと思ってお付き合いの程を･･･。
何通りかの解答をみなさんに発表して頂いた後、僕は次のような答案を提出しました。

答案１　　カードの取り除き方はカードに書かれている番号に依存しないので、
途中、番号を書き換えても再現できれば気にならない。
１周したとき残っているのは、２の倍数（偶数）のカードが３２枚。
その番号を２で割ってみると、１から３２までの数が並ぶ。これで６４枚が３２枚になった。
１周目と２周目のつながり方に注意しよう。
もう一周すると、この書き直した番号で２の倍数が１６枚残る。番号を２で割ってみる。

この操作を繰り返す。一周するごとに、枚数は半分になる。
６４枚＝２×２×２×２×２×２枚なので、６周目が終わったとき残りが１枚になり、
いままで書き換えた分を清算すれば、そのカードは２×２×２×２×２×２＝６４番。
最後に残るのは６４と書かれたカードであることが分かる。

もちろん、問題は「最後に残るのはどのカード」かを訊いているだけなので、
「６４と書かれたカード」とだけ答えればよく、理由の説明は不要です。
だから、「答だけ合ってる」のも正解。

ところが、これで事件は終わらなかった！　問題の拡張を依頼されてしまったのです。
つまり、この問題はカードの枚数が６４枚の場合だが、
一般の枚数のとき最後に残るのはどのカードだろう･･･というわけです。
とりあえず問題の形に整理しておきましょう。

問題２　　ｎを自然数（１，２，３，･･･）とする。1からｎまでの数字を書いたｎ枚のカードを
円周上に小さい順に連続して時計回りに並べる。
最初に1のカードを取り除き、時計回りに、1つおきにカードを取り除いていく。
残りのカードが1枚になるまで続ける。最後に残るカードをみつける公式を求めよ。

しかしこのままでは、問題として弱い。「公式」とは何かが定義されていないからです。
屁理屈に思えますが、そのあたり数学は結構デリケートなのでご勘弁下さい。
ある特定のｎについて、実際やってみたら最後のカードが分かるんだから、
実際いちいちやってみるのもひとつの公式だ、公式なんだい！　と言い張ることさえできます。

さて、とにかく何か依頼されてしまいました。僕はこの期待に応えることができるのでしょうか。

解決編その１へ