面白い問題おしえて～な 28問目

**１３２人目の素数さん** · 2018/10/29(月) 00:19:23.87

**１３２人目の素数さん** · 2018/11/18(日) 01:04:20.36

>>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にできる。

**１３２人目の素数さん** · 2018/11/18(日) 01:42:47.40

訂正
×まず左上のm×mを必要なだけ挿げ替えて
○ まず左上の(m^n/m)×(m^n/m)を必要なだけ挿げ替えて

訂正ついでにも少し補足。
挿げ替えとはA→B、C→DをA→D、C→Bと→を選び直す事。
この作業を何回か繰り返せば同じブロックに属する→は全て同一成分に出来る。
今の例なら
A→B→‥→A、C→D→‥→Cという2成分が
A→D→‥→C→B→‥→Aとつながって1成分減る。

**１３２人目の素数さん** · 2018/11/18(日) 02:05:20.86

あ、いらん訂正した。>>344であってます。
>>345は無かったことに。
同一ブロックに入るのはたとえばm=3, n=5ならたとえば
fromが02430,02431,02432,02433,02434,
toが. 00243,10243,20243,30243,40243
であるm×m個。
このfromがm個、toがm個のm×m通りは全て→で結ばれていて自由に挿げ替えられる。

**１３２人目の素数さん** · 2018/11/18(日) 02:36:13.22

>>346
スレ汚しすまん。まだ間違ってる。
挿げ替えのアルゴリズムは>>344では不十分。
以外に訂正。

とりあえず、全ブロックの→を挿げ替えで同一成分にする。
これで十分。
もしこれで2成分以上あったとする。
しかし元のグラフは連結なので2成分X YとXの通過する点とＹの通過する点を結ぶ→がみつかる。
実際異なる連結成分を結ぶパスで長さ最小のパスを取ればそれは→である。
たとえばm=5, n=5で
X: …→02432→30243→…
Y: …→02431→10243→…
の02432と10243の様な組みである。
そしてこの部分は同一ブロックに属する。
しかし同一ブロックの→は全て同一連結成分になる様に取っているのでそれらが異なる連結成分に属するのは矛盾。