【挑戦】(数セミ)エレガントな解答をもとむを解く㊴

本記事の内容
今日の問題
チャレンジの結果…
筆者の解答 (解けなかったのであまり意味は無いですが)
投稿されたエレガントな解答
！次回予告！
筆者からの挑戦状！ (5分で解けるかな？)
結

本記事の内容

本記事は『数学セミナー』(日本評論社)に掲載されている”エレガントな解答をもとむ”に出題されいている問題を1時間で解けるか、という挑戦をする記事です。

本記事を読むにあたり、前提知識は基本的に必要ありませんが、以前紹介した記事の内容を使う場合はその旨を記述することにします。

今回も「エレガントな解答をもとむ selections」に掲載されいている問題です。

※「これを5分で解けるかな！？」も是非挑戦してみて下さい！

前回の問題については以下の記事を御覧ください！

【挑戦】(数セミ)エレガントな解答をもとむを解く㊳

...

今日の問題

A、B、C、D、E、Fの6個の金庫と、それらを開ける鍵a、b、c、d、e、fが1本ずつあります。いたずらモノがどの金庫にも別の鍵を1本ずつ入れて、6個の金庫とも締めてしまいました。このため、壊さないと金庫は開けられません。
　しかし、すべての金庫を壊す必要はないのです。例えば、Aの金庫を壊したとき、中にbの鍵が入っていれば、その鍵でBの金庫は開けられます。また、Bの金庫にcの鍵が入っていれば、その鍵でCの金庫も開けられます。さらに、Cの金庫にdの鍵が入っていれば、その鍵でDの金庫も開けられます。しかし、Dの金庫にaの鍵が入っていれば、EとFの金庫は開けられません。そこで、またEかFの金庫を壊すことになります。
　どの金庫にも別の鍵を1本ずつデタラメに入れたとき、すべての金庫を開けるには、平均で何個の金庫を壊す必要があるでしょうか。
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p28-p29.

チャレンジの結果…

チャレンジの結果…解けませんでした…

ただ、「これが分かれば解けるだろうな」というところまではできました(という言い訳)。

筆者の解答 (解けなかったのであまり意味は無いですが)

問題を見て真っ先に思ったのは「平均？相加平均のこと？それとももしかして期待値？」です。
おそらく期待値じゃないかなあと思い、その前提のもとで取り組みました。

さて、金庫$S\left( =A,\ B,\ C,\ D,\ E,\ F\right)$に対して、その金庫$S$に鍵$i\left( =a,\ b,\ c,\ d,\ e,\ f\right)$が入っているという状態を
$$
I(S)=i
$$
と書くことにします。

数個例を考えてみます。

例1.

$I(A)=a$、
$I(B)=b$、
$I(C)=c$、
$I(D)=d$、
$I(E)=e$、
$I(F)=f$

すなわち、全ての金庫に対して、自身の鍵が入っている状態です。
この場合は、どの金庫を壊したとしても、壊した金庫の鍵しか出てきませんので、6個すべての金庫を破壊しなければなりません。
つまり、破壊の回数は6回です。

例2.

$I(A)=b$、
$I(B)=c$、
$I(C)=f$、
$I(D)=a$、
$I(E)=e$、
$I(F)=d$

これは、2回破壊すればOKです。

例3.

$I(A)=d$、
$I(B)=e$、
$I(C)=a$、
$I(D)=b$、
$I(E)=f$、
$I(F)=c$

これは、1回破壊すればOKです。

例4.

$I(A)=b$、
$I(B)=a$、
$I(C)=d$、
$I(D)=c$、
$I(E)=f$、
$I(F)=e$

この場合は、3回破壊すればOKです。

例5.

$I(A)=b$、
$I(B)=c$、
$I(C)=d$、
$I(D)=a$、
$I(E)=f$、
$I(F)=e$

この場合も、2回破壊すればOKです。

さて、例を上げたところで、それぞれの金庫にどのような関係性があるかを考えてみました。
すると、次の円順列のような関係性があることがわかります。

