2015年8月16日日曜日

Hinged dissections of polycubes

Erik D. Demaineらによって書かれた論文に
Hinged Dissections of Polyominoes and Polyforms という問題がある。

論文はこちら
Hinged Dissections of Polyominoes and Polyforms

このうち、Hinged Dissections of Polyominoes は、
オミノ同士を頂点で接続した(Hinged)形を変形させて様々なポリオミノをつくるという問題だ。

オミノは接続された頂点を中心に自由に回転することができるが切り離すことはできない。
そして、オミノ同士をどのように接続させるかによってつくることができるポリオミノは変わってくる。




単位数4の場合、4つのオミノを以下のように接続すると(赤丸が接続箇所)すべてのテトロミノ(5種類)をつくることができる。論文で書かれているのは右側の形のみであるが、これは裏返しせずに鏡像を含めたテトロミノ(7種類)をすべてつくることができる。


また、単位数5の場合、すべてのペントミノ(12種類)をつくれるような接続の仕方はない。10種類をつくれるものが最大のようだ。
(論文ではペントミノ12種類をつくれる形がないことが証明されているのみで、つくれるペントミノの最大種類数についての言及はない)