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

本記事の内容

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

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

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

※今回からちょっと趣向を変えた「これを5分で解けるかな！？」を初めたいと思います。

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

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

...

for-spring.com

2023.04.16

今日の問題

円と$n$本の直径からなる図形をかきます。各直径の両端について、片方に○印、もう片方に✕印をつけます。どちらを○印にするかは確率$1/{2}$で決め、他の直径の印付とは独立であるとします。
　○印が円周で連続する部分を島とよびます。下図の例では、点線で囲った3個の島があります。
　さて、$n$本の直径に印付をおこなったとき、ちょうど$k$個の島ができる確率はいくらでしょうか？

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

チャレンジの結果…

チャレンジの結果….解けませんでした。
なんと恥ずかしいことに、問題文を誤認しておりまして…

1時間のうち40分は無駄に時間を使ってしまうというなんとも情けない話です。

残り20分で「なんとかならんか」とやってみましたが、解答という形にはたどり着きませんでした。

筆者の情けない解答

「筆者の解答はこれだ！」と言いたいところですが…

ちょっとその前に

先述の通り、筆者は問題文を誤認していました。

筆者は「○が“複数個”連続する部分を“島”と呼ぶのだな？」と理解していたのですが、実際はそうではなくて、○の両端が✕だったとしてもその○は“島”と認識するとのことでした。

内緒

「じゃあ“連続する”って表現は変えてほしいなあ…」と思ったのは秘密。

この誤認のマズかったところは、解答を進めても違和感に気が付かないところです(単純に私が気が付かないということを言い訳がましく述べただけですが)。

誤認していた段階での筆者の解答は、全く意味をなさないので、それについては記述せずに残り20分でなんとかしようとした軌跡を記すことにします….

嗚呼…悲しい…

残り20分でなんとかしようと頑張ってみたけどダメだった解答

そもそも、求めたい確率はどのようにして求まるのか？を考えました。
$n$本の直径に知りし付を行ったとき、ちょうど$k$個の島ができる確率を$p(n,k)$と書いたとすると、

です。
分母の「印付けのパターン数」は、○✕の2種類の印を$n$本につけるため$2^n$と直ちに求まります。

問題は分子ですが、全然イメージが湧かなかった為、実験することにしました。

「実験している場合なのか…？」と思いながらも「いきなりやっても分からんな」ということでいくつか実験をしました。

1. $n=1$のとき
確率が$1$で1つの島ができます($n=1$の実験の段階で気がつけたのでは？と今思います)。
この場合、$k=1$以外起こりえません。
2. $n=2$のとき
これも確率が$1$でちょうど1個の島ができます。
$k$も$k=1$以外起こりえません。
3. $n=3$のとき
1. $k=1$のとき
このとき、パターンとしては6パターンあります。
$n=3$ですから、求めたい確率は$\displaystyle\frac{6}{8}=\frac{3}{4}$です。
2. $k=2$のとき
これは起こりえませんので、確率は$0$です。 　
3. $k=3$のとき
以下の2パターンです。
故に、求めたい確率は$\displaystyle\frac{2}{8}=\frac{1}{4}$です。 　

特にめぼしい成果は得られなかった気がします。

ただ、図を描いてみると、島の両端には必ず✕印がついています。
この✕印のペアの位置を考えればよいのでは？と感じました。
また、島の数と✕印のペアの数は一致しています。
とすれば、$n$個の場所から$k$個の場所を選ぶ順列が求めたい数となるわけですので、そのパターン数は${}_nC_{k}$です。

したがって、求めたい確率は$\displaystyle\frac{{}_nC_{k}}{2^n}$と考えました。

ただ、これは予想ですし「そんな気がする」程度で解けたとは言えません。

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

（前略）

結論を先に述べると、島の数$k$は奇数であることが必要で、そのとき確率は$\left.\begin{pmatrix}n \\k \end{pmatrix}\right/2^{n-1}$となります。ここで$\begin{pmatrix}n \\k \end{pmatrix}$は$n$個から$k$個を取り出す場合の数を表します。(${}_nC_{k}$とも書きますね。)
　寄せられた解答の方針は本質的にひとつで、「$k$個の島を持つ印づけの総数を直接数える」というものです。おそらく$\left.\begin{pmatrix}n \\k \end{pmatrix}\right/2^{n-1}$という結果を見て、その理由を考えた方が多かったでしょう。理由がわかってしまえば証明は簡単で、実際1ページの解答が正解者の半数近くありました。

（中略）

