down under と数理

数枚(通常6~15枚程度)のカードを揃えて持つ。上から順に1,2,3と番号が振られているものとする。
まず1番上の1枚をどこかに捨て(down)次の一枚は1番下に回す(under)。その次の1枚はまた捨て、次は1番下に回す。これを残り1枚まで繰り返した時、最後に残ったカードの番号は何番か?

このように1枚おきに捨てていく操作を down under と呼んでいる。この問題の答えはジョン・スカーニー John Scarne が導いており、Scarne’s formula と呼ばれている。

・カードの枚数を n とする。
・2 の累乗の数列 [1,2,4,8,16…] のうち、n を超えない最大のものを m とする。
・最後に残るカードは 2(n-m) である。(ただし n=m の場合は n が残る)
例:カードが11枚だとすると、m=8 となり、残るカードは6

さて答えはわかったが、この formula の意味をもう少し考えてみたい。
まずは簡単の為、n=8とし、最初の4回の down under を考えよう。この時捨てられるのは 1,3,5,7 であり、 2,4,6,8 の4枚がこの順で残る。
数学的に言うとこれは「2で割りきれないカード」を捨てたと言える。
残った 2,4,6,8 から2回 down under をすると、捨てられるのは 2,6 で、残るのは4と8。勘の良い人はもう気付いたと思うが、今回捨てたのは「4で割り切れないカード」だ。
最後の down under を実行しよう。4が捨てられ、8が残る。これは、今までの流れに沿って言えば「8で割り切れないカード」を捨てたということになる。
n が2の累乗の場合(すなわち、2,4,6,8,16,32…)以上の流れによって n 枚目のカードが最後に残るという事が分かった。

これを踏まえた上で、次に n=9 の時を考えてみよう。一見、増えた1枚によってその後のカードの動きがカオス的な影響を受け、結果はまったく予想出来なくなると感じるかもしれない。
ともあれ、まずは1枚を down し、次のカードを under してみよう。カードに振られた数字で言うと1が捨てられ2が最後に回されるので、残る8枚の配置は34567892となる。
さて最後に残るカードがもう分かっただろうか。
つまりこういうことだ。9枚から始まって、down して、 under した。残りの8枚でこれから行う事はまさに8枚での down under である。ということは我々はすでにその答えを知っている。それは8枚目のカード、すなわち、今回の配列で言えば2ということだ。

これが Scarne’s formula の意味するところである。任意の n に対し、数回の down under (正確には n-m 回) を実行する事によってカードの枚数は m 枚になるので、その時 m 枚目に来ているカードが最後に残るカードである。

down under の兄弟に under down があるが、ここまでの議論が理解出来たなら、under down の formula は自明であろう。

余談1: down under というのは イギリス人から見て地面の真下にある国ということでオーストラリアの別称(蔑称?)らしい。そのため、down under には Australian shuffle という別名もあるそうだ。ところで shuffle というのはダンスステップの一種で、そのオーストラリア流というのがあり、これも Australian shuffle と言うようだ。
余談2: John Scarne は映画史に残る名作 The Sting (1973) でカードトリックの演技指導をしたマジシャンで、手だけ映画にも出演している。

return top