2019年 東京大学文科系 第3問 をPythonで解こう

問題

問題は読売新聞 から引用．

　正八角形の頂点を反時計回りに $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{E}, \mathrm{F}, \mathrm{G}, \mathrm{H}$ とする．また，投げたとき表裏の出る確率がそれぞれ $\frac{1}{2}$ のコインがある．
　点 $\mathrm{P}$ が最初に点 $\mathrm{A}$ にある．次の操作を $10$ 回繰り返す．

　操作：コインを投げ，表が出れば点 $\mathrm{P}$ を反時計回りに隣接する頂点に移動させ，裏が出れば点 $\mathrm{P}$ を時計回りに隣接する頂点に移動させる．

例えば，点 $\mathrm{P}$ が点 $\mathrm{H}$ にある状態で，投げたコインの表が出れば点 $\mathrm{A}$ に移動させ，裏が出れば点 $\mathrm{G}$ に移動させる．
　以下の事象を考える．

　事象 $S:$ 操作を $10$ 回行った後に点 $\mathrm{P}$ が点 $\mathrm{A}$ にある．
　事象 $T:$ $1$ 回目から $10$ 回目の操作によって，点 $\mathrm{P}$ は少なくとも1回，点 $\mathrm{F}$ に移動する．

(1) 事象 $S$ が起こる確率を求めよ．
(2) 事象 $S$ と事象 $T$ がともに起こる確率を求めよ．

コード

from itertools import product
from fractions import Fraction

def get_coords(moves):
    '''
    (1, 2, 3, 4) に対して (1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4) を返す
    ただし mod 8 で
    '''
    coords = [moves[0]]
    for move in moves[1:]:
        coords.append((coords[-1] + move) % 8)
    return coords

movecases = product(*[(1, -1)]*10)
coordcases = [get_coords(movecase) for movecase in movecases]
print('(1)', Fraction(len([1 for case in coordcases if case[-1] == 0]), 2**10))
print('(2)', Fraction(len([1 for case in coordcases if 5 in case and case[-1] == 0]), 2**10))

以下が出力結果です．

(1) 17/64
(2) 33/512

コメント

$8$点に対して，$\mathrm{A}$ から順に座標 $0, 1, 2, \ldots, 7$ を設定すると，反時計回りは $+1$，時計回りは $-1$ で表現できます．そして，すべての場合についての点 $\mathrm{P}$ の座標の変化を記録していくだけです．座標 $8$ は一周して点 $\mathrm{A}$ を表すので，$\mod 8$ で座標を考えればうまくいきます．座標 $-1$ は $7$ と同じです．