◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】
答え ６回
１つの手により 表１に示される数のグループに分類される。
これより、最善の場合は全部一致する１組を除いて残りが４等分される場合で、表２に示すように５回は試す必要がある。
一方、最悪の場合の平均的確率から見積もると６回程度となる。表３参照。
実際にこの辺をＰＣで探索すると、５回では無理で表４の手順により６回は可能であることが判った｡
なお、６回の手順は他にもある。
表４において各夫婦は 0〜４で表わされ、最初は ０１２３４ で試行する。
その結果５組一致なら終了。
Ｎ組一致なら表を下方に辿って、数値Ｎのところの右側の組を試行し、以下同様に試行する。
なおＮへはリンクJumpである。
表４をプログラム化（ＪavaＳcript)した.HTMLを添付する｡
| 表１ 初手分類 | 表２ 最善回数 | 表３ 最悪平均確率 | |||||||
| 一致数 | 場合数 | 回数 | 120 | 回数 | 120 | ||||
| 0 | 44 | 1 | 45 | 1 | 45 | ||||
| 1 | 45 | 2 | 11 | 2 | 16.90 | ||||
| 2 | 20 | 3 | 3 | 3 | 6.40 | ||||
| 3 | 10 | 4 | 1 | 4 | 2.40 | ||||
| 4 | 0 | 5 | 完成 | 5 | 0.90 | ||||
| 5 | 1 | 6 | 6 | 完成 | |||||
| 合計 | 120 |
|
|
||||||
| 1 | 2 | 3 | 4 | 5 | 6 |
| 01234 | |||||
| 0 | 12340 | ||||
| 1へ | 0 | 34120 | |||
| 2へ | 1へ | 0 | 42310 | ||
| 3へ | 2へ | 0 | 23401 | ||
| 3へ | 1 | 20413 | |||
| 2 | 43012 | ||||
| 1 | 23041 | ||||
| 0 | 30412 | ||||
| 1 | 43102 | ||||
| 2 | 24013 | ||||
| 3 | 43021 | ||||
| 2 | 30421 | ||||
| 0 | 24103 | ||||
| 1 | 34012 | ||||
| 2 | 40123 | ||||
| 3 | 34102 | ||||
| 2 | 34021 | ||||
| 1 | 21340 | ||||
| 0 | 13420 | ||||
| 0 | 42013 | ||||
| 3 | 42103 | ||||
| 1 | 32401 | ||||
| 2 | 14023 | ||||
| 3 | 10423 | ||||
| 2 | 13402 | ||||
| 1 | 34120 | ||||
| 0 | 40312 | ||||
| 1 | 40321 | ||||
| 2 | 30142 | ||||
| 3 | 43120 | ||||
| 2 | 32140 | ||||
| 0 | 24301 | ||||
| 1 | 23041 | ||||
| 2 | 23410 | ||||
| 2 | 20143 | ||||
| 2 | 23140 | ||||
| 0 | 32410 | ||||
| 0 | 14302 | ||||
| 1 | 42301 | ||||
| 2 | 12403 | ||||
| 1 | 32041 | ||||
| 2 | 32410 | ||||
| 2 | 24310 | ||||
| 0 | 13042 | ||||
| 1 | 13420 | ||||
| 2 | 20341 | ||||
| 3 | 32140 | ||||
| 1 | 10342 | ||||
| 2 | 14320 | ||||
| 2 | 12043 | ||||
| 1 | 42310 | ||||
| 1 | 12340 | ||||
| 0 | 21340 | ||||
| 1へ | 0 | 43201 | |||
| 2へ | 0 | 30124 | |||
| 3へ | 2 | 04123 | |||
| 1 | 40132 | ||||
| 1 | 03412 | ||||
| 2 | 40213 | ||||
| 0 | 03421 | ||||
| 3 | 34201 | ||||
| 1 | 23140 | ||||
| 0 | 41023 | ||||
| 1 | 31402 | ||||
| 1 | 20431 | ||||
| 3 | 24031 | ||||
| 2 | 23014 | ||||
| 3 | 23104 | ||||
| 2 | 21403 | ||||
| 1 | 32140 | ||||
| 0 | 04132 | ||||
| 0 | 13024 | ||||
| 1 | 20314 | ||||
| 1 | 14203 | ||||
| 1 | 41302 | ||||
| 2 | 10432 | ||||
| 0 | 04321 | ||||
| 3 | 14032 | ||||
| 2 | 04312 | ||||
| 1 | 32410 | ||||
| 0 | 21043 | ||||
| 1 | 42031 | ||||
| 2 | 43210 | ||||
| 3 | 02413 | ||||
| 2 | 32014 | ||||
| 0 | 03142 | ||||
| 1 | 24130 | ||||
| 1 | 30241 | ||||
| 1 | 31420 | ||||
| 2 | 31042 | ||||
| 1 | 34210 | ||||
| 3 | 32104 | ||||
| 2 | 23140 | ||||
| 0 | 10324 | ||||
| 1 | 10243 | ||||
| 0 | 41320 | ||||
| 2 | 02143 | ||||
| 2 | 42130 | ||||
| 3 | 21340 | ||||
| 1 | 12304 | ||||
| 2 | 12430 | ||||
| 2 | 02341 | ||||
| 1 | 13240 | ||||
| 2 | 12340 | ||||
| 0 | 31240 | ||||
| 0 | 21430 | ||||
| 0 | 03124 | ||||
| 1 | 04132 | ||||
| 2 | 20134 | ||||
| 1 | 40231 | ||||
| 0 | 01423 | ||||
| 1 | 04213 | ||||
| 2 | 41032 | ||||
| 2 | 32410 | ||||
| 0 | 41203 | ||||
| 1 | 31024 | ||||
| 2 | 30214 | ||||
| 1 | 21340 | ||||
| 0 | 13204 | ||||
| 0 | 02431 | ||||
| 1 | 03241 | ||||
| 3 | 21304 | ||||
| 2 | 21430 | ||||
| 2 | 21340 | ||||
| 0 | 12034 | ||||
| 1 | 02314 | ||||
| 0 | 14230 | ||||
| 3 | 01342 | ||||
| 2 | 31240 | ||||
| 3 | 12340 | ||||
| 0 | 21340 | ||||
| 0 | 03214 | ||||
| 2 | 04231 | ||||
| 1 | 31204 | ||||
| 1 | 01432 | ||||
| 2 | 21034 | ||||
| 1 | 21340 | ||||
| 0 | 10234 | ||||
| 2 | 02134 | ||||
| 2 | 42310 | ||||
| 0 | 01243 | ||||
| 1 | 01324 | ||||
| 2 | 41230 |
◆出題者の山梨県 Footmark さんからのコメント。
みごと正解です。
最悪の場合でも５回までで正解の並び方が判明して、６回目で５組一致します。
証明できませんが、これが最善のようです。
◆山梨県 Footmark さんからの解答。
【追加問題１】
Ｍ(Ｎ,０) はＮ個の乱列の数に当たりますから、包除原理より次式が得られます。
Ｍ(Ｎ,０)
| ＝Ｎ！−NＣ1(Ｎー１)！＋NＣ2(Ｎー２)！＋…＋(−１)NNＣN(Ｎ−Ｎ)！ |
| ＝Ｎ！{１− | １ １！ | ＋ | １ ２！ | − | １ ３！ | ＋…＋(−１)N | １ Ｎ！ | } |
Ｍ(Ｎ,１) は、１箇所一致はＮ箇所あり、
その各々の一致箇所に対して(Ｎー１)個の乱列の数になるので、
Ｍ(Ｎ,１)
＝Ｎ{Ｍ(Ｎ−１,０)}
| ＝Ｎ！{１− | １ １！ | ＋ | １ ２！ | − | １ ３！ | ＋…＋(−１)N-1 | １ (Ｎ−１)！ | } |
∴ ｜Ｍ(Ｎ,０)−Ｍ(Ｎ,１)｜＝｜(−１)N｜＝１
[補足]
数列 １,２,３,… の並び替えで、どの数も元の位置にない数列を乱列(derangement)と呼びます。
【追加問題２】
【追加問題１】より
Ｍ(Ｎ,０)
| ＝Ｎ！{１− | １ １！ | ＋ | １ ２！ | − | １ ３！ | ＋…＋(−１)N | １ Ｎ！ | } |
ですから、
| Ｍ（Ｎ，０） Ｎ！ |
| ＝１− | １ １！ | ＋ | １ ２！ | − | １ ３！ | ＋…＋(−１)N | １ Ｎ！ |
∴ ｎ→∞のとき
| Ｍ（Ｎ，０） Ｎ！ | ＝ｅ-1≒０.３７ |
（ただし，ｅは自然対数の底）
◆愛知県 Y.M.Ojisan さんからのコメントと解答。
【追加問題１，２コメント】
正解です。【追加問題３解答】
一致組数の最大値で分類すると 最大５組 最大３組 最大２組 最大１組 の４種ある。
かならず合計５組だから 最大０組はありえない。
（あ）最大５組の場合
一致組数円順列は ０ ０ ５ ０ ０ しかなく、対称である。
（い）最大３組の場合
（う）最大２組の場合
個数５の円順列で考えるので、一致している最大２組が 夫並びの
＜１＞〜＜５＞のどれかにおいて (1)(2)か(1)(3)位置であると限定しても一般性を失わない。
一方、残り３組は一致していない条件より、２タイプに限られる
これら ２×２＝４ケースを実際に調べると （下図参照）一致組数円順列は
０ ２ １ ２ ０ か ２ ０ １ ０ ２
であり、対称である。
なお、下図においてはＡ−Ｅを再命名し、夫並びを２組一致した場合が先頭になるように回転して考えている。
（え）最大１組の場合
一致組数円順列は １ １ １ １ １ しかなく、対称である。
以上より一致組数円順列は右左回り対称である。
【追加問題４解答】
答え ｎ≦５
∵下図のようにｎ≧６では 「妻並び例外」に対して
夫並び＜Ｐ＞は［ｎ−３］組一致し、２より大きいので単独最大値で対称中心である。
一方＜Ｐ−１＞と＜Ｐ＋１＞の一致組数は０と２で等しくない。
よって、ｎ≧６では例外が必ず存在し成立しない。
n=５は追加問題３で成立証明済み。
n=４は追加問題３の（あ）（い）（え）と同様の方法で成立が証明される。
n=３は追加問題３の（あ）（え）と同様の方法で成立が証明される。
n=２,１は明らかに成立する。
◆出題者の山梨県 Footmark さんからのコメント。
【追加問題３】,【追加問題４】とも、正解です。
５組までの時は対称になるのに、６組以上では対称になりません。
元の問題の解を得るのに、私はその対称性を利用しました。