このくるくる回るサイクルの個数が金庫を壊す回数を指しています。
しかも、巡回しているわけですから、1サイクルにおいてどこを壊してもOKです(破壊の回数は変わらない)。

つまり、「平均して何サイクルある？」という問題になります。
今、平均は期待値のことという仮定を置いていますので、「サイクル数の期待値は？」という問題になります。

期待値だったとすると、

壊す回数$x$	1	2	3	4	5	6
確率$P(x)$	$P(1)$	$P(2)$	$P(3)$	$P(4)$	$P(5)$	$P(6)$

という表が書けますので、求める答えは
$$
\sum_{x=1}^6xP(x)
$$
です。

では、各$P(x)$を求めていきましょう、ということになりますが、これが求まらなかったという話です。

※以下の表は、間違ったことを書いています。

●$P(1)$について

最初は、以下のように考えました。

金庫	$A$	$B$	$C$	$D$	$E$	$F$
金庫に入る鍵のパターン数	$5$	$4$	$3$	$2$	$1$	おん？

しかし、直ちに間違っていることに気が付きました。
そこで、再度考え直してみました。

まず、壊す回数が1回ですので、金庫Aを壊すということにしましょう(どれを壊すことにしても変わらない)。

すると、$I(A)=a$だった場合は、$A$以外の金庫も破壊しなければならないので、$I(A)\neq a$です。
故に、金庫$A$に入り得るのは$a$以外である$b,c,d,e,f$の5種類です。

次に、金庫$B$についてです。
$I(A)\neq a$という状態で、金庫$B$に入る鍵のパターン数は$5$個、または$4$個です。
$I(A)=b$だった場合は$I(B)=a,c,d,e,f$の5パターン、$I(A)\neq b$だった場合は、$a,b,c,d,e,f$から$I(A)$と$b$を除いて4パターン。

というように、各金庫に対して場合分けをしながら進めていき、最後合算するということになります。
しかし、これでは場合が複雑になってしまいますし、結局力技で全パターンを数え上げているのと大差ありません。
およそエレガントとは言えないなあ、と思いながら他の方法を模索していて時間切れでした。

投稿されたエレガントな解答

（前略）

　最初にお詫びしなければならないのは、小生の説明不足で、問題が2通りに解釈されたことです。小生は

　「A：どの金庫にも、それを開ける鍵は入れない」

という意味で出題しましたが、

　「B：その金庫を開ける鍵も入れられる」

と解釈した解答が24通も寄せられました。また、AとBの解答を併記したものも12通ありました。このため、全射を問題A、後者を問題Bとして、両方の解答を示します。ただし、問題Bには巧妙な開放があって、壊す金庫の平均個数($K_n$で表す)は、一般の$n$個の金庫にたいして、

$$
K_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\tag{1}
$$

となります。このため、$n=6$とおけば、$\displaystyle K_6=\frac{49}{20}$がすぐに出ます。まず、この開放から説明します。

　いま、Aの金庫にbの鍵を入れることをb→Aで表すと、出題の例はb→A、c→B、d→C、a→D、f→E、e→Fです。このため、Aの金庫を壊すと、B、C、Dの金庫が順次に明けられます。また、Eの金庫を壊すと、Fの金庫が明けられます。こうして、AとEの2個の金庫を壊せば、残りの金庫はすべて開けられます。これは、金庫を開ける手順が

　A→B→C→D→(Aに戻る)、
　E→F→(Eにう戻る)

の2個のサイクルに分かれるからです。このため、
　A→B→C→D→E→F→(Aに戻る)
の1個のサイクルになれば、どれか1個の金庫を壊せば済みます。こうして、何個のサイクルができるかを調べればよいことになります。このとき、どの金庫にどの鍵を入れたかが大切で、金庫の壊し方の順序に無関係に、壊す金庫の個数は自動的に決まります。

