1998年東京大学後期第3問を一般化した Part2

$$\begin{array}{rl}& ?-\star \\ \Rightarrow & ?-\overline{\star }-\circ \\ \Rightarrow & ?-\star -\circ -\bullet \\ \Rightarrow & ?-\star -\circ -\circ -\circ \end{array}$$

ただし$?$は残りの部分、$\star$は$\circ$または$\bullet$、$\overline{\star }$は$\star$の色を反転したもの。

$n\times m$の長方形の$1$個の辺を構成する全ての頂点に操作$T$を適用すればよい。

操作$2$を行うと$3$個以上の頂点が一直線上に並ぶので$2\times 2$の長方形を作るためには操作$1$のみで行う必要がある。操作$1$は$\bullet$の個数の偶奇を反転させるが、頂点が$4$個あるグラフでは操作$1$が$3$回必要であり、したがって$\bullet$の個数は奇数でなければならない。よって、$4$個すべての頂点を$\circ$にすることはできない。

以下の過程で作れる。

$$\begin{array}{rc}& \begin{array}{c}\circ \end{array}\\ \\ \Rightarrow & \begin{array}{ccc}\bullet & -& \circ \end{array}\\ \\ \Rightarrow & \begin{array}{ccc}\circ & & \\ |& & \\ \circ & -& \circ \end{array}\\ \\ \Rightarrow & \begin{array}{ccc}\bullet & -& \circ \\ |& & \\ \circ & -& \circ \end{array}\\ \\ \Rightarrow & \begin{array}{ccccc}\circ & -& \circ & -& \bullet \\ |& & & & \\ \circ & -& \circ & & \end{array}\\ \\ \Rightarrow & \begin{array}{ccccc}\circ & -& \circ & -& \circ \\ |& & & & |\\ \circ & -& \circ & & \circ \end{array}\end{array}$$

「最も右下にある$\circ$の上と右に操作$1$を適用する」という操作を繰り返すことで、以下のグラフが得られる:

$$\begin{array}{ccccccccc}\circ & & \circ & & & & \circ & & \\ |& & |& & \cdots & & |& & \\ \circ & -& \circ & -& & -& \circ & -& \circ \end{array}$$

ただし、$\begin{array}{c}\circ \\ |\\ \circ \end{array}$は$m-3$個存在する。

このグラフの最も右下の頂点に定理5の証明の構成法と同じものを適用すれば、$2\times m$の長方形が得られる。

$m\mathrm{\%}3=0,1$であれば、$1\times m$のグラフの上下に$\circ$を追加すればよい:

$$\begin{array}{ccccc}\circ & & \circ & & \circ \\ |& & |& & |\\ \circ & -& \circ & \cdots & \circ \\ |& & |& & |\\ \circ & & \circ & & \circ \end{array}$$

$m\mathrm{\%}3=2$であれば、まず$2\times 3$の操作を転置して$3\times 2$を作り、そこから操作$T^{\prime }$を繰り返せばよい。

(i) $m=2,3$のとき

$m\times n$の構成法を転置して$n\times m$とすればよい。

(ii) $m=4$のとき

$n\mathrm{\%}3=1,2$であれば、$1\times m$が作れるのでそれに操作$T^{\prime }$を繰り返せばよい。
$n\mathrm{\%}3=3$であれば、$3\times 4$が作れるのでそれに操作$T^{\prime }$を繰り返せばよい。

(iii) $m\ge 5$のとき

$n\times (m-3)$をまず作り、それに操作$T^{\prime }$を行えばよい。