『今週の問題』第96回　解答

◆鹿児島県　ともひろ さんからの解答

【問題１】

【解】４回 (2→7→3→9)

【問題２】

【解】５回 (4→10→3→8→1)

【問題３】

【解】７回 (6→12→8→2→11→6→1)

◆広島県　清川　育男 さんからの解答

【問題１】

2→7→3→9

４手

【問題２】

4→10→3→8→1

５手で可能でした。

【問題３】

 2  5  11  3  12  6  1 
 2  7  1  12  8  3  13 
 2  7  11  3  12  6  13 
 2  7  12  1  6  11  1 
 2  7  12  1  11  6  1 
 2  7  13  3  8  12  1 
 2  9  4  12  3  8  1 
 2  9  12  4  11  8  1 
 2  9  13  3  7  11  1 
 3  8  13  2  7  12  1 
 3  12  9  5  11  2  13 
 4  7  3  12  2  9  1 
 4  7  11  2  12  5  13 
 4  9  13  2  6  11  1 
 4  12  3  10  6  9  1 
 4  12  8  11  3  9  1 
 5  10  1  12  8  3  13 
 5  10  4  9  2  12  1 
 5  12  1  11  7  3  13
 6  1  8  12  2  10  13 
 6  1  10  5  12  2  13 
 6  3  7  11  2  5  13 
 6  11  4  9  2  13  1 
 6  12  8  2  11  6  1 
 7  2  13  3  8  12  1 
 7  12  1  11  6  2  13 
 8  1  4  9  2  12  1 
 8  3  13  2  7  12  1 
 8  11  6  2  12  6  13 
 8  11  6  12  2  6  13 
 9  2  13  3  7  11  1 
 9  4  10  5  12  2  13 
 9  4  13  2  6  11  1 
10  1  9  3  11  5  13

【問題４】

●３人ずつの時、

男女男女男女□□□

男□□□男女女男女
男女女男男□□□女
□□□男男男女女女

●７人ずつの時、

男女男女男女男女男女男女男女□□□

男女男女男□□□男女男女男女女男女
男女男女男女女男男女男女男□□□女
男女男女□□□男男女男女男男女女女
男女男女女男男男男女男□□□女女女
男女□□□男男男男女男男女女女女女
男女女男男男男男男□□□女女女女女
□□□男男男男男男男女女女女女女女

●９人ずつの時、

男女男女男女男女男女男女男女男女男女□□□

男女男女男女男□□□男女男女男女男女女男女
男女男女男女男女女男男女男女男女男□□□女
男女男女男女□□□男男女男女男女男男女女女
男女男女男女女男男男男女男女男□□□女女女
男女男女□□□男男男男女男女男男女女女女女
男女男女女男男男男男男女男□□□女女女女女
男女□□□男男男男男男女男男女女女女女女女
男女女男男男男男男男男□□□女女女女女女女
□□□男男男男男男男男男女女女女女女女女女

男女それぞれＮ人ずつとするとき、
Ｎが奇数のときはＮ手。

Ｎが偶数のとき
Ｎ＝４では ４手、
それ以外は（Ｎ＋１）手が予想されます。　

◆愛知県　Y.M.Ojisan さんからの解答

【問題１】

最小手数　４回
2 → 7 → 3 → 9　のみ

【問題２】

最小手数　５回
4 → 10 → 3 → 8 → 1　のみ

【問題３】

最小手数　７回

6 → 11 → 4 → 9 → 2→ 13 → 1
　右寄せ　赤青

9 → 4 →10 → 5 → 12→ 2 →13
　左寄せ　青赤

2 → 5 →11 → 3 → 12→ 6 → 1
　右寄せ　青赤

2 → 7 → 1 →12 → 8 → 3 →13
　左寄せ　赤青

等

【問題４】

最小手数

Ｎが３、４、および　５以上の奇数の時
　Ｎ回でかつ１種だけ

Ｎが６以上の偶数の時
　Ｎ＋１回で解の数は
　Ｎ＝６　　３４種
　Ｎ＝８　　１３９種
　Ｎ＝１０　１３９０種

【３以上の奇数のときの方法】

手順：N-1　→ 2N → N-2 → 2N-2 → N-4→ 2N-4 → N-6 →
 　・・・２組ずつ、 2ずつ減少　・・・
　→  3 →  N+3 → 1

(1)上の段からそのまま下に移動
(2)下の段の１個前から上の段に移動
(3)上の段からそのまま下に移動
(4)下の段の２個前から上の段に移動

以後(3)(4)を繰り返す。
下図（Ｎ＝７の場合）参照
なお、この方法が唯一の方法である。

【６以上の偶数のときの方法】

