ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「マイナー・ゲーム」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

n 人のプレイヤーで「少数決」というゲームを行います。

ゲームは次の手順で進みます。

各プレイヤーは、投票用紙にAまたはBの文字を記し投票します。投票は記名式です。他のプレイヤーの投票内容は分かりません。
全員が投票し終わったら開票します。その結果、少数派になる回答をした者が勝者となります。例えばAが 3 票、Bが 4 票の場合は、Aを投票した 3 名が勝者です。AとBが同数の場合や、全員がAの場合、全員がBの場合は、全員が勝者です。
勝者はそのまま勝ち残り次の投票に進めますが、敗者はそこで脱落します。
以上が 1 回の「ターン」です。この要領でターンを繰り返し、勝ち残りが 1 人か 2 人になるまでゲームを続けます。

各プレイヤーはAまたはBをランダムに選んで投票します。
このとき、n 人のプレイヤーから始めてゲームが終了するまでのターンの回数の期待値を F(n) と定義しましょう。

例えば F(3) = 4/3 です。3 人の投票の仕方は計 23= 8 通りあります。このうち全員がAまたは全員がBの場合(2 通り)は 3 人ともが勝者となりますが、それ以外の場合(6 通り)は 1 名の勝者が決まりゲーム終了します。

1 回目のターンでゲームが終了する確率は 6/8 = 3/4 です。
2 回目のターンでゲームが終了する確率は (1/4)×(3/4) です(1 回目で終了せずかつ 2 回目に終了する確率)。
3 回目のターンでゲームが終了する確率は (1/4)2×(3/4) です(1, 2 回目で終了せずかつ 3 回目に終了する確率)。

したがって期待値は 1×(3/4)+2×(1/4)×(3/4)+3×(1/4)2×(3/4)+… = 4/3 となります。

同様に、F(4) = 2,F(5) = 16/15,F(7) = 1.7566137…,F(8) = 2.2028985… となることが確かめられます。

標準入力から、自然数 n(3 ≦ n ≦ 100)が与えられます。
標準出力に、F(n) を 106 倍した値の整数部分を出力するプログラムを書いてください。

方針

確率・期待値に関する問題です。確率というと、学校の試験などで苦労した記憶がある方もいらっしゃかもしれません。丁寧に見ていきましょう。

期待値の求め方としてよく知られているのは、ターンの回数を k とし、すべての k について、k×(ターンがちょうど k 回で終了する確率)の和を求めるという方法です。ですが、「ターンがちょうど k 回で終了する確率」というのは、容易には求められません。別の方法を考えましょう。

ここでは、1 ターン後の状態を考えましょう。類似した考え方は過去の記事でも登場しています。(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。1 ターン後、プレイヤー数が減ったとすると、それは問題のサイズ(つまり n)が一回り小さくなったことを意味します。つまり、より小さな n に対する F(n) の値が分かっていれば、より大きな n に対する F(n) の値が計算できるということです。別の言い方をすると、F(n) の漸化式 が導ければよいということです。

n=7 の場合を例にします。7 人から始めて、1 回ターンを終えたとき、プレイヤー数はどのようになっているでしょうか。

投票結果は全部で 8 通りのケースがあります。Aの人数が、図の上から順に、0人、1人、2人、3人、4人、5人、6人、7人 となるケースです。その結果、少数派が勝ち残り、プレイヤー数はそれぞれ、7 人、1 人、2 人、3 人、3 人、2 人、1 人、7 人へと変わります。つまり 1 ターン後にはこのいずれかの状態に移るということです。

さて、これらの出来事が起こる確率を考えましょう。7 人の投票の仕方は、全部で 27=128 通りあります。このうち、Aが 0 人、Bが 7 人となるのは 1 通りだけですから、その確率は 1/128 です。また、Aが 1 人、Bが 6 人となるのは 7C1=7 通り(7 人の中から 1 人を選ぶ選び方の数)ですから、その確率は 7/128 です。以降、同様に考えて、Aが m 人、Bが (7-m) 人となる確率は 7Cm /128 となることが分かります。

また、いずれかの状態に移った後でのゲーム終了までのターン数の期待値はどうなるでしょうか。それは F の定義にしたがい、それぞれ F(7)、F(1)、F(2)、F(3)、F(3)、F(2)、F(1)、F(7) と表されます。

以上を踏まえると、7 人から始めたときのターン数の期待値 F(7) は、ちょっと長いですが、次のように表されます。

これを F(7) について整理しましょう。この問題のややこしいところは、F(7) が左辺だけでなく右辺にも現れる点です。F(7) の項を左辺に集めて係数で割り算すると、次のようになります。

これで F(7) を求める式が導出できました。

同じ要領で、一般の n に対する F(n) の漸化式を導出できます。

ただし n が偶数の場合は注意が必要です。n=8 の場合を例にします。

4 対 4 で引き分けの場合は、プレイヤー数は 8 人のままです。この部分を考慮した立式が必要です。途中の計算過程は省略しますが、F(8) を求める式は次のようになります。

以上を一般化すると次の通りです。

上記の漸化式をコードにしましょう。コーディング自体は、落ち着いてやれば特に苦労はないと思います。

コード例は以下です(python)。

import math
def binomial(a, b): # 二項係数 a_C_b
r = 1
for i in range(b):
r *= a – i
r /= i + 1
return r

n = int(input())
f = [0] * (n+1)
for t in range(3, n+1):
a = math.pow(2, t) # 分子
for m in range(1, t):
a += binomial(t, m) * f[min(m, t-m)]
b = math.pow(2, t) – 2 # 分母
if t % 2 == 0:
a -= binomial(t, t/2) * f[t/2]
b -= binomial(t, t/2)
f[t] = a / b

print int(1000000 * f[n])

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「マイナー・ゲーム」 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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

TOP