>>338
m=3、n=2の場合で考える。
別のｹｰｽでもいけるけど記述がうるさくなるので。
0〜m^n-1の整数を頂点とし[x/m] ≡ y (mod m^n/m)の時xからyに→を描いて向き付きのｸﾞﾗﾌGを作る。
このｸﾞﾗﾌが全ての点をちょうど一回づつ通る向き付きのﾙｰﾌﾟを持つ事を示せば良い。
隣接行列をfromが横方向、toが縦方向に来るようにとる。
また、見やすいようにfromは最下位桁以外が一致するものを固めてならべ、toは最上位桁以外が固まるように並べる。
今の場合なら例えば以下のようになる。
. 00 01 02 10 11 12 20 21 22
00 1 1 1
10 1 1 1
20 1 1 1
01 1 1 1
11 1 1 1
21 1 1 1
02 1 1 1
12 1 1 1
22 1 1 1
このなかの1から1をm^n個選びその表す部分ｸﾞﾗﾌが連結成分数が1の向き付きﾙｰﾌﾟになるものを見つければ良い。
各行、各列からちょうど一個づつ選べば向き付きﾙｰﾌﾟの有限和にはなる。
例えば対角線上の1を全て選べば良い。しかしそれだと連結成分が複数出てくるので繋げていく。
まず左上のm×mを必要なだけ挿げ替えてそのﾌﾞﾛｯｸにあるﾙｰﾌﾟが成分一個になるようにする。
上の例なら
. 00 01 02 10 11 12 20 21 22
00 ○
10 ○
20 ○
01 ○
11 ＊
21 △
02 ○
12 △
22 ※
となる。
この時点で00→20→02→10→01→00、11→11、12→21→12、22→22の4成分。
ここで右上のﾌﾞﾛｯｸを占有するﾙｰﾌﾟの中の→のtoは最下位桁以外を無視して0〜m^n/m-1までの全ての数がでるから各ﾌﾞﾛｯｸを少なくとも1回づつ通過する。
よって先の様な挿げ替えを再び行って成分数を1にできる。