組み合わせ爆発のはなし
YouTube 上に公開された
「『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!」
という動画が話題になっている。
http://youtube.com/watch?v=Q4gTV4r0zRs
下の図のようなNxNの格子を用意して、左上のスタート地点から、右下のゴール地点にたどり着くルートの数を数えてみよう、というもの。
この例は3x3の格子。
さて、何通りあるか? ルートは最短ルートである必要はなくて、下から上に向かっても構わない。ただし、ルートは自分自身に交わってはいけない。
3x3の格子の例では、答えは184通りある。
意外とたくさんあることに驚かされる。
では、4x4の場合は?
動画の中では「おねえさん」が手で数えているけど、答えは8,512通り。
5x5の場合は、もはや手で数えるわけにはいかなくなる。動画の中のコンピュータを使って求めた答えは1,262,816通り。
組み合わせ爆発によって、あっというまに場合の数が増えてしまうことがわかる。
動画の中で紹介されていたのは、次の10x10まで。
最後の数字は、動画の中のスーパーコンピューターが25万年かけて導き出した答えだ。
1 | 2 |
2 | 12 |
3 | 184 |
4 | 8,512 |
5 | 1,262,816 |
6 | 575,780,564 |
7 | 789,360,053,252 |
8 | 3,266,598,486,981,642 |
9 | 41,044,208,702,632,496,804 |
10 | 1,568,758,030,464,750,013,214,100 |
もはや桁数が多くて、数としての実感がわかない。
さて、この問題は「Self-Avoiding Walk」として知られている問題で、現在は次のように19x19までの解が知られている。
1 | 2 |
2 | 12 |
3 | 184 |
4 | 8512 |
5 | 1262816 |
6 | 575780564 |
7 | 789360053252 |
8 | 3266598486981642 |
9 | 41044208702632496804 |
10 | 1568758030464750013214100 |
11 | 182413291514248049241470885236 |
12 | 64528039343270018963357185158482118 |
13 | 69450664761521361664274701548907358996488 |
14 | 227449714676812739631826459327989863387613323440 |
15 | 2266745568862672746374567396713098934866324885408319028 |
16 | 68745445609149931587631563132489232824587945968099457285419306 |
17 | 63448146112379639713102975407955244004494439868664806936463693 87855336 |
18 | 17821128408420651298933849466523252751678380657047676559314524 74605826692782532 |
19 | 15233449717048799930807428103192296908994542553232945557760298 66737355060592877569255844 |
Wikipediaによると不可思議はなので、1不可思議を超えるのは70桁を持つ17x17以降ということになる。
奇遇にも、現在求まっている最大の19x19は、ちょうど囲碁の盤面と同じサイズだ。
身近に囲碁盤があれば、ちょっと取り出して眺めてみるといいかもしれない。問題は単純で、可能な経路はすべて1つの囲碁盤に収まるのに、左上のカドから右下のカドまで移動する方法は、ほぼ限りなく存在する。
ちなみに、あの偉大なドナルド・クヌース先生もこの問題に興味を持ち、1995年にN=12のときの解を求めている。
もしも20x20の解を求めることができたら、あなたも歴史に名前を残せるはず。
参考
・Self-Avoiding Walk | Wolfram Math World
http://mathworld.wolfram.com/Self-AvoidingWalk.html
・A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid. | OEIS
http://oeis.org/A007764
関連エントリ
・数列の百科事典 OEIS | 大人になってからの再学習
・無量大数とグラハム数 | 大人になってからの再学習
- 作者: ドナルド・E.クヌース,Donald E. Knuth,有澤誠,青木孝,和田英一
- 出版社/メーカー: アスキー
- 発売日: 2006/01
- メディア: 単行本
- 購入: 2人 クリック: 85回
- この商品を含むブログ (26件) を見る
- 作者: 日比孝之,森毅,野崎昭弘,斎藤正彦
- 出版社/メーカー: 朝倉書店
- 発売日: 1997/02
- メディア: 単行本
- クリック: 1回
- この商品を含むブログを見る