第 4 章 ラッキーパズルの凸配置の総数 22
4.3 敷き詰め不可能な凸多角形 26 種類
4.3.3 その他の場合
ここまでに，ある一つのパーツのみの配置可能性を考えるだけで14種類の凸多角形に 対して不可能性を示すことができた．残りの12種類（図4.7）については複数個のピース の配置可能性を考える必要がある．それぞれについて以下で不可能性を証明していく．
多角形Sが敷き詰め可能であるとき，その外周上の辺はあるピースの辺か，または複 数のピースの辺の和集合で被覆される．ラッキーパズルのピースで長さ1の辺はP5にし かないため，以下が成り立つ．
補題 4.3.2. Sの外周が長さ1の辺Lを持つとき，任意のSの敷き詰めにおいてLはP
S11
S12
S13 S14
S15 S16
S17
S18 S9
S10
S20 S19
図 4.7: 残りの12種類の凸多角形
■ S9の不可能性
S9の敷き詰め不可能性を示すために，まずP2の置き方を考える．対称性を考慮すると，
補題4.3.1を満たす置き方は図4.8の7通りのみである．各場合について不可能性を示す．
(a) (b) (c) (d)
(e) (f) (g)
図 4.8: S9へのP2の置き方（7通り）
☆ (c), (d), (e)の不可能性: 黄色のタイルを埋めることができない．
☆ (a)の不可能性: 左上の9タイルからなる部分を考える．P2以外のピースで合計タイ ル数が9となるのは，P3（6タイル）とP5（3タイル）の組合せのみ．この部分へのP3の 置き方で補題4.3.1を満たすものは，対称性を考慮すると1通りしかないが，残りがタイ ル数1の部分とタイル数2の部分に分断されてしまう．
☆ (b)の不可能性: 左に15タイルからなる部分があるが，P2以外のピースで合計タイ ル数が15となる組合せはない．
☆ (f )の不可能性: 右の19タイルからなる部分を考える．P2以外のピースで合計タイ ル数が19となるのは，P1（10タイル）とP3とP5の組合せのみ．この部分の唯一の2×2 正方形はP1によって被覆されるが，残った部分にP3を置くことができない．
☆ (g)の不可能性: 右の部分には2×2正方形がないので，P1は左の部分に置かれる．し かし，P1をどの向きで置いても，タイル数3未満の部分が残されてしまう．
■ S10の不可能性
S10の敷き詰め不可能性を示すために，P2の置き方を考える．対称性を考慮すると，補
題4.3.1を満たす置き方は図4.9の7通りのみである．各場合について不可能性を示す．
(a) (b) (c) (d)
(e) (f) (g)
図 4.9: S10へのP2の置き方（7通り）
☆ (a)の不可能性: 左上の8タイルからなる部分を考える．タイル数8となるのはP4を 二つ使う組合せのみであるが，形が合わず置くことができない．
☆ (b)の不可能性: 左の部分には2×2正方形がないので，P1は右の部分に置かれる．
しかし，P1をどの向きで置いても，タイル数3未満の部分が残されてしまう．
☆ (d)の不可能性: 右下はP4を置くしかない．次に，P1をどこに置くか決める．これ には，図4.10に示す11通りがある．図中で水色で示されているのは，P1を置いた後に バックトラックで確定するピースである．すべての置き方で，埋める手段がない黄色のタ イルができている．
図 4.10: (d)へのP1の追加の仕方（11通り）
☆ (e)の不可能性: さらにP1を追加することを考えると，その方法は図4.11の3通り．
左の二つは，黄色で示したタイルを埋める手段がない．三つ目の置き方では，タイル数4 の部分ができるのでそこにはP4を置くしかない．ここまで進めたものを(e-1)とする．
⇒
(e-1)
図 4.11: (e)へのP1の追加の仕方（3通り）
次に，(e-1)に二つ目のP4を追加する．その方法は図4.12の8通り．図中で水色で示さ
れているのは，二つ目のP4を置いた後に確定するピースである．全ての置き方で，埋め ることのできない黄色のタイルができている．
図 4.12: (e-1)へのP4の追加の仕方（8通り）
☆ (f )の不可能性: さらにP1を追加することを考えると，その方は図4.13の5通り．そ れぞれ，黄色で示したタイルを埋める手段がない．
図 4.13: (f)へのP1の追加の仕方（5通り）
■ S11の不可能性
S11の敷き詰め不可能性を示すために，P2の置き方を考える．対称性を考慮すると，補
題4.3.1を満たす置き方は図4.14の7通りのみである．各場合について不可能性を示す．
(a) (b) (c) (d)
(e) (f) (g)
図 4.14: S11へのP2の置き方（7通り）
☆ (b)の不可能性: 右上の唯一の2×2正方形に合わせてP1を置くしかないが，どちら の向きに置いても，P2の右上にタイル数1の部分が残ってしまう．
☆ (c)の不可能性: 2×2正方形がないので，P1を置くことができない．
☆ (g)の不可能性: 左の部分は外周に長さ1の辺を2本，右の部分は外周に長さ1の辺 を1本を持つ．また，左側の長さ1外周辺2本は離れているため，同一のP5に含まれな
い．補題4.3.2より，P5が三つ必要であることになる．
■ S12の不可能性
S12の敷き詰め不可能性を示すために，P2の置き方を考える．対称性を考慮すると，補
題4.3.1を満たす置き方は図4.18の12通りである．各場合について不可能性を示す．
☆ (b), (c), (d), (f ), (g), (j), (k), (l)の不可能性: 図中の黄色タイルを埋めることが できない．
☆ (a), (i)の不可能性: 唯一の2×2正方形に合わせてP1を置くしかないが，どの向き
に置いてもP2の右上にタイル数1の部分が残ってしまう．
☆ (h)の不可能性: 2×2正方形がないので，P1を置くことができない．
☆ (e)の不可能性: 図4.16より，P1 の置き方は9通り存在するが，(e)-2, (e)-3, (e)-4, (e)-5, (e)-6, (e)-7, (e)-9の置き方では黄色のタイルを埋めることができない．
図4.17よりP3の置き方は，(e)-1には6通り，(e)-8には4通り存在するが，いずれの 場合も黄色のタイルを埋めることができない．
(a) (b) (c) (d)
(e) (f) (g) (h)
(i) (j) (k) (l)
図 4.15: S12へのP2の置き方（12通り）
(e)-5
(e)-1 (e)-2 (e)-3
(e)-4 (e)-6
(e)-8
(e)-7 (e)-9
図 4.16: S12へのP1の置き方（9通り）
図 4.17: S12へのP3の置き方
■ S13の不可能性
S13の敷き詰め不可能性を示すために，P2の置き方を考える．対称性を考慮すると，補
題4.3.1を満たす置き方は図4.18の10通りである．各場合について不可能性を示す．
☆ (b), (c), (e), (f ), (g), (h), (i), (j)の不可能性: 図中の黄色タイルを埋めることが できない．
☆ (d)の不可能性: 残りの部分には2×2正方形がないので，P1を置くことができない．
☆ (a)の不可能性: 補題4.3.2より，一つのP5の置き方は図4.19の4通りであるが，埋 めることができない黄色のタイルが現れないのは図中の一番左の置き方のみである．
このとき，P1の置き方は図4.20の8通りであるが，(a)-1から(a)-7の場合は黄色タイ ルを埋めることができず，(a)-8の場合は，残った部分の正方形タイルは4枚であるのに 対し，残ったピースの正方形タイルの合計は5枚であることから，補題4.3.1より，残っ た部分を埋めることはできない．
■ S14の不可能性
S14の敷き詰め不可能性を示すために，P5の置き方を考える．補題4.3.2より，二枚の P5は左右に一つずつ存在する長さ1の辺を被覆するのに使われる．左側の長さ1の辺を 被覆する置き方に着目すると，P5の置き方は図4.21の4通り考えられるが，もう一枚の P5が右側の長さ1の辺に置かれることを考慮すると，図中の黄色のタイルを埋められな
(a) (b) (c) (d)
(e) (f) (g) (h)
(i) (j)
図 4.18: S13へのP2の置き方（10通り）
図 4.19: S13へのP5の置き方（4通り）
(a)-1 (a)-2 (a)-3 (a)-4
(a)-5 (a)-6 (a)-7 (a)-8
図 4.20: S13へのP1の置き方（8通り）
いので，P5の向きは一通りである．また，対称性より同様の議論が右側のP5にも成り立 つので，二枚のP5の置き方は一意に決まる．
図 4.21: S14へのP5の置き方
次に，P2の置き方を考える．対称性を考慮すると，補題4.3.1を満たす置き方は図4.22 の8通りである．各場合について不可能性を示す．
☆ (b), (c), (d), (e), (f ), (g), (h)の不可能性: 図中の黄色タイルを埋めることができ ない．
☆ (a)の不可能性: P5の置き方は図4.23の9通り考えられるが，(a)-1, (a)-2, (a)-3, (a)-4,
(a)-5, (a)-6, (a)-9の置き方では図中の黄色タイルを埋めることができない．
(a)-7の場合，一つのP4 の置き方は図4.23の一通りに決まるが，このとき黄色のタイ
ルを埋められない．
(a)-8の場合，一つのP3の置き方は図4.25の4通り存在するが，いずれの場合も黄色の
タイルを埋められない．
■ S15の不可能性
補題4.3.2より，右側の長さ1の辺を被覆するために一枚のP5を使用する．
S15の敷き詰め不可能性を示すために，P2の置き方を考える．補題4.3.1を満たす置き 方は図4.26の20通りである．各場合について不可能性を示す．
☆ (b), (d), (f )-(h), (j), (m)-(p), (r), (t)の不可能性: 図中の黄色タイルを埋めるこ とができない．
(a) (b) (c) (d)
(e) (f) (g) (h)
図 4.22: S14へのP2の置き方（8通り）
(a)-1 (a)-2 (a)-3
(a)-5 (a)-6 (a)-7
(a)-4
(a)-9 (a)-8
図 4.24: S14へのP4の置き方
(a)-8
図 4.25: S14へのP3の置き方
☆ (l), (q), (s)の不可能性: 2×2正方形がないので，P1を置くことができない．
☆ (a), (e)不可能性: P5 の置き方は図4.27のそれぞれ4通り存在するが，どちらも図
の最も左の置き方以外では黄色のタイルを埋められない．
このとき，もう一枚のP5は補題4.3.2より，左側の長さ1の辺を被覆するために使用さ れるが，右側のP5の下の黄色のタイルを埋められるピースは残っていない．
☆ (c)の不可能性: 右側の長さ1の辺を被覆するP5の置き方は4通り存在するが，埋め られないタイルが出ないような置き方は1通りに決まる．また，左側の長さ1の辺を被覆 するためにもう一枚のP5が使用される．さらに，上の4タイルの部分を埋めるために一 枚のP4が使用される．このとき，P1の置き方は図4.29の7通り存在するが，いずれの場 合も黄色のタイルを埋められない．
☆ (n)の不可能性: 右側の長さ1の辺を被覆するP5の置き方は4通り存在するが，埋め られないタイルが出ないような置き方は1通りに決まる．このP5の下の部分を埋めるた めに，もう一枚のP5の置き方も決まる．さらに，P2と一枚目に置いたP5に挟まれた部 分を埋めるために一枚のP4の置き方も決まる．このとき図4.30の黄色のタイルを埋めら れない．
☆ (i)の不可能性: P1の置き方は図4.31の9通り存在する．
(a) (b) (c) (d)
(e) (f) (g) (h)
(i) (j) (k) (l)
(m) (n) (o) (p)
図 4.27: S15への一枚のP5の置き方
(a)
(e)図 4.28: S15への二枚のP5の置き方
(c)
図 4.29: (c)へのP1の置き方
図 4.30: (n)へのP5,P4の置き方
(i-1) (i-2) (i-3) (i-4)
(i-5) (i-6) (i-7) (i-8)
(i-9)
図 4.31: (i)へのP1の置き方
(i)-2, (i)-4, (i)-5, (i)-9の場合は黄色のタイルを埋められない．(i)-3の場合は，右側の7 タイルの部分を埋めるピースの組み合わせは存在しない．(i)-7の場合は，上側の6タイ ルの部分を埋めるピースの組み合わせは存在しない．(i)-1と(i)-8の場合はP3の置き方が 図4.32の通りそれぞれ2通りずつ存在するが，いずれの場合も黄色のタイルを埋められ ない．(i)-6の場合は，P3の置き方は図4.33の5通り存在するが，右上の置き方では7タ
図 4.32: (i)-1, (i)-8へのP3の置き方
イルの部分を埋めるピースの組み合わせが存在せず，その他の場合は黄色のタイルを埋め られない．
☆ (k)の不可能性: P2の右側の1タイルの部分を埋めるために一枚のP5の置き方が決 まり，それによって二枚目のP5の置き方も決まる．さらに，二枚のP5が使われたことか ら，残った部分の上部を埋めるために一枚のP4の置き方も決まる．このとき，P1の置き 方は図4.34の7通り存在するが，図の左上の置き方ではP3を置くことが出来ず，その他 の場合は黄色のタイルを埋められない．
■ S16の不可能性
S16の敷き詰め不可能性を示すために，P2の置き方を考える．対称性を考慮すると，補
題4.3.1を満たす置き方は図4.35の13通りである．各場合について不可能性を示す．
☆ (a)の不可能性: 左上の8タイルからなる部分を埋めるピースは二つのP4に限られる