体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説

問題のおさらい

n を自然数とします。1 から n までの自然数が 1 つずつ書かれた n 枚のカードが 2 組あります。

これら 2n 枚のカードをよく混ぜ、A と B の 2 人に n 枚ずつ配ります。

A と B は、それぞれ自分の持ち札の中に番号が一致するカードがあればその 2 枚を捨てます。

捨てられるカードを全て捨てた後の A の持っているカードの枚数が k である確率を F(n, k) とします。

例えば F(1, 0)=0, F(1, 1)=1, F(2, 0)=1/3, F(2, 1)=0, F(2, 2)=2/3, F(4, 2)=24/35 です。

標準入力から、自然数 n と k (1 ≦ k ≦ n ≦ 100)が半角空白区切りで与えられます。
標準出力に 106×F(n, k) の整数部分の値を出力するプログラムを書いてください。

方針:何枚目のカードが残るかをはじめに固定

確率の求め方にはいろいろなやり方があります。ここではそのうちの一つを紹介します。A に配られたカードのうち、何枚目のカードが手元に残るかをはじめに固定してその確率を求め、そして全てのあり得る組み合わせについて確率を足し合わせる、という方針で求めます。

はじめに、A の 1~n 枚目のカードのうち、何枚目のカードが手元に残るかを固定します。ここでは話を分かりやすくするために、1~k 枚目のカードが手元に残ると仮定しましょう。後の (k+1)~n 枚目のカードが捨てられます。

さて、このような残り方をするには、各カードの数字はどうなっていないといけないでしょうか? 以下、n=13, k=5 の場合を例に、1~5 枚目が手元に残り、6~13 枚目が捨てられる確率を計算します。

まず 1 枚目についてです。これが手元に残るためには、この数字とペアのカードが B の方に配られてないといけません。そうなる確率は 13/25 です。

数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説

次に 2 枚目です。1 枚目と同じく、この数字とペアのカードが B の方に配られてないといけません。1 枚目の条件が満たされたときにそうなる確率は 12/23 です。

数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説

以降、同様にして、3 枚目、4 枚目、5 枚目に対する確率は、11/21、10/19、9/17 と求められます。

次は 6 枚目です。ここから先は、捨てられる確率を考えます。このカードが捨てられるためには、この数字とペアのカードが同じ A の方に配られてないといけません。そうなる確率は 7/15 です。

数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説

7 枚目についても、6 枚目と同様、この数字とペアのカードが A の方に配られてないといけません。そうなる確率は 5/13 です。(もし▲が 7 枚目にある場合は次の 8 枚目について考えます。)

数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説

以降、同様にして、8 枚目、9枚目に対する確率は、3/11、1/9 と求められます。

以上の確率をすべて掛け合わせたものが、はじめに固定した組みあわせでカードが残る確率となります。

1 2次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。