Scratchで学ぶ！ポリオミノ・パターンの世界～数学編 その２
引き続き, 私が先頃リリースしたScratchアプリP.T.P.S. のアルゴリズムが働くメカニズムに迫っていこうと思います.
単一ポリオミノの平行移動による敷詰め問題
ではここからは,
「ポリオミノを一種類だけ使って, そのポリオミノの平行移動により平面を埋め尽くすにはどうすればいいか？」
というアルゴリズムの本丸に着手しようと思います. アルゴリズムではキャンバスという限られた領域を相手にしていましたが, その制限を取っ払って考えることにします. つまりそもそもオリジナルの平行移動のみで平面全体を埋め尽くすにはどうすればいいのかを考えます. その場合（キャンバスという限られた領域ではなく）平面全体を埋め尽くす必要があるので, その方法は有限回で必ず終わる手順というわけではもちろんありません.
なお, その方法が分かってしまえばそのタイリング模様のどの部分が繰り返しパターンになっているのか判別するのは割と簡単なので, そのことに関する証明は割愛しました.
整数の順序対全体の直和分割
では実際どうやるのかを数学的に考察したいと思います. まず整数の順序対全体の集合$${\Z^2}$$を考えます. この$${\Z^2}$$というのは, 整数全体の集合$${\Z}$$について, $${\Z}$$と$${\Z}$$の直積のことであり, $${\Z^2=\lbrace(x,y) \vert x,y∈\Z\rbrace}$$と定義されます. 私たちの目標は$${\Z^2}$$に対して, $${\Z^2}$$の直和分割を与えることにあるのですが, 進め方としては, 次のようにします.
結果20230707-1：
$${m}$$を$${m≥2}$$である任意の整数とし, $${\lvert O \rvert = m}$$である$${\Z^2}$$の任意の部分集合を$${O}$$とする. 集合$${M}$$を$${M = \lbrace 0,1, \dots ,m-1 \rbrace}$$とする. すべての$${(i,j)∈\Z^2}$$について, 関数$${f_{i,j}:\Z^2→M}$$を, すべての$${(x,y)∈\Z^2}$$に対して, $${f_{i,j}(x,y)=(ix+jy) \mod m}$$と定義する. すべての$${(i,j)∈\Z^2}$$について, 集合$${S_{i,j}}$$を$${S_{i,j}=\lbrace(x+i,y+j)∈\Z^2 \vert (x,y)∈O \rbrace}$$と定義する.
このとき, ある整数$${a,b}$$が存在して, $${f_{a,b}}$$の$${O}$$への制限$${g:O→M}$$が全単射だと仮定すると, 集合$${T}$$, ただし$${T=\lbrace (x,y)∈\Z^2 \vert ax+by≡0 \pmod m \rbrace}$$により, 次の$${(1),(2)}$$が成り立つ.
$${(1)}$$ 任意の$${(x,y),(i,j)∈\Z^2}$$について, $${(i,j)∈T}$$のとき, かつそのときに限り$${f_{a,b}(x,y)=f_{a,b}(x+i,y+j)}$$.
$${(2)}$$ $${\Z^2 = ∐_{(i,j)∈T}S_{i,j}}$$ .
証明：
始めに, $${(1)}$$から示す. $${(x,y)}$$と$${(i,j)}$$を$${\Z^2}$$の任意の元とする. $${(i,j)∈T}$$を仮定したとき, $${T}$$の定義から$${ai+bj≡0 \pmod m}$$なので,
$$
f_{a,b} (x,y)=(ax+by) \mod m
≡ax+by=ax+by+0 \\
≡ax+by+(ai+bj)=a(x+i)+b(y+j) \\
≡(a(x+i)+b(y+j)) \mod m
=f_{a,b} (x+i,y+j) \pmod m
$$
が成立する. ただし, $${f_{a,b} (x,y),f_{a,b} (x+i,y+j)∈M= \lbrace 0,1,⋯,m-1\rbrace}$$であることから, よって$${f_{a,b} (x,y)=f_{a,b} (x+i,y+j)}$$となる. 一方で, $${f_{a,b} (x,y)=f_{a,b} (x+i,y+j)}$$を仮定すれば,
$$
ax+by≡(ax+by) \mod m
=f_{a,b} (x,y)
=f_{a,b} (x+i,y+j) \\
=(a(x+i)+b(y+j)) \mod m
≡a(x+i)+b(y+j) \\
=ax+by+(ai+bj) \pmod m
$$
であり, $${ax+by≡ax+by+(ai+bj) \pmod m}$$が得られた. 両辺から$${ax+by}$$を引くことで, $${0≡ai+bj \pmod m}$$を得る. したがって$${T}$$の定義により$${(i,j)∈T}$$が成立する.
では次に, $${(2)}$$を示す. まず$${i=0,j=0}$$のときは, $${(i,j)∈\Z^2}$$かつ
$$
ai+bj=a \cdot 0+b \cdot 0=0≡0 \pmod m
$$
なので, $${T}$$の定義により$${(i,j)∈T}$$である. したがって$${T}$$は空ではない. 次に, すべての$${(i,j)∈T}$$について, $${S_{i,j}}$$が空でないことを確認する. $${(i,j)}$$を$${T}$$の任意の元とする. $${O}$$は空ではないので, ある$${(x,y)∈O}$$により, $${(x,y)∈\Z^2}$$かつ$${(i,j)∈\Z^2}$$だから, $${(x+i,y+j)∈\Z^2}$$である. すると$${S_{i,j}}$$の定義により$${(x+i,y+j)}$$は$${S_{i,j}}$$の元なので, $${S_{i,j}}$$は空ではない.
次に, $${\Z^2 = ⋃_{(i,j)∈T}S_{i,j}}$$であることを示す. まず$${\Z^2 ⊇ ⋃_{(i,j)∈T}S_{i,j}}$$であることを示す. $${(α,β)}$$を$${⋃_{(i,j)∈T}S_{i,j}}$$の任意の元とする. このときある$${(i,j)∈T}$$により$${(α,β)∈S_{i,j}}$$である. $${S_{i,j}}$$は$${\Z^2}$$の部分集合なので, $${(α,β)∈S_{i,j}}$$のときは$${(α,β)∈\Z^2}$$である. したがって$${\Z^2 ⊇ ⋃_{(i,j)∈T}S_{i,j}}$$は成り立つ. 次に, $${\Z^2 ⊆ ⋃_{(i,j)∈T}S_{i,j}}$$であることを示す. $${(α,β)}$$を$${\Z^2}$$の任意の元とする. $${g:O→M}$$は全射なので, ある$${(x,y)∈O}$$によって, $${g(x,y)=f_{a,b} (α,β)}$$が成り立つことになる. したがって合同式を用いると
$$
ax+by≡(ax+by) \mod m
=g(x,y) \\
=f_{a,b} (α,β)
=(aα+bβ) \mod m \\
≡aα+bβ \pmod m
$$
と書ける. $${ax+by≡aα+bβ \pmod m}$$の両辺から$${ax+by}$$を引いて,
$$
0≡aα+bβ-(ax+by)=a(α-x)+b(β-y) \pmod m
$$
を得る. したがって$${(α-x,β-y)∈\Z^2}$$, かつ$${T}$$の定義より$${(α-x,β-y)∈T}$$となる. $${i=α-x,j=β-y}$$とおくと, $${α=x+i,β=y+j}$$, ただし$${(x,y)∈O}$$かつ$${(i,j)∈\Z^2}$$なので, $${S_{i,j}}$$の定義より
$$
S_{i,j}∋(x+i,y+j)=(α,β)
$$
が成り立つ. すると, ある$${(i,j)∈T}$$により$${(α,β)∈S_{i,j}}$$だから, したがって$${(α,β)∈⋃_{(i,j)∈T}S_{i,j}}$$ であり, このことは$${\Z^2 ⊆ ⋃_{(i,j)∈T}S_{i,j}}$$を意味する.
次に, 任意の$${(i,j),(i',j')∈T}$$について, $${(i,j)≠(i',j')}$$のときは$${S_{i,j}∩S_{i',j' }=\empty}$$であることを示す. では, $${(i,j)}$$と$${(i',j')}$$を$${T}$$の元とし, $${(i,j)≠(i',j')}$$を仮定する. 背理法で進めることにして, 仮に$${S_{i,j}∩S_{i',j' }≠\empty}$$だったとする. このとき, $${S_{i,j}∩S_{i',j' }}$$の元$${(α,β)}$$が存在する. $${(α,β)∈S_{i,j}}$$なので, $${S_{i,j}}$$の定義より$${(α,β)=(x+i,y+j)}$$である$${O}$$の元$${(x,y)}$$が存在する. 同様に$${(α,β)∈S_{i',j'}}$$なので, $${S_{i',j'}}$$の定義より$${(α,β)=(x'+i',y'+j')}$$である$${O}$$の元$${(x',y')}$$が存在する. $${(i,j)}$$は$${T}$$の元だから$${0≡ai+bj \pmod m}$$である. すると式の両辺に$${ax+by}$$を足すことで
$$
ax+by≡ai+bj+(ax+by)=a(x+i)+b(y+j)=aα+bβ \pmod m
$$
を得る. 同様にして, $${(i',j')}$$は$${T}$$の元だから$${0≡ai'+bj' \pmod m}$$であり, 式の両辺に$${ax'+by'}$$を足すことで
$$
ax'+by'≡ai'+bj'+(ax'+by' )
=a(x'+i' )+b(y'+j' ) \\
=aα+bβ \pmod m
$$
を得る. したがって
$$
g(x,y)=(ax+by)\mod m
≡ax+by
≡aα+bβ \\
≡ax'+by'
≡(ax'+by')\mod m
=g(x',y') \pmod m
$$
が成り立つ. すると, $${g(x,y),g(x',y')∈M = \lbrace 0,1, \dots ,m-1 \rbrace}$$であることから, よって$${g(x,y)=g(x',y')}$$となる. $${g:O→M}$$は単射なので, このとき$${(x,y)=(x',y')}$$が成り立つ.
$$
x+i=α=x'+i'
$$
より,
$$
i=x+i-x=x'+i'-x'=i'
$$
を得る. 同様に
$$
y+j=β=y'+j'
$$
より,
$$
j=y+j-y=y'+j'-y'=j'
$$
を得る. よって$${(i,j)=(i',j')}$$となり矛盾する.
$${\blacksquare}$$
この記事が気に入ったらサポートをしてみませんか？