ペンシルズの自作問題をここに載せる。
「ペンシルズ」はニコリの季刊158号（2017年春）のオモパコーナーで現れたパズル。
「ペンシルズ」のルール








ペンシルズを作る際は数を３以上の奇数に分解する組み合わせの数が重要になる。
整数を奇数に分割する組み合わせの数はOEISのA9で、
整数を相異なる数に分割する組み合わせの数と等しい（オイラーの恒等式：同じ数を２個ずつ足し合わせれば対応が得られる）。
３以上の奇数に分割する組み合わせの数は、その数から、１を含む分割の組み合わせの数を引けば良いのでA9(n)-A9(n-1)となる。
n=1,2,3,...,20までの数列は0,0,1,0,1,1,1,1,2,2,2,3,3,4,5,5,6,8,8,10となる。
表出なしで唯一解の空間を作りたい場合、３を含む組み合わせも除く必要がある。
上の数列からさらに３ずらした数列を引けばよく、n=5,6,7,...,20までの数列は1,0,1,0,1,1,1,1,1,2,2,2,2,3,3,4となる。
具体的に書くと、

n	3を含まない組み合わせ	3を含む組み合わせ
5	(5)
6		(3,3)
7	(7)
8		(3,5)
9	(9)	(3,3,3)
10	(5,5)	(3,7)
11	(11)	(3,3,5)
12	(5,7)	(3,9),(3,3,3,3)
13	(13)	(3,5,5),(3,3,7)
14	(5,9)(7,7)	(3,11),(3,3,3,5)
15	(15)(5,5,5)	(3,5,7),(3,3,9),(3,3,3,3,3)
16	(5,11)(7,9)	(3,13),(3,3,5,5),(3,3,3,7)
17	(17)(5,5,7)	(3,5,9),(3,7,7),(3,3,11),(3,3,3,3,5)
18	(5,13)(7,11)(9,9)	(3,15),(3,5,5,5),(3,3,5,7),(3,3,3,9),(3,3,3,3,3,3)
19	(19)(5,5,9)(5,7,7)	(3,5,11),(3,7,9),(3,3,13),(3,3,3,5,5),(3,3,3,3,7)
20	(5,15)(5,5,5,5)(7,13)(9,11)	(3,17),(3,5,5,7),(3,3,5,9),(3,3,7,7),(3,3,3,11),(3,3,3,3,3,5)

組み合わせは漸化式の要領で網羅できる。
[2017/12/24追記]黄色い烏様から間違いのご指摘があったため修正を行った。
組み合わせが複数ある場合は部屋の形を工夫すれば唯一解にできることがある。
表出なし５マスで唯一解となるのは以下の３種類のみ（Ｐ、Ｎ、Ｌペントミノ）。

７マスの場合は以下の９通り。

１０マスの場合、5+5と分解できる場合に唯一解になるケースがある。Ｐペントミノ２つの場合は以下に挙げる３２通り。

※リストは手作業で列挙しているので間違いがある可能性がある。間違いを見つけた場合はコメントにて指摘いただきたい。
[2017/12/24追記]黄色い烏様から複数解パターンのご指摘があったため修正を行った。
[2017/12/28追記]末尾の４種類が抜けていたので追加した。
この調子で全て列挙しても良いが、面倒なので列挙はここまでにしておく。
上の問題はＰペントミノとＮペントミノの組み合わせを用いている。



今まで問題の画像を作成していた自作アプリケーションはCUIベースで、どうにも使い勝手が悪かったため、今回はInkscapeでの作成を試みた。レイヤー機能は当然として、グリッドを定義したりスナップしたりできるので配置は想定より効率良くできた。「想定より効率良い」と言ってもスナップ機能が悪さすることもあり、また、配置のためにわざわざオブジェクトをコピー＆ペーストする必要があり、マウスを動かす労力も必要になるため、今までの方法とどちらが良いかは判断しかねる。ただここであまり試行錯誤しても、ぱずぷれに実装されれば間違いなくそちらを使うことになると思われるので、あまり最適化しないことにする。

下図のように三つ又または四つ又の部分から長さ１と長さ２の枝が出る構造は、常に解なしになる。上の問題はこの原理を使っている。

関連して見つけた下図のようなラダー構造は、常に唯一解になる。

これによって、総マス数が5の倍数（5n, n∈{1,2,3,...}）のフィールドで唯一解のものが構成できることが示された。
一方で、下図のラダー構造も唯一解になる。

したがって総マス数が7の倍数（7n, n∈{1,2,3,...}）のフィールドでも唯一解のものが構成できることが示された。
５マスタイプのラダーと７マスタイプのラダーをつなげることもできるので、一般に5m+7nが実現できることになる（m∈{0,1,2,...},n∈{0,1,2,...}）。5と7は互いに素だが、負の値が許されないために実現できない数が生じる。具体的には1,2,3,4,6,8,9,11,13,16,18,23が含まれないことになる。総マス数12以下は既に見てきたので、総マス数13以上に注目すると13,16,18,23だけが候補として残る。これらの総マス数を持つフィールドで唯一解の構造を作れるかどうかを考える。

総マス数13の唯一解空間は作れない；(13)が常に(7,3,3)で分解できてしまう。
16マスの唯一解空間は作れない；16マスの分割が(5,11)(7,9),(3,13),(3,3,5,5),(3,3,3,7)の５種類のみであることを既に示しており、唯一解となるためには(5,11)または(7,9)で分解できる必要があるが、9マスのブロックと11マスのブロックは解が存在するなら常に複数解になることがわかっているためである。
18マスの唯一解空間も作れない；18マスの3を含まない分割は(5,13)(7,11)(9,9)の３つのみで、既にみたように9マス、11マス、13マスの唯一解空間が作れないためである。
23マスの唯一解空間も作れない；23マスの3を含まない分割は(23),(5,5,13),(5,7,11),(5,9,9),(7,7,9)の５つのみで、9マス、11マス、13マスは不可なので唯一解にするには分割は(23)である必要があるが、(23)は常に(5,3,3,3,3,3,3)と分解できるためである。

以上から、結局5m+7nで表せない総マス数の空間は唯一解にできないことが分かった。具体的に書き下すと、総マス数が1,2,3,4,6,8,9,11,13,16,18,23のいずれかの時そしてその時に限り、表出なしで唯一解にできないとわかった。

中空構造で表出なし唯一解の例：






私は飽きの早い性格なのもあり、最近はあまり議論をしていなかったが、また少し興味のある問題が出てきたのでここで考察する。
既に総マス数が5m+7nで表せる時に限り、表出なしで唯一解の形状にできることを示した。逆に、ある総マス数の空間が表出なしで唯一解の場合、その解は、必ず5マスのブロックと7マスのブロックで構成されることになることが証明できる。なぜならば、その解が３マスブロックや９マスブロックを含む場合は明らかに複数解であり、１１マス以上の単体ブロックは３マスブロック２つと（総マス数-６）マスブロックに分解できるためである。したがって表出なし唯一解空間は本質的に5マスブロックと7マスブロックの集まりで構成されるもので全てである。
よくよく考えるとこちらの証明の方がはるかに簡単で明快なので、この証明を先にしておけばここまで長い議論は不要だったかもしれない。随分と遠回りをしていたようだ。




当記事の公開日：2017/10/04
当記事の最終更新日：2019/10/19
カテゴリ：自作問題