まず２進法の構造を調べることから始めましょう。
A B C D
---------------------------
1 1 1 1
2 10 10 2
3 11 1 1
4 100 100 3
5 101 1 1
6 110 10 2
7 111 1 1
8 1000 1000 4
9 1001 1 1
10 1010 10 2
11 1011 1 1
12 1100 100 3
13 1101 1 1
14 1110 10 2
15 1111 1 1
ここで、Ａ は10進数、Ｂ はその２進数、Ｃ は２進数を
右から探して初めて１が現れるまでを書き出したもの、
Ｄ はそのときの１の位置（桁）を示します。
Ｄ を２進法の「リズム」ということにします。この「リズム」
が２進法の特徴を示しているのです。
練習１ 親指を１、人差し指を２、中指を３、薬指を４、
小指を５とします。これら５本の指を用いて１から31までを
２進法で数えてみましょう。どの指を折ったか（伸ばした指
は無視して）に注意すると2進法の「リズム」が得られます。
次は「ハノイの塔」です。
ハノイの塔とは、大きさの異なる数枚の円板が、大きさの
順の山に積み上げられていて、
１ 一度に１枚しか動かせない。
２ 小さな円板の上に、より大きな円板を乗せ
ることはできない。
３ 始めの山も含めて３箇所にしか置けない。
という制限のもとで、円板の山を別の場所に移動せよ、という
遊びです。
上の小さな円板から順に １、２、３、４、と番号をつけます。
n 番目の円板を動かすことを単に n とあらわすことにします。
n 番目から上の山を動かすことを a_n で表します。
n は現実の具体的なひとつの操作ですが、 a_n はいくつかの
操作を続けておこなったものです。
これらの間の関係式として次の漸化式
a_n = a_{n-1} n a_{n-1}, a_1 = 1
が得られます。 n 番目から上の山を動かすには、まず n-1 番目
から上の山を動かし、次いで n 番目の円板を動かし、 n-1 番目
から上の山を戻してくれば良いという、まことに常識的な話を、
数式で表したものです。
これから帰納的に、
a_1 = 1
a_2 = 1 2 1
a_3 = 1 2 1 3 1 2 1
a_4 = 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
と求めていくことができて、これはまさに２進法の「リズム」
そのものです。
４桁までの２進法と４段のハノイの塔が 「同型」となる
ところを表にしてみましょう。
A B C D ハノイの塔
------------------------------------------
4321
1 1 1 1
432 1
2 10 10 2
43 1 2
3 11 1 1
43 21
4 100 100 3
4 3 21
5 101 1 1
41 3 2
6 110 10 2
41 32
7 111 1 1
4 321
8 1000 1000 4
321 4
9 1001 1 1
32 41
10 1010 10 2
2 3 41
11 1011 1 1
21 3 4
12 1100 100 3
21 43
13 1101 1 1
2 1 43
14 1110 10 2
1 432
15 1111 1 1
4321
ここで２進法は 「操作」、ハノイの塔は 「状態」
であることにご留意下さい。
「知恵の輪」
のページへ戻る。
「ホームページ」
へ戻る。