手順：N   → 2N-1 → N-2 → 2N-3 → N-4→ 2N-5 → N-6 →
 　・・・２組ずつ、 2ずつ減少　N-2回(手=2)まで
　→  2N+1 → 1

(1)上の段からそのまま下に移動
(2)下の段の２個前から上の段に移動する。
以後(1)(2)をＮ−１回まで繰り返す。

(3)Ｎ回目は　２N＋１番から移動
(4)Ｎ＋１回目は１番から移動する。
下図（Ｎ＝８の場合）参照。

【証明】

●Ｎが奇数のとき。

男男　女女同士が　隣接している状態（隣接関係とする）数が
最初「０」の状態から最後は２Ｎ−２にまで増加を要す。

一方、一度の移動で新たな隣接関係は最大２である。
また、一番最初は、隙間が無いので新たな隣接関係は最大１である。

よって　手数＊２−１≧２Ｎ−２でなければならず、Ｎは整数なので手数の最小値はＮより大きいか等しい。
前に示したように、実際に手数Ｎの方法が存在しており、従って，手数最小はＮである。

●Ｎが偶数のときN＋１が最小　および　Ｎが奇数のとき解が１種だけの証明

（１）関連問題の設定

基本的に同じ問題で、右端と左端をつないでループさせ、すこし条件のゆるい場合を考える。
そして、条件を緩くしても存在しないことを証明する。

すなわち、図のＡの状態から隣接する３人ずつを方向を変えないで、空きスペースに移動しながら、Ｂの状態に何手でできるかという問題である。
なお、最後に全体を回転させたり、裏返したりしてもよく、これは手数に数えない。

先にこの問題の答えを言うと、最少手数は　Ｎであって、それらは
　裏返し＋男と女を交換したら同じ手順になるものと、最初の手に必ずある２手で分類すると３群のみである。
逆にいうと　全部で２×２×３＝１２種類が存在する。

これら１２種類を吟味すると、基本問題に適合するものはＮが奇数のときはただ１つ、Ｎが偶数のときは０であることがわかる。
但しＮ＞５

よって、Ｎが偶数のときの最小手数はＮ＋１である。

証明は隣接関係の数をベースにおこなう。
また、ＡからＢの手順の変わりにＢからＡの手順を探索する。
これらは同値である。

この場合の最後の手は隣接関係を１のみ減少可能である。
なぜなら，図Ａにおける　13,14,15の隣接セルが男と女であり、一方そこにあった関係は「男女男」か「女男女」でなければならないので、隣接関係数は１のみであるからである。

Ｎ回でＢからＡに到達するには隣接関係の数の減少数は、最後が１回に決まっているので、
残り　Ｎ−１回のうちの１回だけが１減少し、その他では必ず２減少する必要がある。

（２）隣接関係の減少が
２→２→２　・・・・・・２→１→１　の場合

　上図はN=１２の場合を示しているが、一般に隣接関係がずっと２ずつ減少する手順は、
一番最初が　N−１とNの手（白文字と黒枠）の２手のみである。

これらは鏡像対称の関係にあるので、N-1の場合のみを考えればよい。
その後の手順は移動した３人の両端が常に異性で無ければならずかつ両端は隣接している必要があるので常に１通り（白文字）しかなく，空きスペースを常に先頭に回転させると、図のようにシンメトリックに変化してゆく。

　最終的に残り２手のところで、隣接関係を２減少させることが出来なくなり、１ずつ減少させる手順しかなくなる。
この場合　白文字　と　黒枠の２手がそれぞれの段階であり、合計２群　４種が存在する。
最初の鏡像を含めると８種存在する。　

（３）隣接関係の減少が
２→２→２　・・・・・・２→１→２→１　の場合

残り３手のところで、隣接関係を１減じる手順は　男まはた女の５連続がないので、右が男で左が女かつ一方が隣接関係にないところ移動しなければならない。
従って、一般に上図の白文字の手　１群しかなく、最終手の２種（白文字と黒枠）と鏡像関係を掛けて４種存在する。

（４）隣接関係の減少が
２→２→２　・・・・・・２→１→２→２→１　の場合

この場合は、男女が交互にならんでいる部分は、もはや動かすことが出来ない（隣接関係がない）ので、適当なNで存在しなければそれより大きいNでは存在しない。
実際、N=6の時存在しないことが計算機により確かめられているので、この手は存在しない。

（５）・・・・・・１　・・・・→２→２→２→１（一般）の場合の証明の準備

証明の前に若干準備をしておく。
すべて　隣接関係を一度１減じた後の２ずつ減少させなければならない条件下での場合とする。
なお、言葉の定義として、以下を規定する．

「移動中心」とは移動させる３人の中心の人の位置とする。

