長方形ポリオミノの色分け問題～数学編（全三回）その３

補題1について

結果20230928-1の証明では, 次の補題$${1}$$を頻繁に呼び出し使っています. その証明については前記事を参照してください.

補題$${1}$$. $${m}$$を$${2}$$以上の任意の整数, $${a}$$を任意の整数, ただし$${a≠0}$$とする. $${m}$$と$${a}$$の最大公約数を$${d}$$, ただし$${m>d}$$とする. 集合$${A}$$を$${A=\{0,a,2a,\dots,(\frac{m}{d}-1)a\}}$$と定義する. このとき, 任意の$${x,y∈A}$$について, $${x≠y}$$のときは$${x\not\equiv y \pmod m}$$.

その他の利用した結果

証明では次のような結果も利用しています.

結果$${1}$$. 有限集合$${A}$$と$${B}$$の直積$${A \times B}$$について, $${\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert }$$が成り立つ.

結果$${2}$$. 同時に$${0}$$ではない整数$${a}$$と$${b}$$および, $${a}$$と$${b}$$の最大公約数$${d}$$について, $${c}$$が$${a}$$と$${b}$$の公約数なら$${c}$$は$${d}$$を割り切る.

長方形ポリオミノの色分け問題

それでは, 結果20230928-1の証明に移ります.

結果20230928-1（長方形ポリオミノの色分け問題）:
$${m}$$を$${2}$$以上の任意の整数とする. $${a}$$と$${b}$$を任意の整数, ただし$${a≠0}$$とする. $${a}$$と$${b}$$の最大公約数を$${d}$$とする. $${m}$$と$${a}$$の最大公約数を$${d_1}$$とする. $${m}$$と$${d}$$は互いに素であると仮定する. 集合$${G}$$を$${G=\{(x,y)∈{\Z}^2 \colon 0≤x<\frac{m}{d_1} ,0≤y<{d_1} \}}$$と定義する. するとこのとき,
$${\lvert G \rvert =m}$$かつ, 任意の$${(x,y),(x\rq,y\rq)∈G}$$について, $${(x,y)≠(x\rq,y\rq)}$$のとき$${ax+by \not\equiv ax\rq+by\rq \pmod m}$$が成り立つ.

証明:
始めに, $${\lvert G \rvert =m}$$を示す. 集合$${S_1}$$,$${S_2}$$を$${S_1=\{0,1,\dots,\frac{m}{d_1} -1\}}$$,$${S_2=\{0,1,\dots,{d_1}-1\}}$$と定義する. このとき, $${\lvert S_1 \rvert =\frac{m}{d_1}}$$ かつ$${\lvert S_2 \rvert=d_1}$$である. 有限集合$${S_1}$$,$${S_2}$$について, $${G=S_1 \times S_2}$$なので,

$$
\lvert G \rvert =\lvert S_1 \times S_2 \rvert = \lvert S_1 \rvert \cdot \lvert S_2 \rvert =\frac{m}{d_1} \cdot d_1=m
$$

が成り立つ .
次に, 任意の$${(x,y),(x\rq,y\rq)∈G}$$について, $${(x,y)≠(x\rq,y\rq)}$$ならば$${ax+by \not\equiv ax\rq+by\rq \pmod m}$$が成り立つことを示す. そのために, 集合$${A_1}$$および集合$${A_2}$$を次のように定義した上で議論を進める.

$$
A_1=\{0,a,2a,\dots,(\frac{m}{d_1} -1)a\}, \\
A_2=\{0,b,2b,\dots,({d_1}-1)b\}.
$$

それでは, $${(x,y)}$$,$${(x\rq,y\rq)}$$を$${G}$$の任意の要素とし, $${(x,y)≠(x\rq,y\rq)}$$を仮定する.

始めに$${d_1=1}$$を仮定する. このときは$${G}$$の定義により, $${ y=0=y\rq}$$である. すると仮定より$${(x,y)≠(x\rq,y\rq)}$$なので, $${x≠x\rq}$$となる. すると, $${a≠0}$$であることから, $${ax≠ax\rq}$$である. $${ax}$$および$${ax\rq}$$は$${A_1}$$の要素なのだが, $${ax≠ax\rq}$$を仮定すると, 補題$${1}$$より$${ax\not\equiv ax\rq \pmod m}$$が成り立つ. $${ax≡ax+0=ax+by \pmod m}$$かつ $${ax\rq≡ax\rq+0=ax\rq+by\rq \pmod m}$$なので, $${ax+by\not\equiv ax\rq+by\rq \pmod m}$$となる.

