「どうしても解けなかった数学の練習問題」の編集履歴（バックアップ）一覧に戻る
数学の勉強で昔こんな問題に挑戦したことがあります。
堀江 伸一
3*3*10＾10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。
答えは答えを１０億7だったかそんな数で割った余りを答えよという問題。
１０億段とか１兆段とかそういうちいさな段数でなく10001桁段です。
とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。
上下に出っ張りのはみでた可能な一段全てを用意し、それを二セット作り全組み合わせで２段を作ります。
２段を二つ組み合わせて4段を作り、４段を組み合わせて８段を作ります。
これを10＾10000段の直前まで作り。
10＾10000段を２進数になおしたときあるｎ桁目に１のビットが立ってたら、２^n段を作れた時にそれをどんどんアセンブリしていけば答えが出ます。
細部は覚えてませんが大体この方法で６時間半の計算で答えが出ました。
アセンブルするときに上面の凸凹が512通り位、下面の凸凹が５１２通り、真中の凸凹は結合部の上面が決まれば結合部下面の形が決まるので512通り。
一つ結合するときに512*512*512、必要な段数は10＾10000=2^37000くらいなのでこの結合を３７０００回する必要があります。
512*512*512*37000回の計算です。
実際は上面と下面に制約があるのでもうすこし計算量が落ちると思いますし、当時コードを書いたときは試行錯誤の残るもう少し非効率で多少無駄も入ったコードも書いていた覚えもあります。
数時間かかったのは仕方ないような気もするのですが。
正しいコードを書くと、３０秒で答えが出るそうなのでもっと高度な発想が必要なようです。