「ホモ移動」とは同性の３人（男男男　or 女女女）が移動すること。

「ヘテロ移動」とは　男女男　or　女男女　が移動すること。

「ホモ異性である」とは　男男男に対する女女女の関係

「ヘテロ異性である」とは　男女男に対する女男女の関係

「双変移動」とは　隣接関係が両側で切れ移動先で復活せず　隣接関係が２減じる移動のこと。

「単変移動」とは　隣接関係が両側で切れ移動先で１個復活するか、片側で切れるのみの　隣接関係が１減じる移動のこと。
特に後者を「純単変移動」とする。

「切替後状態」とは　単変移動直後の状態のこと。

（５−１）移動は必ずホモ双変移動かヘテロ双変移動でなければならない。

∵（２）の図に示したように、隣接関係減少量が偶数状態では空きスペースの両側は異性であるが、単変移動後は空きスペース両側は同性になる。
従って、その後隣接関係を２ずつ減少させるには移動の両端は同性でなければならない。
（５−２）図参照

（５−２）移動する３人の端の性は１手毎に入れ替わる。

∵　移動元で隣接関係を２切ったあと、移動先で隣接関係を１つも回復してはならず、上図から明らか。

（５−３）男女が交互に４人以上連続するところはもはや動かすことができない。
従って、この人たちを含む移動はできない。

∵　条件下では、隣接関係の無い境目で切ることは出来ないので、上図の移動中心が×の位置は利用できない。
従ってこれら４人はもはや移動できない．

（５−４）特にヘテロ双変移動（黄色枠）後には　下図のように、５人の不動状態と７個の移動不可の移動中心ができる。

（５−５）空白部に隣接して男女が交互に３人連続するところはもはや動かすことができない。
従って、この人たちを含む移動はできない。

∵　条件下では、隣接関係の無い境目で切ることは出来ないので、上図の移動中心が×の位置は利用できない。
かつ空白部が埋まった後の状態ではかならず交互に必ず４人ならぶので、
（５−３）によりこれら初期の３人は移動できない．

（５−６）ホモ双変移動可能な人は　切替後状態から未移動の人に限られる。
従って，Ｍ人が同性で連続している状態からはホモ移動は
最大でも［(Ｍ-１)/4］組だけである。
ここで [ ] はガウス記号。下図参照

∵ホモ移動するには最低５人が同性で連続していなければならないが，移動後には連続できるのは最大でも３人であるからである。

（５−７）残り２手状態に於いてへテロ双変移動済みの中心ないし空白スペース中心の間隔は
通常は（５−４）により最小４であるが、一箇所だけは同性へテロ双変移動後中心ないし空白スペース間で８以上である。

∵　残り２手の状態を逆からたどると上の図の状態である。
従って、残り２手における最後のヘテロ移動の両側は、同性のヘテロ双変移動（黄色枠）ないし空白スペースの場合、最小でも間隔は８必要である。
さらに異性へテロなら９必要である。

（６）・・・・・・１　・・・・→２→２→２→１（一般）の場合の証明

（６−１）　初手が単変移動　途中は全部双変移動、最後が純単変移動の場合

（２）の手数０の状態から、単変移動した後の状態は　
Ｎ≧５のとき　性の交換は同じとすると、一般に下記パターンのみである。

なおｋは同性がｋ人連続を意味する。
また（　）内は（２）の図に対応する　
Ｎ＝１２の場合の値である。

この状態から、残り手数２の状態考える。
（５−６）の補題を用いるので、Ｎを４を法として分類し、（５）の補題を用いると下表となる。

特に　Ｐ項を説明する。　
（５−７）により双変へテロ移動の最初の手で７セルが移動中心から除外され、
以後（５−６）により双変へテロ移動１回につき４セルが除外されるとともに、
Ｉ項が１以上なら （５−６）により＋４セルが除外される。

また空白スペースは１個の双変へテロ移動後と同じ効果をもつので　
都合　７＋４＊（Ｉ＋１）セルが移動中心でいることが出来なくなる。

　結果、残り２手における、双変移動できるセルの数Q項は最大でも
Ｎ＝６，１０，１４．。。。の場合の０となり、このような移動は不可能であることがわかる。

なお、Ｊ項Ｌ項は参考であり証明には不要。

