『チャイニーズリング』解答

◆広島県　清川　育男さんからの解答。

【第１問の答え】

　４連　１０。
　５連　２１。
　６連　４２。

【第２問の答え】

ｍ≧１

奇数のとき　ｎ＝２ｍ−１とすると

手数は１＋

（４m-1−１）×４ ３

偶数のとき　ｎ＝２ｍとすると

手数は２＋

（４m-1−１）×８ ３

【コメント】

　みごと正解です。
順序だててやらないと、実験はまずうまくいかないと思います。
１７世紀にはもう日本にもこのパズルがあったらしいです。
他の方は理由を考えてくださいね。

◆東京都　GOYAさんからの解答。

チャイニーズリング第２問の解答

ｎ連のリングのｎ連目のリングをはずすには１番目から（ｎ−２）番目のリングをはずさないとはずせません。

ｎ番目のリングをはずした時のリングの状態は（ｎ−１）番目のリングだけはまっていて、その他のリングははずれています。
その状態から（ｎ−１）番目のリングをはずすにはと考えていくと下の表の手順(1)〜(6)のようになります。

(1)〜(6)で連数が１つ減った訳ですからこれを順次繰り返せば全てのリングがはずれます。

　　　手　順　　　＜−┫　┣−＞　　連　数

	反転させる リング��	リングの状態	１	２	３	４	５	６	７	・・
(1)	１〜(ｎ−２)	１１１１１〜１	−	−	１	２	５	１０	２１	・・
(2)	ｎ	１１０００〜０	１	１	１	１	１	１	１	１
(3)	１〜(ｎ−３)	０１０００〜０	−	−	−	１	２	５	１０	・・
(4)	１〜(ｎ−４)	０１０１１〜１	−	−	−	−	１	２	５	・・
(5)	ｎ−２	０１０１０〜０	−	−	１	１	１	１	１	１
(6)	１〜(ｎ−４)	０１１１０〜０	−	−	−	−	１	２	５	・・
(1)〜(6)の結果		０１１１１〜１
小計(手)			１	１	３	５	１１	２１	４３	・・
合計(手)			１	２	５	１０	２１	４２	８５	・・

(1)〜(6)の各手順に要する手数は(2)と(5)は１手ですが、その他の手順はｎより少ない連数をはずす手数が判らないと求めることができません。
そこで、少ない連数から求めていくと表の右側部分になります。
　（表内の数字は(1)〜(6)に要する手数）
小計は連数を１つ少なくするまでの手数（(1)〜(6)の合計）
合計がｎ連のリングを全てはずす手数

１からｎ連迄の小計の総和ですがｎ連の小計と１連少ない合計との和で求められます。
　（例えば５連の場合、１１＋１０）

次にｎ連をはずすのに必要な最小手数を求めるという本題に入ります。
上の表の合計の欄の規則性を探します。

奇数連だけに着目すると

　１，５，２１，８５・・　各項の差は

　　４　１６　６４　　と４の累乗になっているので次式となります。

　Ｓ_n

＝１＋４＋４2＋４3＋４4＋・・・＋４m-1

＝

m-1 Σ k=0

(４k)

ここで ｍ＝（ｎ−１）÷２

偶数連の場合は直前の奇数連の２倍の手数になってますから

　Ｓ_n

＝２×(１＋４＋４2＋４3＋４4＋・・・＋４m-1)

＝２×

m-1 Σ k=0

(４k)

ここで ｍ＝ｎ÷２

　−　以上　−

Σを使った式から広島県　清川　育男さんからの解答の式

１＋	（４m-1−１）×４ ３

への移行方法は残念ながら判りませんでした。

どうやったら、この式が導き出せるのでしょうか？誰か教えて。

ついでにJavaScriptで開錠の手順をhtml生成するスクリプトを作成しました。

• １手につきｈｔｍｌを１行生成しますので多い手数を生成すると表示完了までに長い時間が掛かります。
  　　（たぶん、普通にページロードする程度）
  
• 生成する連数をキー入力するようにしてあり、１４連迄生成できます。
  
• 生成完了までブラウザが見た目停止するため、１０００手生成する毎に処理を続行するか確認メッセージを表示するようにしています。

【コメント】

　この解答には驚きました。
開錠の手順は必見ですので、ぜひ見てください。
たぶんＩＥ３．０以上、ＮＮ３．０以上で動くと思います。
Σの式からの変形は
初項ａ、公比ｒの等比数列のｎ項までの和が
ａ＋ａｒ＋・・・＋ａｒ^n-1

