つりあわない男女：「プログラマ脳を鍛える数学パズル」Q09の答え

問題

男性20人、女性10人がランダムに到着して行列を作る。ある位置で区切って行列を2つのグループに分ける時、どこで区切っても2つのグループのいずれかで男女の数が異なってしまうような到着順は何通りあるか。

この問題の元ネタをCode IQのサイトで探したけど見つからなかったので、書籍版のオリジナル問題なのだろうか。

わたしの考え方

• まずは男性20名、女性10名の並び替えの組み合わせを全て吐きだす。
• 最初の2名のところで区切るところから初めて、28名で区切るところまで全ての場合を検証して、男女の数が等しくならない組み合わせを数え上げて行く。

わたしのオリジナル解答

import itertools

p = list('MMMMMMMMMMMMMMMMMMMMFFFFFFFFFF')
r=30
cnt = 0

for q in set(itertools.permutations(p,r)):
    for n in range (2, 28):
        former = q[:n]
        latter = q[n:]
        if former.count('M') != former.count('F') or latter.count('M') != latter.count('F'):
            cnt += 1
print cnt

このプログラム、理論的には正しいはずなのだが検証すべき場合の数が多すぎて走らせるといつまでたっても終わらない・・・

模範解答のミソ

• 模範解答では、男女の順列の問題を2次元の表を使って考えている。
• 男性が来たら右へ、女性が来たら上へ移動する経路を考える。
• 男女が同数になる場所をカウントしないように、経路が何通りあるかを算出する。

修正されたわたしの解答

def path(b, g):
    if b == g:
        return 0
    elif b - g == 9:
        return path(b-1, g)
    elif b == 0 or g == 0:
        return 1
    else:
        return path(b-1, g) + path(b, g-1)

print path(19,10)

気づき・反省点

• 馬鹿正直に答えを出そうとすると、検証しきれなくなる事が分かった。
• 問題を抽象的に置き換えて考えることが重要で、これは数学的センスが問われている。
• 修正解答では再帰定義を使うことでうまく解くことが出来た。

参考にしたサイト

同じ物を含む順列 - メモ
リストオブジェクトの使い方 - Python Tips
お気楽 Python プログラミング入門（再帰定義についての解説）

---

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問