東大理系数学1971第6問

人で ’ジャンケン’ をして勝者をきめることにする。 たとえば， 人が ’紙’ を出し，他の 人が ’石’ を出せば，ただ 回でちょうど 人の勝者がきまることになる。 人で ’ジャンケン’ をして，負けた人は次の回に参加しないことにして，ちょうど 人の勝者がきまるまで，’ジャンケン’ をくり返すことにする。 このとき， 回目に，はじめてちょうど 人の勝者がきまる確率 を求めよ。

求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では，その値を互いに素な つの整数 を用いて と表したとき， かつ を満たす整数 がただ一つ存在することが証明できます。この を求めてください。

入力はすべて整数である。

k

計算結果を一行に出力せよ。

1

332748118

回でちょうど 人の勝者がきまるのは，

• 人が ’石’ を出し，残りの 人が ’ハサミ’ を出す
• 人が ’ハサミ’ を出し，残りの 人が ’紙’ を出す
• 人が ’紙’ を出し，残りの 人が ’石’ を出す

ときです。このようになる確率は です。

114514

200889667