＝	ａ（１−ｒ）n １−ｒ

であることを用いると、

奇数連の時は、初項１，公比４，項数ｍだから

＝

１−４m １−４

＝

４m ３

−

１ ３

偶数連の時は、

（

４m ３

−

１ ３

）×２

＝

２×４m ３

−

２ ３

これは清川　育男さんの解答と一致しています。

◆東京都　藤本 さんからの解答。

【問題２】

ｎ個のリングをはずすための手数をＰ_n　とする。

ｎ≧３の場合　この手数Ｐ_nは

1. Ｃ₁ から Ｃ_n-2 までのリングをすべてはずす
   　Ｐ_n-2手
2. Ｃ_ｎ をはずす
   　１手
3. Ｃ₁ から Ｃ_n-2 までのリングをすべてはめる
   　Ｐ_n-2手
4. Ｃ₁ から Ｃ_n-1 までのリングをすべてはずす
   　Ｐ_n-1手

Ｐ_n＝Ｐ_n-1＋２Ｐ_n-2＋１…(1)

の漸化式が成立する

また　ｎ＝１，２の場合　それぞれ

Ｐ₁ ＝ １…(2)
Ｐ₂ ＝ ２…(3)である。（自明）

ここで　(1)の　漸化式より

Ｐn−２Ｐn-1−

１ ２

