![かず6年(1204)](https://www.kitashirakawa.jp/yama-blog/wp-content/uploads/2023/05/2021-05-19-23.22.08-2-e1685531534636.jpg)
福西です。
この日は、K君とは「21を3つの自然数の和に分解する場合分け」を、Y君とは「ブラフマンの塔」の問題(通称ハノイの塔)を一緒に考えました。K君は、一つ目の数をまず(最小の自然数である)1で止めて、次に二つ目の数を1から1つずつ大きくしていき、残りを三つ目の数にするという方法で考えていきました。
(1,1,19)
(1,2,18)
(1,3,17)
(1,4,16)
(1,5,15)
(1,6,14)
(1,7,13)
(1,8,12)
(1,9,11)
(1,10,10)
こうすることで、もれなく10通りがまず見つかりました。ここでK君の方法のミソは、3つの自然数について、
1つ目の数≦2つ目の数≦3つ目の数
という右肩上がり(単調増加)の序列を作っていることです。
これによって、上の例で言えば、次に(1,11,9)を書き加えたくなってしまいますが、すでに(1,9,11)があり、ダブルカウントになってしまいます。その心配をなくすというこのテクニックはK君が自分で見つけてくれました。とても有用ですので、ぜひ今後も自家薬篭中にして下さい。
K君の答案です。
一方のY君は、円板が1枚、2枚、3枚の場合・・・と帰納的に試行錯誤を重ねて行って、とうとう「n枚の手数は、(n-1枚の手数)×2+1」という法則を見つけ出しました。
(ブラフマンの塔の問題文は、こちらのリンクをご覧ください)
そして、順次求めた、1、3、7、15、31・・・という数の様子が、「どうも、どこかで見たことがある並びだぞ?」ということにも気づきました。
さらにその秘密が、どうやら「2倍」にあるらしいということを嗅ぎつけたY君は、以前、2進数を勉強した時に、2^nという数がよく出てきたことを思い出しました。そうです。
Y君の答案です。