格子パターンの折りたたみ方の数え上げ(3)
折り紙の話。
折り紙の各辺を4等分するようにして折って、
あとは対角線に平行な斜めの線を折ると、次のような格子パターンができます。
さて、この格子の中には「平坦に折りたためるような、折り線のパターン（展開図）」がいくつ隠されているだろうか？
ということを考えて、早2年半。
（2012年5月のブログ）
その数は約2億6千万通り (2014年12月時点の計算)であることがわかりました。
↓こんな感じのものが2億6千個！ いずれも平らに折りたたむことができる。
そうすると、当然気になるのが、
「この約2億6千万通りの展開図を全部折りたたむと、どのような形が出てくるだろうか」
という問題。
私が10年くらい前に開発した、展開図から折った形を計算するソフトである「ORIPA」を改造して、
誤差無しで、ユニークな形を列挙するようにしてくれたのです。
約2億6千万通りの展開図をひたすらORIPAで折る。折った形を保存する。
折る。折った形を保存する。
という計算を60時間かけて実行し、その結果、得られた結論は
13,451個
でした！
こんな感じの形が1万3千個。
展開図は2億6千万通りありますが、「折りたたんだ結果、同じ形になる」という展開図がたくさんあるので、得られる形は少なくなります。
たとえば、異なる1700万以上の展開図が、結果として次の形に折りたたまれました。
次の形は、そんなに単純ではないけど、約960万の異なる展開図から作り出されます。
一方で、次の形になる展開図は唯1つしかありません。
2億6千万通りもある展開図のうちの1つだけが、次の形に折りたたまれます。とてもレア。
（↑ 「この形を折ってみましょう」という問題はとても難しい。）
今回の実験で、
をいろいろ折ることで、約1万3千個の形を折り出すことができることがわかったのです！
さらにさらに、山本君は、得られた形には、どのようなものがあるかを検索するツールを開発しました。
↓ 「だまし舟」の形を入れると、その展開図が出てくる！
↓「かざぐるま」の形も出てくる。
↓でも、無理な形（どうやったって折り出せない形）を入れると、「NOT FOUND」と言われる。
その結果として、アルファベット26文字と数字10文字の形に折りたたまれる展開図を発見しました。
すごい。
展開図には山谷の区別がつけられていないので、実際に折るのはなかなか大変ですが、
確かにアルファベットの形に折りたたまれることは確認済みです。
ということで、次のような格子パターンからは、どんな形が折り出されるだろうか。
という2年越しの問題が解決したのでした。
こんなシンプルなパターンから、アルファベットや数字、その他、たくさんの形（1万3千個）を作りだすことができるのです！
※ 形の全13,451パターン、および検索ツールは、次の山本君のWebページで公開されています。
http://www.npal.cs.tsukuba.ac.jp/~yamamoto_y/
（追記 2015/3/10）
得られた形の数について誤りがありましたので訂正しました。