　これを踏まえて、問題Bを考えます。最初に壊す金庫をAとすると、それにaの鍵が入っていれば、壊す金庫の平均個数は$1+K_{n-1}$、その確率は$1/n$です。また、aの鍵が入っていなければ、壊す金庫の平均個数は$K_{n-1}$、その確率は$(n-1)/n$です。これは$K_n$が金庫の壊し方の順序に無関係なためで、まずaの鍵が入っている金庫を壊せばよいからです。こうして
\begin{eqnarray}
K_n&=&\frac{1}{n}\left( 1+K_{n-1}\right)+\frac{(n-1)}{n}K_{n-1}\\
&=&\frac{1}{n}+K_{n-1},
\end{eqnarray}
が成り立ちます。ところが、$K_1=1$は明らかなので、式(1)が簡単に得られます。

（中略）

　問題Aに移り、まず金庫が6個のときを考えます。いま、$m$個の金庫で作るサイクルを「$m-$サイクル」と呼ぶと、

　①　1個の6-サイクル
　②　2個の3-サイクル
　③　1個の4-サイクル
　④　3個の2-サイクル

の4通りとなります。そこで、それぞれに何通りの組み合わせが或るかを調べます。
　①の場合は、金庫Aに津八雲区すると、つぎの金庫の選び方は5通り、その次は4通り、そのつぎは3通りなどとなるので、全部で

$5\times4\times3\times2\times1=120$通り①

です。②の場合は、金庫Aを含むサイクルに着目すると、次の金庫の選び方は5通り、そのつぎは4通りです。もう一方の3-サイクルでは、残りのどれかの金庫に着目すると、次の金庫の選び方は2通り、その次は1通りなので、全部で

$5\times4\times2\times1=40$通り②

です。③の場合は、金庫Aが4-サイクルにあれば、つぎの金庫の選びかたは5通り、そのつぎは4通り、そのつぎは3通りです。このとき、2-サイクルは自動的に決まります。金庫Aが2-サイクルにあれば、もう1個の金庫の選び方は5通りです。また、4-サイクルでは、残りのどれかの金庫に着もk，うすると、つぎの金庫の選び方は3通り、そのつぎは2通り、そのつぎは1通りです。こうして、全部で

$5\times4\times3+5\times3\times2\times1=90$通り③

です。④の場合は、金庫Aに着目すると、もう1個ｎ金庫の選び方は5通りです。つぎに、別の2-サイクルを見て、どれかの金庫に着目すると、もう1個の金庫の選び方は3通りです。すると、最後の2-サイクルは自動的に決まるので、全部で

$5\times3=15$通り④

です。①、②、③、④を総合すると、全部で

$120+40+90+15=265$通り

の組み合わせとなります。

　ここで、壊す金庫の個数はサイクルの個数そのものであることに注意すると、1個、2個、3個の金庫を壊さなければならない確率はそれぞれ
$$
\frac{120}{265},\quad \frac{130}{265}\left( =\frac{40}{265}+\frac{90}{265}\right),\quad \frac{15}{265}
$$
となり、壊す金庫の平均個数($L_6$で表す)は
$$
L_6=\frac{120}{265}+2\times\frac{130}{265}+3\times\frac{15}{265}=\frac{85}{53}\tag{2}
$$
となります。

　最後に、金庫が$n$個のときの問題Aに簡単に触れておきます。まず、2-サイクルが$k_2$個、3-サイクルが$k_3$個、$\cdots$、$n-$サイクルが$k_n$個あれば、
$$
2k_2+3k_3+\cdots+nk_n=n
$$
は明らかです。すると、これを満たす鍵の入れ方は
$$
C=\frac{n!}{k_2!2^{k_2}!3^{k_3}\cdots k_n!n^{k_n}}\tag{3}
$$
となることが知られています。手間さえいとわなければ、これから平均個数$L_n\ (n\geq 7)$も順次に計算できます。一方、サイクルの個数は
$$
k=k_2+k_3+\cdots+k_n
$$
で、これを満たす鍵の入れ方を$d_{n,k}$で表すと、特定の鍵が3以上のサイクルに含まれているか、それとも2-サイクルに含まれているかのどちらかなので、
$$
d_{n,k}=(n-1)\left( d_{n-1,k}+d_{n-2,k-1}\right)\tag{4}
$$
が成り立ちます。されに、その金庫を開ける鍵も入れられる(問題B)とすると、1-サイクルは平均でちょうど1個できることも簡単に導けます。これから、大数の法則によって、
$$
L_n\fallingdotseq K_n-1=\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\tag{5}
$$
が成り立ちます。

