映画 X+Y 僕と世界の方程式

2015年　英国

2進数

他人とのコミュニケーションを苦手とする少年が，ずば抜けた数学の才能によって国際数学オリンピックの英国代表になったという実際にあった話をモデルにしたドラマです．その中の数学の授業での一コマです．

問題
Teacher : Twenty random cards are placed in a row, all face down. A move consists of turning a face down card, face up and turning over the card immediately to the right. Show that no matter what the choice of card to turn, this sequence of moves must terminate.

(筆者訳) 教師：20枚のカードが一列ですべて裏向きに置かれている．いずれかの裏向きのカードを表向きにして，すぐ右のカードをひっくり返すという動作を繰り返す．どのようにカードを選んでも，この一連の動作は必ず終わることを示しなさい．

教師に指名され，黒板の前に立った主人公の少年 Nathan は，話しにくそうにしながらも次のように説明していました．

(英語略･筆者訳) カードではなく数字だとして考える．裏向きを1，表向きを0とすると，最初は全部1が並んでいる．その後，例えば次のようになったとすると，これは2進数と考えられる．

10011010

この動作をすると，例えば11は00になり，

10000010

10は01になる．

10000001

上から下へ，この2進数の値は狭義単調減少になる（減っていく）． （注：「広義単調減少」は，減っていくが同じ値を繰り返すこともある）
これはこの一連の動作が必ず終わることを意味する．なぜなら，正の整数から整数がずっと減り続けて負の数にならないようにすることはできないから．

2進数表記にして考えるのは分かり易いですね．この後 Nathan は教師から褒められ，教室にいた生徒たちから賞賛の拍手を浴びていました．

さてこの問題，毎回どれか裏向きのカードを表向きにしてその右のカードをひっくり返していくわけですから，次の2種類の動作しかありません．

裏裏 → 表表（上の解答では11→00）

裏表 → 表裏（上の解答では10→01）

これを繰り返すと，偶数枚の時は最後に全部表向きで終わり，奇数枚の時は最後に右端だけ裏向きで終わります．この問題でのカードの枚数は20枚ということでしたが，$n$枚の場合に，終わるまでの最少動作数minと最多動作数maxを考えてみました．

例えば，$n$=3枚の時，最少で終わるのは 111→001 の1回で，最多で終わるのは 111→100→010→001 の3回になります．また，$n$=4枚の時，最少で終わるのは 1111→0011→0000 の2回で，最多で終わるのは 1111→1100→1010→1001→0101→0011→0000 の6回になります．さらにいくつかの場合を調べてみると次の表のようになります．

これを$n$の式で表すと次式になります．　( [    ]はガウス記号 )$$\min=\left [ \frac{n}{2}\right ]$$ $$\max=\frac{1}{2}n(n-1)$$なので，この問題の$n=20$枚の場合は，$$\min=\left [ \frac{20}{2}\right ]=10$$ $$\max=\frac{1}{2}\times20\times(20-1)=190$$すなわち，少なくて10回，多くて190回の動作で全部表向きになります．

[Reference]

X+Y (Clip) - Nathan solves math problem | Pinnacle Films
https://www.youtube.com/watch?v=mYAahN1G8Y8