Chinese ring ３

 　西洋では、イタリアのGerolamo Cardano（ジェロラモ・カルダーノ、1501～1576年、数学者）が1550年に書いた本の中で論じているから、相当古くからあることがわかるが、中国との関係はよくわからない。その後イギリスのJohn Wallis（ジョン・ウォリス、1616～1703年、数学者）も論じている。注目すべきは、1872年にフランスのＭ .Ｌ．グロ（詳細不明）が二進法を利用してこの問題を巧みに解明したことであるという。
 
　二進法は、２になるごとにケタが上がり、数字は０と１しか用いない。われわれが普通使っている十進法の数を２進法に直すには、左の図のように、どんどん２でわっていき、割り切れたときには０、余ったときには１と右側に書く。この書き留めた数を下のほうから順に並べると、二進法の数になる。つまり、十進法の26は　二進法であらわすと、　11010　となるのである。
　反対に二進法の数を十進法に直すには、二進法のｎ位は２ⁿ⁻¹ を単位としているわけであるから、11010　は、　２⁴＋２³＋０＋２¹＋０＝16＋８＋２＝26　が十進法で表わした数となる。
 
　チャイニーズ・リングを少しいじってみると分かるが、３月14日のブログでも述べたように、一番右端の環は自由にはずせる。また二番目の環もはずすことができる。しかし、３番目から先は簡単にはいかない。一般にｎ番目の環は、（ｎ－２）番目の環までは全部はずれていて、（ｎ－１）番目の環がはまっているときに限ってはずすことができるのである。
 
　ここでＭ .Ｌ．グロのやり方を簡単に説明してみよう。まず横線を一本引いて、竿にはまっている環はその上部に、はずれている環はその下部に○印で表すことにする。この記載法で４連のものをはずす手順を図に示すと、左図の「４連のものを外す手順」の中央のような図になる。なお、この図は一番端の、自由にはずせる環のある方を右に置いている。
ところで、
(ａ) 横線より上にある○には、左から1､0､1､0､･･･と、交互に１と０をつける。
(ｂ) 横線より下にある○には、それより左側にはまっている環がなければ全部０、あればそれと同じ数字をつける。
という約束にすると、今の４連のものを解く過程は、左図の「4連のものを外す手順」の各右側に示すようように表せることになる。
　ここで、この数を二進法の数と考えてみよう。M.L.グロはChinese ringの環を１個嵌めたり外したりする度に、必ずこの数が１だけ変わることに注目したのである。４連の場合は、全部嵌っている状態　1010 から、全部外れた状態　0000 にするには、その差だけの手数が必要ということになる。二進法の1010は十進法では
　２³＋０＋２＋０＝８＋２＝10　であるから、最低10手が必要なわけである。
 
　環の数が奇数個の場合、すなわち、１個の場合は二進法で１回、３個の場合は二進法では101回、５個の場合は二進法で10101回の手数がかかることになり、これを十進法に直すとそれぞれ１、５、21となる。
　環の数が偶数この場合、すなわち、２個の場合は二進法で10回、4個の場合は二進法で1010回、6個の場合は二進法で101010回の手数がかかることになり、これを十進法に直すとそれぞれ２､10、42となる。
 
　一般に環の数がｎ個の時の最少手数は、ｎが奇数の場合と偶数の場合に分けて、左の式で求めることが出来る。