変則ナイトで盤面を駆け回る

大学院の入試があったので久しぶりの更新となってしまった.
今回は変則的な動きをするナイト（変則ナイト）がどのような動きをするならば, この変則ナイトで盤面上を駆け回れるかを考える.
参考までにナイト（チェス）, 変則チェスのwikipediaのリンクを張っておく:
ナイト（チェス）, 変則チェス.
この記事では盤面の広さを $\infty\times\infty$ とし, ナイトの初期位置は原点 $(0,0)$ にとる（通常のチェスの盤面の広さは $8\times8$ で, ナイトの初期位置は $(2,1)$ , $(7,1)$ , 相手方なら $(2,8)$ , $(7,8)$ である）.


図1 通常ナイトの動き	図2 変則ナイトの動き

変則ナイトの動きの定義

通常のチェスでは, ナイトは上の図1のように, 1列先の右斜め前などの最大8ヶ所のマスに移動することが出来る.
これを数学的に表せば, 通常ナイトはベクトル \begin{align*} \boldsymbol{v}_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}, \quad \boldsymbol{v}_2 = \begin{pmatrix} 1 \\ 2 \end{pmatrix}, \quad \boldsymbol{v}_3 = \begin{pmatrix} -1 \\ 2 \end{pmatrix}, \quad \boldsymbol{v}_4 = \begin{pmatrix} -2 \\ 1 \end{pmatrix}, \end{align*} およびこれらの逆ベクトルの動きが出来ると言える.
これを一般化して, ベクトル \begin{align*} \boldsymbol{v}_1 = \begin{pmatrix} a \\ b \end{pmatrix}, \quad \boldsymbol{v}_2 = \begin{pmatrix} b \\ a \end{pmatrix}, \quad \boldsymbol{v}_3 = \begin{pmatrix} -b \\ a \end{pmatrix}, \quad \boldsymbol{v}_4 = \begin{pmatrix} -a \\ b \end{pmatrix}, \end{align*} およびこれらの逆ベクトルの動きが出来る「変則ナイト」を考える（図2）.
以下, このナイトを「 $(a,b)$ ナイト」と呼ぼう.
ただし $a$ , $b$ は整数で, $a\gt b \gt 0$ である（ $a=2$ , $b=1$ のとき通常ナイトを再現する）.
このとき, ナイトが到達するマスの位置ベクトル $\boldsymbol{p}$ は, 1～4の値をとる整数列 $a_n$ を用いて \begin{align*} \boldsymbol{p} = \pm\boldsymbol{v}_{a_1} \pm\boldsymbol{v}_{a_2} \pm\boldsymbol{v}_{a_3} \pm\cdots \end{align*} と書ける.
すなわち, ナイトが到達可能なマスは, $n_1$ ～ $n_4$ を整数として \begin{align*} \boldsymbol{p} = n_1\boldsymbol{v}_1+n_2\boldsymbol{v}_2+n_3\boldsymbol{v}_3+n_4\boldsymbol{v}_4 \tag{1} \end{align*} で表される $\boldsymbol{p}$ の全体である.

変則ナイトで盤面を駆け回るには