では次に, $${d_1>1}$$の場合を考察する. このとき, $${b≠0}$$であることを背理法によって示す. もし仮に$${b=0}$$だとすると,

$$
d=\gcd(a,b)=\gcd(a,0)=\lvert a \rvert
$$

が成立するが, するとこのとき,

$$
\gcd(m,d)=\gcd(m,\lvert a \rvert)=\gcd(m,a)=d_1>1
$$

となり$${m}$$と$${d}$$は互いに素であるとする仮定と矛盾する. よって$${b≠0}$$は成り立つ. 続いて, $${d_1}$$と$${b}$$が互いに素であることを示す. $${d_1}$$と$${b}$$の最大公約数を$${d_2}$$とする. $${d_2 \vert d_1}$$かつ, $${d_1 \vert a}$$だから, よって$${d_2 \vert a}$$である. したがって$${d_2}$$は$${a}$$と$${b}$$の公約数である. よって$${d_2}$$は$${a}$$と$${b}$$の最大公約数$${d}$$を割り切る. 一方では, $${d_2 \vert d_1}$$かつ, $${d_1 \vert m}$$だから, よって$${d_2 \vert m}$$である. したがって, $${d_2}$$は$${d}$$と$${m}$$の公約数である. 仮定により$${d}$$と$${m}$$の最大公約数は$${1}$$なので, よって$${d_2=1}$$であることが判明した.

場合$${1}$$. $${x=x\rq}$$であると仮定する. すると仮定より$${(x,y)≠(x\rq,y\rq)}$$だから, $${y≠y\rq}$$が要請される. $${b≠0}$$であるので, $${by≠by\rq}$$が成立することになる. ところで, $${by}$$および$${by\rq}$$は$${A_2}$$の要素なのだが, $${d_1}$$と$${b}$$が互いに素であること,および$${\frac{d_1}{1}=d_1}$$であることに注意すると, 補題$${1}$$より, $${by,by\rq∈A_2}$$に対して, $${by≠by\rq}$$のときは$${by\not\equiv by\rq \pmod {d_1}}$$が成立することが分かる. $${d_1}$$は$${m}$$の約数なので, よって$${by\not\equiv by\rq \pmod m}$$は成り立つ. このとき$${ax+by\not\equiv ax\rq+by\rq \pmod m}$$であることは背理法で示す. では仮に, $${ax+by≡ax\rq+by\rq \pmod m}$$が成立するとする. $${x=x\rq}$$だから, $${ax≡ax\rq \pmod m}$$であり, よって$${by≡by\rq \pmod m}$$が導ける. しかしこれは矛盾なので, したがって$${ax+by\not\equiv ax\rq+by\rq \pmod m}$$は成り立つ.

場合$${2}$$. では次に, $${x≠x\rq}$$であると仮定する. このとき, $${m=d_1}$$は成立しない. なぜなら, もし仮に$${m=d_1}$$だったとすると, $${0≤x<\frac{m}{d_1} =1}$$かつ, $${0≤x\rq<\frac{m}{d_1} =1}$$より, $${x=0=x\rq}$$となり, 矛盾する. よって, $${m>d_1}$$であると結論できる. なおかつ, $${a≠0}$$であることから, $${ax≠ax\rq}$$が成立している. するとこのとき, $${ax,ax\rq∈A_1}$$, ただし$${ax≠ax\rq}$$に対して, 補題$${1}$$より$${ax\not\equiv ax\rq \pmod m}$$が成立する. そこでまずは $${y=y\rq}$$だと仮定する. よって$${by≡by\rq \pmod m}$$である. このとき, $${ax+by\not\equiv ax\rq+by\rq \pmod m}$$であることは先程と同様にして容易に示せる. 続いて, $${y≠y\rq}$$を仮定する. $${b≠0}$$だから, このときは$${by≠by\rq}$$が成立する. そして補題$${1}$$より, $${by,by\rq∈A_2}$$に対して, $${by≠by\rq}$$のときは$${by\not\equiv by\rq \pmod {d_1}}$$が成立する. $${d_1}$$は$${a}$$の約数なので,

$$
by≡ax+by \pmod {d_1}
$$

かつ,

$$
by\rq≡ax\rq+by\rq \pmod {d_1}
$$

が成り立つ. したがって$${ax+by\not\equiv ax\rq+by\rq \pmod {d_1}}$$である. $${d_1 \vert m}$$なので, よって$${ax+by\not\equiv ax\rq+by\rq \pmod m}$$が成立する. $${\blacksquare}$$