$n$本の直径の両端の点を時計まわりの準に$a_1,\cdots,a_{2n}$とする。添字の番号は$2n$を方として$a_0=a_{2n}$、$a_{2n+1}=a_1$などと解釈する。このとき、$a_ia_{i+n}\ (i=1,\cdots,n)$が直径である。印づけはどれも同程度の確からしさから起こるので、$k$個の島ができる確率$P(n,k)$は、
$$P(n,k)=\frac{k個の島をもつ印づけの総数}{印づけの総数}\tag{1}$$
で与えられる。印づけの総数は$2^n$だから、$k$個の島をもつ印づけの総数がわかればよい。
　印付け$\sigma$に対して
$$\sigma(a_i)= \begin{cases} 1&a_iが○印のとき\\ -1&a_iが✕印のとき \end{cases}$$
と定める。また、隣接する2点$a_i,a_{i+1}$に対して、$\sigma(a_i)\cdot\sigma(a_i)=-1$のときの対$(a_i,a_{i+1})$を$\sigma$の節と呼ぶ。島$\left\{ a_i,a_{i+1},\cdots,a_j\right\}$に、二つの節$(a_{i-1},a_i)$、$(a_j,a_{j+1})$が対応する。(図1)

　この対応で$\sigma$の島の数$I(\sigma)$は、$\sigma$の節の数の半分であることがわかる。さらに、$(a_i,a_{i+1})$が節からその反対側の対$(a_{i+n},a_{i+n+1})$も節となるので、
$$I(\sigma)=「(a_1,a_2),\cdots,(a_n,a_{n+1})のうち節である対の数」\tag{2}$$
を得る。
　ここで、節ごとに$\sigma(a_i)$の符号が変わることに注意すると、(2)から$\sigma(a_{n+1})=(-1)^{I(\sigma)}\cdot\sigma(a_1)$がわかる。また、$\sigma(a_1)$と$\sigma(a_{n+1})$は対称点だから異符号。したがって、島の数$I(\sigma)$は、奇数でなければならない。
　さて、$k$が奇数のとき$I(\sigma)=k$となる印づけ$\sigma$の総数を数えよう。これは(2)より$(a_i,a_{i+1})\ (i=1,\cdots,n)$の中に$k$個の節を持つ印づけの数で、$2\begin{pmatrix}n \\k \end{pmatrix}$個である。実際、$\sigma$は$\sigma(a_1)$と$(a_i,a_{i+1})\ (i=1,\cdots,n)$における節のいちによって一意的に決まり、$\sigma(a_1)$は$\pm$の2通り、$k$個の節の配置は$\begin{pmatrix}n \\k \end{pmatrix}$とおりである。結局(1)より、
$$P(n,k)= \begin{cases} 0&kが偶数のとき\\ \left.\begin{pmatrix}n \\k \end{pmatrix}\right/2^{n-1}&kが奇数のとき \end{cases}$$
を得る。

（後略）

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

これを見ると、20分にしては結構よいところまで行ったのではないかな、と思いましたが、間違いは間違いです。

さらに、パターン数が2倍になるということを失念していました…残念です…

！次回予告！

ウィンブルドンのテニスや甲子園の高校野球など、勝ち抜きトーナメント形式で優勝者を決める方式は、参加者数に比べて総試合数が少なくてすむ利点があります。すなわち、参加者が$n$なら総試合数は$n-1$となります。もし総当たりリーグ戦にすれば、$\displaystyle\frac{n(n-1)}{2}$試合が必要ですから、$n$が大きい場合に総試合数の差がはっきりします。
　勝ち抜きトーナメントの欠点は、半数の参加者が1試合だけで姿を消してしまうことです。そこで、1敗で失格という規則を少しだけ緩和して、2敗で失格という規則を考えます。このとき、総試合数はいくつになるでしょうか。また、このときのエレガントな組合せ方式を求めてください。毎回残っている参加者が抽選で対戦相手を決めるような方式でなく、おおよその対戦表が予め決まっている方式を考えて下さい。

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

この問題は来週挑戦します！
是非この1週間で解いてみて下さい！

前回の問題は【１時間チャレンジシリーズ】挑戦㊱を御覧ください！

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

今回から、サクッと挑戦できる問題を筆者が考えて出題したいと思います！
5分程度で解ける問題を出していきたいと思います。

基準として、筆者は4分40秒で解けました。

解けた方は、本記事へコメントするか、Twitter、instagramのDMで解答を送って下さい！

結

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

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

質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ一週間ほどでお答えします。
(難しかったらもう少しかかるかもしれませんが…)

Twitterでもリプ、DM問わず質問、コメントを大募集しております！

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