では, 上で定義した $(a,b)$ ナイトが盤面上の全てのマスに到達できる条件を考える.
明らかにこれの必要十分条件は $(1)$ 式が2つの基本ベクトルを含むことである.
つまり, \begin{align*} \begin{pmatrix} 1 \\ 0 \end{pmatrix} &= n_1\boldsymbol{v}_1+n_2\boldsymbol{v}_2+n_3\boldsymbol{v}_3+n_4\boldsymbol{v}_4, \tag{2-1} \\ \begin{pmatrix} 0 \\ 1 \end{pmatrix} &= m_1\boldsymbol{v}_1+m_2\boldsymbol{v}_2+m_3\boldsymbol{v}_3+m_4\boldsymbol{v}_4 \tag{2-2} \end{align*} を満たす整数の組 $n_1$ ～ $m_4$ が存在するような正整数の組 $(a,b)$ が条件を満たす.
ナイトの動きの対称性から $(2\text{-}1)$ 式だけを考えれば十分なので, 全ての成分をあらわに書いて \begin{align*} \left\{ \begin{matrix} n_1a+n_2b-n_3b-n_4a =1, \\ n_1b+n_2a+n_3a+n_4b =0. \end{matrix} \right. ~\Leftrightarrow~ \left\{ \begin{matrix} (n_1-n_4)a+(n_2-n_3)b =1, \\ (n_2+n_3)a+(n_1+n_4)b =0. \end{matrix} \right. \tag{3} \end{align*} まず, $(3)$ 式の第1式より $a$ , $b$ は互いに素である必要がある.
これはBézoutの補題（Wikipedia: ベズーの等式）より従う.
これは,「正整数 $a$ , $b$ , 整数 $x$ , $y$ に対して定義される整数 $p:=ax+by$ は, $a$ , $b$ の最大公約数の倍数しか取りえない」というものである（証明略）.
この補題より $a$ , $b$ の最大公約数は1であることが分かるので, $a$ , $b$ は互いに素である.

次に, 考えている $a$ , $b$ に対して, 等式 $ax+by=1$ の整数解 $(x,y)$ が1組見つかったとする
（例えば $(a,b)=(2,1)$ ならば $(x,y)=(1,-1)$ など, $(a,b)=(5,3)$ ならば $(x,y)=(-1,2)$ などである）.
その整数解を $(x,y)=(p_1,p_2)$ とおく.
すると $k$ を整数として \begin{align*} p_1a+p_2b=1 ~\Leftrightarrow~ \left\{ \begin{matrix} n_1-n_4 = p_1+kb, \\ n_2-n_3 = p_2-ka \end{matrix} \right. \tag{a} \end{align*} が成立する（これは $(3)$ 式の第1式に代入すれば明らか）.
これを $(3)$ 式の第2式に代入して, \begin{align*} (p_2-ka+2n_3)a+(p_1+kb+2n_4)b =0. \end{align*} これが成立するためには, 整数 $l$ を用いて \begin{align*} \left\{ \begin{matrix} p_2-ka+2n_3 = ~~~\, lb, \\ p_1+kb+2n_4 = -la\, \end{matrix} \right. \tag{b} \end{align*} と書ける必要があり, 逆に \begin{align*} \left\{ \begin{matrix} \displaystyle n_1 = \frac{p_1-la+kb}{2},~\, &\displaystyle n_2 = \frac{p_2-ka+lb}{2},~~ \\ \displaystyle n_3 = \frac{-p_2+ka+lb}{2},&\displaystyle n_4 = \frac{-p_1-la-kb}{2}\, \end{matrix} \right. \tag{4} \end{align*} は全て整数である必要がある.

最後に, $a$ , $b$ の偶奇が異なる場合のみ $(4)$ 式で表される $n_1$ ～ $n_4$ が整数になることを示す.
「 $a$ :偶数, $b$ :奇数」とする（逆の場合も同様の議論が成り立つ）.
このような $a$ , $b$ に対しては, $p_1a+p_2b=1$ なる $p_1$ , $p_2$ が「 $p_1$ :偶数, $p_2$ :奇数」に取れる（必要ならば $(\mathrm{a})$ 式の $k$ を適当に動かせばよい）.
すると $(4)$ 式の $n_1$ ～ $n_4$ は（分子が全て偶数になる必要があるので）,
「 $k$ :偶数, $l$ :奇数」のとき整数となる.
これで「 $a$ :偶数, $b$ :奇数（とその逆）」のときは $(3)$ 式が成立するような整数 $n_1$ ～ $n_4$ が存在することが示された.
（いま $a$ , $b$ は互いに素なので,「 $a$ :偶数, $b$ :奇数（とその逆）」もしくは「 $a$ :奇数, $b$ :奇数」しかありえない. 後者の場合そのような整数 $n_1$ ～ $n_4$ は存在しないことが同様の議論で証明できる.）