＝−(Ｐn-1−２Ｐn-2−

１ ２

）

………………

＝（−１）n-2(Ｐ2−２Ｐ1−

１ ２

）

＝

（−１）n-１ ２

…(4)

が導かれる。

ここで　ｎが奇数の場合 ｎ＝２ｍ−１ とすると

Ｐ_2m-1 −２Ｐ_2m-2 − １ ＝ ０

故に
Ｐ_2m-1 ＋ １ ＝ ２（ Ｐ_2m-2 ＋ １ ）…(5)

が成り立つ。

また　ｎが偶数の場合　ｎ ＝ ２ｍ　とすると

Ｐ_2m −２Ｐ_2m-1 ＝ ０

故に
Ｐ_2m ＝ ２Ｐ_2m-1…(6)

が成り立つ。

(5)(6)　より

Ｐ_2m-1 ＋ １
＝ ２（ ２Ｐ_2m-3 ＋ １ ）
＝ ４Ｐ_2m-3 ＋ １

故に

Ｐ2m-1＋

１ ３

＝４（ Ｐ2m-3＋

１ ３

）

……………

＝４m-1（Ｐ1＋

１ ３

）

＝

４m ３

よって

Ｐ2m-1 ＝

４m−１ ３

…(7)

また　(7)　を　(6)に代入して

Ｐ2m ＝

２（４m−１） ３

◆カステラ さんからの解答。

【コメント】

大学のゼミでチャイニーズリングを取り扱ったときに解きました。
これなら、チャイニーズリングの輪の個数がわかれば、何回で解けるか、奇数偶数に関係なく求められます。

【解答】

n=輪の個数
A_n=輪を外すまでに要する回数

このようにおくと、 この輪の移動回数の漸化式は既に出ている、少ない輪の数の解答から

A_n＝A_n-1＋２A_n-2＋１となる。

この式を変形すると、『こうなる』という予想をたて、

(A_n＋αA_n-1＋γ)＝β(A_n-1＋αA_n＋γ)

と、おいてみる。これを展開すると、

A_n＋(α−β)A_n-1−αβA_n-2＋γ(１−β)＝０

これは、A_n−A_n-1−２A_n-2＝０と対応しているので、

α−β＝−１
αβ＝２
γ(１−β)＝−１

これを解くと、

(α，β，γ)＝(１，２，１)、(−２，−１，−

１ ２

)

(�@)(α，β，γ)＝(１，２，１)のとき、

A_n＋A_n-1＋１＝２(A_n-1＋A_n-2＋１)

A_n-1＋A_n-2＋１＝B_nとおく。

∴B_n+1＝２B_n

B₁＝A₂＋A₁＋１＝２＋１＋１＝４
（∵A₁＝１，A₂＝２）

｛B_n｝は初項４、公比２の等比数列

B_n＝４・２^n-1＝２ⁿ⁺¹＝A_n-1＋A_n-2＋１・・・(1)とおく。

(�A)(α，β，γ)＝(−２，−１，−

１ ２

)のとき

An−２An-1−

１ ２

＝(An-1−２An-2−

１ ２

）

An-1−２An-2−

１ ２

＝Cnとおく。

∴C_n+1＝−C_n

C1＝A1−２A1−

１ ２

＝２−２・１−

１ ２

・・・(2)

{Cn}は初項−

１ ２

、公比−１の等比数列

Cn＝−

１ ２

・(−１)n-1＝An-1−２An-2−

１ ２

・・・(2)

(1)と(2)の連立方程式を解くと

An＝	２n+2＋(−１)n+1−３ ６

◆北海道　小西 さんからの解答。

みなさんの解答の補足です。

n個の輪を外すまでに要する回数A_nを以下のように定義する。

An =	{	Bn (nが奇数の場合)
		Cn (nが偶数の場合)

清川さん、GOYAさん、藤本さんの解答をまとめると、

nが奇数の時、m =

n + 1 2

より、

Bn =	2n + 1 - 1 3

nが偶数の時、m =

n 2

より、

Cn =	2n + 1 - 2 3

A_nはB_nとC_nの平均からB_n側とC_n側への振動を繰り返しているから、

An ≡

Bn + Cn 2

+

(-1)n + 1(Bn - Cn) 2

(nが奇数の時A_n = B_n、nが偶数の時A_n=C_nになる)

これに先のB_n、C_nをそれぞれ代入すれば、

An＝	2n + 2 + (-1)n + 1 - 3 6

となり、カステラさんの解答と一致します。

◆京都府　あさとみ さんからの解答。

【問題２】

＊ｎ番目の輪は、ここでは「Ｃ(n)」と表記する。

Ｃ(1),Ｃ(2),...,Ｃ(n)がすべて外れた状態から、Ｃ(1),Ｃ(2),...,Ｃ(n-1)がすべて外れ、Ｃ(n)がはまった状態にするための最小手数をＰ(n)とする。

このとき、Ｃ(1),Ｃ(2),...,Ｃ(n-1)がすべて外れ、Ｃ(n)がはまった状態から、Ｃ(1),Ｃ(2),...,Ｃ(n)がすべて外れた状態にするための最小手数もＰ(n)である。

Ｃ(1),Ｃ(2),...,Ｃ(n)がすべて外れた状態から、Ｃ(1),Ｃ(2),...,Ｃ(n-1)がすべて外れ、Ｃ(n)がはまった状態にするためには、次のような手順を経ればよい。

1. Ｃ(n-1)のみがはまった状態にする。
2. Ｃ(n)をはめる。
3. Ｃ(n-1)を外す。

Ｐ(n)＝Ｐ(n-1)＋1＋Ｐ(n-1)＝２×Ｐ(n-1)＋1

また、Ｐ(1)＝1

よって、Ｐ(n)を求めると、Ｐ(n)＝2ⁿ-1

また、Ｃ(1),Ｃ(2),...,Ｃ(n)がすべてはまった状態から、Ｃ(1),Ｃ(2),...,Ｃ(n)がすべて外れた状態にするための最小手数（求めたい最小手数）をＱ(n)とする。

この作業を行うには、次のような手順を経ればよい。

1. Ｃ(1),Ｃ(2),...,Ｃ(n-2)を外す。
2. Ｃ(n)を外す。
   （このとき、Ｃ(n-1)のみがはまった状態となる。）
3. Ｃ(n-1)を外す。

Ｑ(n)＝Ｑ(n-2)＋1＋Ｐ(n-1)＝Ｑ(n-2)＋2^n-1

ここで、kを自然数とおく。

Ｑ(1)＝1より、

　Ｑ(2k-1)
＝1＋2²＋2⁴＋...＋2^2k-2
＝1＋4¹＋4²＋...＋4^k-1

＝1＋4×

4k-1-1 4-1

＝1＋4×

4k-1-1 3

Ｑ(2)＝2より、 　Ｑ(2k)
＝2＋2³＋2⁵＋...＋2^2k-1
＝2(1+2²＋2⁴＋...＋2^2k-2)

＝2(1＋4×

4k-1-1 3

)

＝2＋8×

4k-1-1 3

以上より、求める最小手数は、

n=2k-1 のとき、1＋4×

4k-1-1 3

であり、

n=2k のとき、2＋8×

4k-1-1 3

である。

　チャイニーズリングへ

　数学の部屋へもどる