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

2023年11月10日 11:10

P.T.P.S.

私はScratchでP.T.P.S.というアプリを開発し公開しています. それはポリオミノと呼ばれる複数の正方形が辺でつながった図形を用いて, そのタイリングパターンを作成できるアプリです.

アプリへのリンク（Scratch）：P.T.P.S.(Polyomino Tiling Pattern Simulator)

詳しい説明は省きますが, アプリでは「キャンバス」と呼ばれる$${m^2}$$にセルが並んだグリッド上に$${m}$$個のセルで構成されるポリオミノを描くというプロセスがあります.

キャンバス上の各セルには「セル番号」という$${0}$$から$${m-1}$$までの整数が表示されており, セル番号はユーザが設定した$${m}$$,$${a}$$,$${b}$$という値と各セルの座標から計算されています. ただし, $${m}$$は$${2}$$から$${10}$$までの整数, $${a}$$と$${b}$$は$${0}$$から$${m-1}$$までの整数です.

座標の決め方：

座標は$${0}$$から$${m-1}$$までの整数の順序対$${(x,y)}$$で表される．
一番左，一番下にあるセルの座標は$${(0,0)}$$で，この座標のことを原点と呼ぶ．
原点から$${x}$$右，$${y}$$上にあるセルの座標は$${(x,y)}$$．

座標$${(x,y)}$$にあるセルのセル番号$${r}$$の計算は次のようにします. ただし, $${\bmod}$$は割り算の余りを計算する演算子です.

セル番号の計算式：

$$
r=(ax+by) \bmod m.
$$

そして, ユーザはそのセル番号を頼りに, 選んだセルのセル番号同士で重複がないようにポリオミノを構成するセルを選択していきます. したがって, ユーザが$${m}$$個のセルを選び終わったときには, それらのセルのセル番号は$${0}$$から$${m-1}$$まですべて登場することになります.

キャンバスにm色が登場する条件

しかし, そもそもキャンバスにすべてのセル番号($${0}$$から$${m-1}$$まで)が登場していなかった場合, $${m}$$個のセルをセル番号が重複しないように選ぶことは不可能です.

ユーザが$${m}$$,$${a}$$,$${b}$$を適切に設定することで, そういった状況は回避できるのですが, そのための条件を私はすでに特定しています. 具体的には, $${a}$$と$${b}$$が同時に$${0}$$にならないようにして, $${a}$$と$${b}$$の最大公約数を$${d}$$としたとき,

$${d}$$と$${m}$$の最大公約数が$${1}$$になること.

がキャンバス上にすべてのセル番号が登場するための必要十分条件となっています. （詳細については以下のリンクを参照してください. ）

問題発見

以前の私の説明では, $${m}$$,$${a}$$,$${b}$$の設定法に関してはそこで終わっていました. しかし後になってからよくよく考えてみると, キャンバス上にすべてのセル番号が登場したからといって, $${m}$$色に塗り分けられたポリオミノが構成できるという保証はありませんでした. （各セル番号を互いに異なる「色」とみなして表現しています.）

それからというもの, 色々と実験を重ねて検討した結果, この意外と頭を悩ます問題にようやく解決法を見出すことができました. 今回はこの記事をご覧の皆様とその解決法を共有したいと思います.

解決手段

まず私たちは, ユーザが設定した$${m}$$,$${a}$$,$${b}$$により, キャンバス上にすべての色が登場しているという前提で話を進めます. このとき$${a}$$と$${b}$$は同時に$${0}$$であるとは考えにくく, 実際不合理なので, $${a}$$と$${b}$$は同時に$${0}$$ではないと結論できます. 上記の通り, このときは$${\gcd (a,b)=d}$$として$${\gcd (m,d)=1}$$が成り立っています. 次に, 私たちは一般性を失うことなく$${a}$$が$${0}$$ではないと仮定します. そして$${a}$$と$${m}$$の最大公約数を$${d_1}$$とします. すると, 原点を左下隅にもつ, $${(m/d_1)\cdot d_1}$$のポリオミノがとれます.

原点を左下隅にもつ長方形のポリオミノをとる. (m=10, a=6, b=9.)

このポリオミノは長方形の形をしており, 横方向にセルが$${m/d_1}$$個, 縦方向にセルが$${d_1}$$個並んでいます. $${(m/d_1)\cdot d_1 =m}$$なので, ポリオミノは$${m}$$個のセルで構成されることになります. しかも$${m^2}$$のキャンバスからはみ出したりはしていません.

私たちはこれから結果20230928-1を証明しますが, それにより, 注目している長方形ポリオミノが$${m}$$色に塗り分けられていることが分かります.

この記事が気に入ったらサポートをしてみませんか？