記号	N	C	D	E	F	G	H	I	J	L	Ｐ	Ｑ
項目	N例	type#	セル数	残り手数２までの 手数	男の最大 双変ホモ 移動数	女の最大 双変ホモ 移動数	双変 ホモ移動最大数	双変 へテロ移動最小数	両端男の 最大双変 へテロ移動数	両端女の 最大双変 へテロ移動数	移動不可中心セルの数 @N＞6	移動可能 中心数
式		N mod 4	２Ｎ＋３	N-3	[(N-1)/4]	[(N-2)/4]	F+G	Ｅ−Ｈ	[(E+1)/2]-F	[E/2]-G	７+4*(I+１)	D-P
type0	12	0	27	9	2	2	4	5	3	2	31	-4
type1	9	1	21	6	2	1	3	3	1	2	23	-2
type2	6	2	15	3	1	1	2	1	1	0	15	0
type3	7	3	17	4	1	1	2	2	1	1	19	-2

（６−２）
初手が双変移動　２手目が単変移動　、途中は全部双変移動、最後が純単変移動の場合　

（２）の手数１の状態から、単変移動した後の状態は
Ｎ≧６のとき　性の交換を同じとすると、一般に下記３パターンのみである。
また（　）内は（２）の図に対応する　Ｎ＝１２の場合の値である。

(1)の場合は黄色枠の４人が（５−３）により移動できないので、
Nが２小さい場合の（６−１）のケースに含まれ、不可能である。

(2)(3)の場合を（６−１）と同じ方法で検査すると以下である。
よって、可能性があるのは　
(2)type3　N=７＋4mの場合のみ。

type3が不可能であることは（６−５）で証明する。

（６−３）１〜２手目が双変移動　３手目が単変移動　、途中は全部双変移動、最後が純単変移動の場合

（２）の手数２の状態から、単変移動した後の状態は
Ｎ≧６のとき　性の交換を同じとすると、一般に下記５パターンのみである。
このうち、(1)(3)(4)�Dのパターンには（５−３）によりこれ以上移動できない部分があり、
下図の黄色枠部分を除外するとNが小さい場合の（６−２）のケースの一部に帰着できるので、数学的帰納法により不可能である。

(2)の場合を（６−１）と同じ方法で検査すると以下である。
よって、本ケースは不可能。

（６−４）始めのうちが双変移動　（４以上）手目が単変移動　、途中は全部双変移動、最後が純単変移動の場合

（２）の図の緑の部分が単変移動以降で不動部分になる。
従って、（２）の図で
(1)手数３のものはNが１小さい場合の手数２の場合に
(2)手数４以上のものはNが２小さい場合の手数が２少ないもの場合に
帰着でき、数学的帰納法により不可能である。

（６−５）　（６−２）の(2)のＮ＝７＋４ｍのケース

女性に注目すると　女の最大双変ホモ移動数は　
[(N-3)/4]=1+m=(N-3)/4 であって、無駄がない。

一方、Ｑ値は２≦４であって、ヘテロ双変移動が一つ増えたら、成立しなくなる。
以上より、全てのホモ双変移動は消費しなければならない。

この場合ホモ移動した左側の抜け殻分には女性の隣接関係は存在せず、全て移動先の３連続状態の内部の２こずつになる。

これらは、双変（ヘテロ）移動で切って行くしかなく、従って、ホモ移動先は４とびに連続していなければならない。
下図

この逆周りの距離をＮ＝７＋４ｍについて計算すると　

２Ｎ−４Ｇ＋２＝１４＋８ｍ−４ｍ−４＋２＝１２＋８ｍ＞３

(７）まとめ

以上から、関連問題である　リング状の問題でＮ≧６の場合の手数の最小はＮで、
全て１２種類存在することが証明できた。

なお、Ｎ≧６の条件は手数３以下の部分と残り手数３以下の部分が重ならないために必要な条件である。

実際　計算機で調べると、
Ｎ＝５の場合は　Ｎ≧６の場合の拡張の１２種以外に４種存在する。
すなわち１６種。

なお、Ｎ＝４の場合は　１４種存在。
Ｎ＝３の場合は６種であった。

（８）元の問題の解答

リングの問題を元の問題に変えるには以下の条件を付加すればよい。

（Ａ）リングに特有の　２Ｎ＋２（２６）、２Ｎ＋３（２７）からの移動を禁止。
（Ｂ）最後に全員つながるために、手数に関係ない反転、回転をしないとき、
最後の手が１または２Ｎ＋１（２５）であること。

１２種類の方法のうち（Ｂ）を満足するのは　Ｎが奇数ないし６のとき最後の手が１になるただ一つであり、Ｎが８以上の偶数では存在しない。

これらに（Ａ）の条件を課すと、Ｎが奇数の場合は全てＯＫであるが、
Ｎ＝６のケースはこれに抵触する。

よって、Ｎ≧６のとき　Ｎが偶数のときの最小手数はＮではない。

また　Ｎが奇数のときの最小手数はＮであり、その方法は唯一である。

以上

　◆　問題へもどる

　◆　今週の問題へ

数学の部屋へもどる