Scratchで学ぶ！ポリオミノ・パターンの世界～数学編 その１
みなさん, こんにちは. C-Watcher開発担当の鈴木です. さて, 今回は数学編と題し私が先頃リリースしたScratchアプリP.T.P.S. のアルゴリズムが働くメカニズムに迫っていこうと思います.
本編を読む前に少なくとも上記のアルゴリズム編を読んでおくことを強くおすすめします. 本編から先に呼んでしまうと, 何をいっているのか皆目見当がつかない事態となってしまうと思います.
必要知識について
大前提として, 本編は数学的な内容を含むとはいえ, 高度な専門知識を要すといった類のものではありません. 数学が得意な高校生向けの探求課題といったところだと思われます. 具体的には, 前半部分「キャンバスの色分け問題」では, もっぱら整数や合同式といった分野の知識を使いました. 一方, 後半部分「単一ポリオミノの平行移動による敷詰め問題」では集合や関数といった知識を使います. なお, 用語や記号の定義で不明なところがあったら, ネットや本で調べるなどして自己解決のほどよろしくお願いします. そういった定義も含めて本編で扱うのはスペースの都合上というか, 筆者の力量からして困難と判断し割愛させていただきました.
キャンバスの色分け問題
では, アルゴリズムにおいて, $${2}$$以上の整数$${m}$$を設定後に,
「どのような整数$${a, b}$$を選べば, キャンバス上のセルをセル番号$${0, 1, …, m-1}$$によって$${m}$$色に色分けできるのか？」
という問題があるので, まずはその問題に関心を寄せることにします.
登場しないセル番号があって$${m}$$色に至らなかったとすると, その後の工程でポリオミノを完成させることができなくなってしまうことはチュートリアル編でもお伝えしたとおりです. チュートリアル編ではそのような「詰み設定」に対し, ユーザに対してアプリのリスタートを要求していました.
一方で, その状況を回避するための方法として, アルゴリズム編には,
$${a}$$と$${b}$$の最大公約数を$${d}$$とするとき, $${d}$$と$${m}$$が互いに素となる. （$${d}$$と$${m}$$の最大公約数が$${1}$$. ）
というような$${a}$$と$${b}$$を設定すればよいという旨の記述があります. （ただし, $${a}$$と$${b}$$は同時に$${0}$$ではないとします. ）実際これがすべてのセル番号（$${0, 1, …, m-1}$$）がそろうための必要十分条件となっていて, 条件が成立しない場合は$${m}$$色の色分けは成功しません. とはいえ, なぜそうなるのかという疑問が残ると思います.
利用する定理
それではその数学的な考察に移ります. 私たちはこれから結果20230427-1の証明を試みますが, その証明においては次の定理を認めることにします.
定理$${1}$$ :
$${a}$$と$${b}$$を同時に$${0}$$ではない整数とする. このとき$${\gcd (a,b)=1}$$の必要十分条件は, 整数$${x}$$と$${y}$$で$${ax+by=1}$$であるものが存在すること.
定理$${2}$$ :
$${a}$$と$${b}$$を同時に$${0}$$ではない整数とする. このとき$${\gcd (a,b)}$$は, $${ax+by}$$, ただし$${x,y∈\Z}$$で表される最小の正の整数である.
定理$${3}$$ :
$${a,b,c}$$を$${a≠0}$$である整数とする. このとき$${a}$$が, $${b}$$と$${c}$$の公約数なら, すべての整数$${x}$$と$${y}$$について$${a \mid (bx+cy)}$$である.
色分け問題の解決
そして次の結果を証明することで（直接的ではないにせよ）キャンバスの色分け問題が解決します.
結果20230427-1（キャンバスの色分け問題）:
$${m}$$を$${m≥2}$$である任意の整数, $${a}$$と$${b}$$を同時に$${0}$$ではない任意の整数として, $${a}$$と$${b}$$の最大公約数を$${d}$$とする. このとき, $${\gcd (d,m)=1}$$の必要十分条件は, ある$${x,y∈\Z}$$が存在して$${ax+by≡1 \pmod m}$$.
証明：
始めに, $${\gcd (d,m)=1}$$を仮定する. このとき, ある$${x,y∈\Z}$$が存在して$${ax+by≡1 \pmod m}$$であることを示す. $${\gcd (d,m)=1}$$のときは, 補題$${1}$$より, ある$${x_0 ∈\Z}$$により$${dx_0≡1 \pmod m}$$が成り立つ. 定理$${2}$$より, ある$${x_1,y_1 ∈\Z}$$により$${ax_1+by_1=d}$$と表せるから,
$$
a(x_0 x_1 )+b(x_0 y_1 )=(ax_1+by_1 ) x_0=dx_0≡1 \pmod m
$$
が成り立つ. よって$${x=x_0 x_1,y=x_0 y_1}$$とおくと, $${x,y∈\Z}$$かつ$${ax+by≡1 \pmod m}$$である.
次に, $${\gcd (d,m)≠1}$$を仮定する. このとき, すべての$${x,y∈\Z}$$に対して$${ax+by \not\equiv 1 \pmod m}$$であることを示す. では, 背理法で進めることにする. もし仮に, ある$${x,y∈\Z}$$が存在して$${ax+by≡1 \pmod m}$$が成立するとする. このとき, $${d}$$は$${a}$$と$${b}$$の公約数なので, 定理$${3}$$より$${d \mid (ax+by)}$$である. よってある$${k∈\Z}$$により$${ax+by=dk}$$となり,
$$
dk=ax+by≡1 \pmod m
$$
が成り立つ. しかし, このとき補題$${1}$$より, $${\gcd (d,m)=1}$$なので矛盾する.
$${\blacksquare}$$
補題$${1}$$:
$${m}$$を$${m≥2}$$である任意の整数とする. $${a}$$を任意の整数とする. このとき$${\gcd (a,m)=1}$$の必要十分条件は, 整数$${x}$$で$${ax≡1 \pmod m}$$であるものが存在すること.
証明：
始めに, $${\gcd (a,m)=1}$$を仮定する. このとき, 定理$${1}$$より, ある整数$${x,y}$$が$${ax+my=1}$$を満たす. よって$${ax≡ax+my=1 \pmod m}$$である.
次に, $${\gcd (a,m)≠1}$$を仮定する. 背理法で進めることにして, もし仮に, ある整数$${x}$$で$${ax≡1 \pmod m}$$が成立するとする. $${n_0,n_1, \dots ,n_{m-1}}$$を
$$
n_0=0a, \\
n_1=1a, \\
\dots, \\
n_{m-1}=(m-1)a,
$$
とおく. するとこのとき, すべての$${k}$$, ただし$${k=0,1, \dots ,m-1}$$について,
$$
(1) \space n_{k}x=(ka)x=k(ax)≡k \cdot 1=k \pmod m
$$
が成り立つ. ここで$${\gcd (a,m)=d,a=da',m=dm'}$$とおく. すると, $${1 < d}$$なので, $${m'}$$は$${0 < m' < m}$$である整数である. したがって
$$
n_{m'}=m'a=m' (da' )=(m' d) a'=ma'≡0 \pmod m
$$
が成立する. すると$${n_{m'}≡0 \pmod m}$$の両辺に$${x}$$をかけることで
$$
n_{m'}x≡0x=0 \pmod m
$$
が得られた. しかし一方では, $${(1)}$$より
$$
n_{m'} x≡m' \pmod m
$$
も同時に成り立つので矛盾する.
$${\blacksquare}$$
この記事が気に入ったらサポートをしてみませんか？