（後略）
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p247-p250.

どうやら、筆者は問題Bを考えていたようです。
出題者は謝罪していますが、筆者も「全ての金庫に自身の鍵を格納するなんて、実際どうやるんだ？マスターキーみたいなのがあるのか？まあ、あってもおかしくないのかもしれん」と半信半疑でした。

そして、やはり平均というのは期待値を指すようでした。

考え方自体は間違っていなかったようですが、悔しい結果です。

！次回予告！

1から6までの自然数$\left\{ 1,2,3,4,5,6\right\}$を考え、その中から隣り合う数を含まないようにして何個かの数を選び出します。すると、1個選ぶときは
$$
\left\{ 1\right\},\ \left\{ 2\right\},\ \left\{ 3\right\},\ \left\{ 4\right\},\ \left\{5\right\},\ \left\{ 6\right\}
$$
の6通り、2個選ぶときは
\begin{eqnarray}
&&\left\{ 1,3\right\},\ \left\{ 1,4\right\},\ \left\{ 1,5\right\},\ \left\{ 1,6\right\},\ \left\{ 2,4\right\},\\
&&\left\{ 2,5\right\},\ \left\{ 2,6\right\},\ \left\{ 3,5\right\},\ \left\{ 3,6\right\},\ \left\{ 4,6\right\}
\end{eqnarray}
の10通り、3個選ぶときは、
$$
\left\{ 1,3,5\right\},\ \left\{ 1,3,6\right\},\ \left\{ 1,4,6\right\},\ \left\{ 2,4,6\right\},\
$$
の4通りとなります。
　これと同じ方法で、1から10までの10個の自然数を考えると、1個、2個、3個、4個、5個の数を選び出す仕方はそれぞれ何通りあるでしょうか。また、一般の1から$n$までの自然数を考えるときはどうでしょうか。
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p29.

前回の問題は【1時間チャレンジシリーズ】その㊳を御覧ください。

筆者からの挑戦状！ (5分で解けるかな？)

知人から「次の問題を解説して」と言われまして、今回はその問題を出したいと思います。

宇宙人「うちは10進数を使います」
地球人「おお、私達と一緒ですね」
宇宙人「ところで7の倍数かどうかを判定するには、すべての桁の和が7の倍数かどうかを確かめればいいですよね」
地球人「それは3と9の倍数の判定方法ではないですか」
宇宙人「なるほど、どうやら私達と一緒ではないようですね」

地球人（もしかして8進数？）宇宙人（……おそらく12進数だろうな）
https://twitter.com/skytomo221/status/1684398205335658496?s=53&t=PeLNzAAVdDvlb1F4DZrxcQ　および　https://twitter.com/skytomo221/status/1684398617245908992?s=53&t=PeLNzAAVdDvlb1F4DZrxcQ

この状況で、宇宙人と地球人の基数を求めよ、ということです。
筆者はちょうど5分くらいでした。

結

いかがでしたか？
今回は数セミの「エレガントな解答をもとむ」に挑戦してみる、という記事でした。

読者の皆様も是非一度挑戦してみて下さい！
そして、「筆者からのの挑戦状」にも是非挑戦していただき、解答をコメントで教えて下さい！

質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
Twitterでもリプ、DM問わず質問、コメントを大募集しております！

他の「エレガントな解答をもとむ」の問題に挑戦してみたい方はぜひ以下の書籍をお買い求め下さい！

壊す回数\(x\)	1	2	3	4	5	6
確率\(P(x)\)	\(P(1)\)	\(P(2)\)	\(P(3)\)	\(P(4)\)	\(P(5)\)	\(P(6)\)

金庫	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
金庫に入る鍵のパターン数	\(5\)	\(4\)	\(3\)	\(2\)	\(1\)	おん？