1近畿大学 2019年 数学 第1問解答・解説

第1問 辺を共有する単位正方形の集まりを考え、平行移動は各図形の各座標の最小値がともに0となるよう移して除く。さらに、回転・線対称移動に対応する $$(x,y),\ (x,-y),\ (-x,y),\ (-x,-y),\ (y,x),\ (y,-x),\ (-y,x),\ (-y,-x)$$ の8通りの変換を行い、各々を平行移動で正規化して座標列を辞書順に並べる。そのうち辞書順最小の表現だけを代表に採るので、同じ図形は1回だけ数えられる。

具体的には、$F_1=\{\{(0,0)\}\}$ とし、$F_k$ の各図形の外側に辺を共有する1マスを付け加えた後、平行移動と8通りの対称変換で同じものを一つにまとめて $F_{k+1}$ を作る。この生成で漏れがないことを確認する。任意の連結な $(k+1)$ マス図形について、まず1マスを選ぶ。まだ選んでいないマスが残る間、連結性から、選んだマスから未選択マスへ至る辺共有の道がある。その道で最初に現れる未選択マスを選び、直前の選択済みマスとの共有辺を1本記録する。この操作を繰り返すと全マスが選ばれる。記録した辺は全マスをつなぐ。記録した辺に閉路があると仮定し、その閉路上で最後に選ばれたマスを見る。このマスは選ばれた時点で、それ以前に選ばれたマスとの辺を1本しか記録していないので、閉路の2辺を持つことはできない。これは矛盾する。従って記録した辺には閉路がなく、全マスをつなぐ木になる。マスが2個以上あるので、この木の最長の道は少なくとも1辺をもち、その両端の少なくとも一方は最初に選んだマスではない。最長の道のその端点には記録辺が1本だけある。そうでなければ、道上の隣以外の隣接点から道を延ばせるか、道上の別の点につながって閉路ができる。そこで端点のマスを除くと、残りの記録辺は全ての残りのマスをつないだままである。従って $k$ マスの連結図形が得られる。この1マスを付け戻せば元の図形になるので、任意の $(k+1)$ マス図形が生成に漏れることはない。生成数は $$\begin{array}{c|rrrrrr} k&1&2&3&4&5&6\\ \hline |F_k|&1&1&2&5&12&35 \end{array}$$ である。従って(1)の答えは、$n=3,4,5$の順に $2,5,12$ 種類、(2)の総数は $35$ 種類である。

列挙の確認用に、次の表示では `#` を1マス、`.` を空所、`/` を下から上への行の区切りとする。各行の幅は図形全体の幅である。以下は上の規則で正規化した代表で、$n=6$では35個ある。

n=3: #/#/#  ##/#.
n=4: #/#/#/#  ##/#./#.  #./##/#.  ##/##  #./##/.#
n=5: #/#/#/#/#  ##/#./#./#.  #./##/#./#.  ##/##/#.
     ##/#./##  ###/#../#..  #../###/#..  #./#./##/.#
     #../###/.#.  #../##./.##  #../###/..#  .#./###/.#.
n=6: #/#/#/#/#/#  ##/#./#./#./#.  #./##/#./#./#.
     #./#./##/#./#.  ##/##/#./#.  ##/#./##/#.
     ##/#./#./##  ###/#../#../#..  #./##/##/#.
     #../###/#../#..  #./#./#./##/.#  ##/##/##
     ###/##./#..  ##./###/#..  ##/#./##/.#
     ###/#../##.  #./##/##/.#  #.#/###/#..
     #.../####/#...  #./#./##/.#/.#  #../#../###/.#.
     #../#../##./.##  #../#../###/..#  ##./###/.#.
     ##./##./.##  #../###/.#./.#.  #../##./.##/.#.
     #../##./.#./.##  #.#/###/.#.  #.../####/.#..
     #../##./.##/..#  #.../####/..#.  #.../####/...#
     .#./###/.#./.#.  .#./##./.##/.#.

立方体の展開図かどうかは、1マスを立方体の面に置き、隣のマスを共有辺のまわりに90度折り曲げて判定する。各マスの右・上・外向きの方向を $(u,v,w)$ とすると、東西南北の隣のマスの方向はそれぞれ $$(-w,v,u),\quad (w,v,-u),\quad (u,-w,v),\quad (u,w,-v)$$ となる。経路を変えて同じマスに来たとき向きが矛盾するもの、または6マスの外向き方向が立方体の6面に一対一に対応しないものは展開図でない。この判定を35個に行うと、該当する代表は次の11個である。

#.../####/#...
#./#./##/.#/.#
#../###/.#./.#.
#../##./.##/.#.
#../##./.#./.##
#.../####/.#..
#../##./.##/..#
#.../####/..#.
#.../####/...#
.#./###/.#./.#.
.#./##./.##/.#.

従って、立方体の展開図と一致するものは $11$ 種類である。

検算 正規化代表の個数は各段階で $1,1,2,5,12,35$。展開図の代表は上の11個で、いずれも6マスであり、8通りの回転・反転を同一視して互いに異なる。よって全体数と展開図数の大小関係も $11\le35$ と整合する。