Pythonの基礎  冬休み短期スクール 受付中

中高生向けの冬休み短期スクールを受付中です。

短期スクールの詳細はこちら

東大の確率問題を瞬殺で解く 3個の赤玉とn個の白玉を無作為に環状に並べる・・・

サイエンス記事

生徒に教えてもらった1989年の東大入試問題です。

3個の赤玉とn個の白玉を無作為に環状に並べるものとする。このとき白玉が連続してk+1個以上並んだ箇所が現れない確率を求めよ。ただしn/3<=k<n/2とする。

有名な問題のようで、ネットで検索するといくつも解答例が出て来ます。

どれもが、赤玉にはさまれる白玉の個数をa, b, cとして延々と解いています。

しかし、東大入試問題にはエレガントな解法がある場合がよくあります。

ラテラルシンキングで逆転の発想をしてみましょう。

実は、赤玉にはさまれる白玉の個数を全てk個としてしまえば簡単です。ただし、k個には空席も含まれるとするのです。

以下に具体的に説明しましょう。

赤玉をR1, R2, R3とし、R1を固定して考えます。

まず、全体の場合の数は白玉n個+赤玉2個の(n+2)個から赤玉2個を選ぶ組み合わせの数なので、

(n+2)C2通り。

次に下図(上の方)のように空席を含めて考えます。空席の数はk-x>=0, k-y>=0, k-z>=0です。

空席は全部で3k-(x+y+z)=3k-n個あります。

下図(下の方)のように空席と赤玉2個の合計3k-n+2個から赤玉2個を選ぶ組み合わせは

(3k-n+2)C2通り。

よって求める確率をpとすると

p=(3k-n+2)C2 / (n+2)C2=(3k-n+2)(3k-n+1)/((n+2)(n+1))

 

この方法なら3分もあれば解けるでしょう。

せっかくなので、具体的に確率を計算してみましょう。

n=10000として、kを所定の範囲で変化させ、そのときの確率pを計算します。

Pythonのプログラムは以下のようにすれば良いでしょう。

%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

n=10000
k1=int(n/3)+1
k2=int(n/2)
print(k1, k2)
k = np.arange(k1, k2)
p = (3*k-n+2)*(3*k-n+1)/(n+2)/(n+1)

plt.plot(k, p)
plt.xlabel('k')
plt.ylabel('p')
plt.title('p = (3*k-n+2)*(3*k-n+1)/(n+2)/(n+1)')
plt.grid()
plt.savefig('p=f(k).png')

 

kを横軸に、pを縦軸にとったグラフが以下のグラフです。

nが十分大きいとき、kの最大値においてpは0.25に近づいていくことがわかります。