Xmas Contest 2020 B: Beterminant 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_b

問題概要

$1$ 円払うと $P$ % で $W$ 円もらえる賭けを $n$ 回やって最終的に所持金が増えている確率が $\frac{1}{2}$ を超えるような最大の $n$ を求めよ．存在しない場合や無限個存在する場合はそれを指摘せよ．

考察

$W \ge 2$ として，所持金が増えるのはあたりが $\left\lfloor \frac{n}{W} \right\rfloor + 1$ 回以上出たときです． $\left\lfloor \frac{n}{W} \right\rfloor$ が一定の範囲内では $n$ を増やしてもその確率は減少しないので，条件を満たす最大の $n$ を求めるにあたっては $n = W m - 1$ ( $m$ は正の整数) の形のみ考えればよいです．

所持金の増加の期待値を考えると， $PW \lt 100$ のときはたくさんやったら負けそうで， $PW \gt 100$ のときはたくさんやったら勝てそうです． $PW = 100$ のときは期待値は $0$ ですが， $n = W m - 1$ のとき切り捨てで得をしてそうなのでなんとなく勝てそうです．コンテスト中に正解するためにはこのくらいの考察でほぼ足りるのですが，以下ちゃんとした正当化を与えておきます．

道具

整数 $n, k$ と実数 $p$ ( $n \ge 0$ ， $0 \le k \le n+1$ ， $0 \le p \le 1$ ) に対し， $f(n, k, p) = \sum_{i=0}^{k-1} \binom{n}{i} p^i (1-p)^{n-i}$ と定めます (すなわち，確率 $p$ であたる賭けを $n$ 回やってあたりが $k$ 回未満の確率です)．

Uhlmann [1] により以下の式が示されています：

$f\left(n, k, \frac{k}{n+1}\right) + f\left(n, n+1-k, \frac{n+1-k}{n+1}\right) = 1$ ( $0 \le k \le n+1$ )
$0 = f\left(n, 0, \frac{0}{n+1}\right) \lt f\left(n, 1, \frac{1}{n+1}\right) \lt \cdots \lt f\left(n, n+1, \frac{n+1}{n+1}\right) = 1$
$f\left(n, k, \frac{k-1}{n-1}\right) + f\left(n, n+1-k, \frac{n-k}{n-1}\right) = 1$ ( $n \ge 2$ ， $1 \le k \le n$ )
$1 = f\left(n, 1, \frac{0}{n-1}\right) \gt f\left(n, 2, \frac{1}{n-1}\right) \gt \cdots \gt f\left(n, n, \frac{n-1}{n-1}\right) = 0$ ( $n \ge 2$ )

[1] の論文は記法がちょっと違うしドイツ語だしなので，ここでも証明をまとめておきます．

1. と 3. は $f(n, n+1-k, 1-p) = \sum_{i=0}^{n-k} \binom{n}{i} (1-p)^i p^{n-i} = \sum_{i=k+1}^n \binom{n}{i} p^i (1-p)^{n-i}$ なのでよいです．

ここで， $f$ の $p$ による微分を計算しておきます． $1 \le k \le n$ として， $f'(n, k, p) = -n \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k} \lt 0$ です ( $f$ が $p$ について単調減少なことは定義の意味から明らかですが)．さらに， $f''(n, k, p) = -n \binom{n-1}{k-1} p^{k-2} (1-p)^{n-1-k} ((k-1) - (n-1) p)$ で，これは $0 \lt p \lt \frac{k-1}{n-1}$ のとき負， $p = \frac{k-1}{n-1}$ のとき $0$ ， $\frac{k-1}{n-1} \lt p \lt 1$ のとき正です．これを $f'$ の評価に用います．

2. について， $f\left(n, 0, \frac{0}{n+1}\right) = 0 \lt f\left(n, 1, \frac{1}{n+1}\right)$ はよいです． $2 \le k \le \frac{n+1}{2}$ のとき， $\frac{k-1}{n+1} \lt \frac{k-1}{n-1} \le \frac{k}{n+1}$ なので，平均値の定理と合わせて，

$\begin{align} &f\left(n, k, \frac{k}{n+1}\right) - f\left(n, k-1, \frac{k-1}{n+1}\right) \\ &= \left(f\left(n, k, \frac{k}{n+1}\right) - f\left(n, k, \frac{k-1}{n+1}\right)\right) + \binom{n}{k-1} \left(\frac{k-1}{n+1}\right)^{k-1} \left(1 - \frac{k-1}{n+1}\right)^{n-k+1} \\ &\gt \frac{1}{n+1} f'\left(n, k, \frac{k-1}{n-1}\right) + \binom{n}{k-1} \left(\frac{k-1}{n+1}\right)^{k-1} \left(1 - \frac{k-1}{n+1}\right)^{n-k+1} \\ &= -\frac{n}{n+1} \binom{n-1}{k-1} \left(\frac{k-1}{n-1}\right)^{k-1} \left(1 - \frac{k-1}{n-1}\right)^{n-k} + \binom{n}{k-1} \left(\frac{k-1}{n+1}\right)^{k-1} \left(1 - \frac{k-1}{n+1}\right)^{n-k+1} \\ &= \binom{n}{k-1} \frac{(k-1)^{k-1} (n-k)^{n-k} (n-k+1)}{(n+1)^n} \left(-\left(1+\frac{2}{n-1}\right)^{n-1} + \left(1+\frac{1}{n-k}\right)^{n-k} \left(1+\frac{1}{n-k+1}\right)^{n-k+1}\right) \\ &\gt 0 \end{align}$

です (最後の不等号は $\left(1+\frac{1}{x}\right)^x$ の単調性から従います)．また，偶数 $n$ に対し， $\frac{n/2+1}{n+1} \lt \frac{n/2}{n-1}$ より，

$\begin{align} &f\left(n, n/2+1, \frac{n/2+1}{n+1}\right) - f\left(n, n/2, \frac{n/2}{n+1}\right) \\ &= \left(f\left(n, n/2+1, \frac{n/2+1}{n+1}\right) - f\left(n, n/2+1, \frac{n/2}{n+1}\right)\right) + \binom{n}{n/2} \left(\frac{n/2}{n+1}\right)^{n/2} \left(1 - \frac{n/2}{n+1}\right)^{n-n/2} \\ &\gt \frac{1}{n+1} f'\left(n, n/2+1, \frac{n/2+1}{n+1}\right) + \binom{n}{n/2} \left(\frac{n/2}{n+1}\right)^{n/2} \left(1 - \frac{n/2}{n+1}\right)^{n-n/2} \\ &= -\frac{n}{n+1} \binom{n-1}{n/2} \left(\frac{n/2+1}{n+1}\right)^{n/2} \left(1 - \frac{n/2+1}{n+1}\right)^{n/2-1} + \binom{n}{n/2} \left(\frac{n/2}{n+1}\right)^{n/2} \left(1 - \frac{n/2}{n+1}\right)^{n-n/2} \\ &= 0 \end{align}$

です．これで「中央とその手前」のすべての不等号が示され，残りは 1. より得られます．

4. について， $1 \le k \le n-1$ として，

$\begin{align} &f\left(n, k+1, \frac{k}{n-1}\right) - f\left(n, k, \frac{k-1}{n-1}\right) \\ &= \left(f\left(n, k, \frac{k}{n-1}\right) - f\left(n, k, \frac{k-1}{n-1}\right)\right) + \binom{n}{k} \left(\frac{k}{n-1}\right)^k \left(1 - \frac{k}{n-1}\right)^{n-k} \\ &\lt \frac{1}{n-1} f'\left(n, k, \frac{k}{n-1}\right) + \binom{n}{k} \left(\frac{k}{n-1}\right)^k \left(1 - \frac{k}{n-1}\right)^{n-k} \\ &= -\frac{n}{n-1} \binom{n-1}{k-1} \left(\frac{k}{n-1}\right)^{k-1} \left(1 - \frac{k}{n-1}\right)^{n-k} + \binom{n}{k} \left(\frac{k}{n-1}\right)^k \left(1 - \frac{k}{n-1}\right)^{n-k} \\ &= 0 \end{align}$

なのでよいです．

議論

$W \le 1$ のときは所持金が増えないので条件を満たす $n$ は存在しません．以下 $W \ge 2$ とします．また， $p = \frac{P}{100}$ とおきます．

$W \ge 2$ より $m \le \frac{(Wm-1) + 1}{2}$ です．

3. と 4. より，正の整数 $m$ に対し $f\left(Wm-1, m, \frac{m-1}{(Wm-1)-1}\right) \ge \frac{1}{2}$ です． $pW \lt 1$ のとき， $m \ge \frac{1-2p}{1-pW}$ のとき $p \le \frac{m-1}{(Wm-1)-1}$ なので， $f(Wm-W, m, p) \ge \cdots \ge f(Wm-2, m, p) \ge f(Wm-1, m, p) \ge \frac{1}{2}$ が得られます．よって，各 $m \lt \frac{1-2p}{1-pW}$ に対し $n = Wm-1$ を条件を満たす候補として調べればよいです．制約下での $\frac{1-2p}{1-pW}$ の最大値は， $(p, W) = \left(\frac{1}{100}, 99\right)$ のときの $98$ です (ちなみに，このように得られた評価は少し緩く，実際に条件を満たす $n$ の最大値はこのとき $3167 = 99 \cdot 32 - 1$ です)．

一方，1. と 2. より，正の整数 $m$ に対し $f\left(Wm-1, m, \frac{m}{(Wm-1)+1}\right) \le \frac{1}{2}$ です． $pW \ge 1$ のとき， $p \ge \frac{1}{W} = \frac{m}{(Wm-1)+1}$ なので $f(Wm-1, m, p) \le \frac{1}{2}$ が得られます．ここですべての等号が成り立つのは $p = \frac{1}{W}$ かつ $m = \frac{(Wm-1)+1}{2}$ のとき，すなわち $(p, W) = \left(\frac{1}{2}, 2\right)$ の場合であり，そうでない場合はこれで無限個の $n = Wm - 1$ が条件を満たすことがわかりました．

$(p, W) = \left(\frac{1}{2}, 2\right)$ の場合は， $f\left(n, \left\lfloor\frac{n}{2}\right\rfloor+1, \frac{1}{2}\right)$ は $n$ が偶数のとき $\frac{1}{2}$ より大きく $n$ が奇数のときちょうど $\frac{1}{2}$ であることが簡単にわかります．よって条件を満たす $n$ は存在しません．

実装

多倍長整数を使って $f\left(n, \left\lfloor\frac{n}{W}\right\rfloor, \frac{P}{100}\right)$ を計算する (最初に $(100-P)^n$ を計算し，二項係数などをひとつずつ求めていく) のが確実です．浮動小数点数で適切に計算 (階乗の $\log$ などをとる) してぎりぎりになるケースは実際には制約下にはありません．ちなみに，有理数 $p \ne \frac{1}{2}$ に対し $f(n, k, p) \ne \frac{1}{2}$ らしいです [2]．

$n$ 回中 $i$ 回あたる確率を DP で求めていってもよいです (誤差も小さいです)． $n = Wm - 1$ のみ考えるという考察すらスキップ可能です．あたりが少ないほうだけ調べる (つまり，所持金が増えない確率を計算する)，答えを埋め込むなどをしないと時間制限は厳しいかもしれません．

注意を要するのは条件を満たす $n$ が無限個存在するかの判定です．場合分けをする場合は $(P, W) = (50, 2)$ を忘れない必要があります．実験的に行う場合は，「適当に大きい $n$ で成り立たなかったら無限個存在はしない」としてしまうのは誤りで，ちゃんと $n = Wm - 1$ を見たり前後 $W$ 個程度を見たりすることになります．

統計情報

正解者：チーム人任せ (0:45:20) はじめ 31 チーム

厳密な証明をしなくてもそれっぽくやれば正解できる (ただし考察が雑なほど一部のケースではまる)
整数パーセントなことが本質的な制約 (そして出てくる答えの上限は案外 (?) 大きい)

という特徴の問題でした．1 つ目のために普通のコンテストには出しにくい問題ですが，クリスマスにはとっつきやすい枠としてよさそうという気持ちで出題しました．結果としては順位表を赤く染め上げてしまいました……．ここまでは予想外でしたが，一発 AC の方はとても丁寧だと思います．

ところで， $P W \lt 100$ のときに $n = W m - 1$ だけ考えると所持金が増える確率が単調減少ということも実験的に気づきました．このことを使った人もいるかもしれません．これについては証明が思い浮かなかったので，証明あるいは反証を募集しています． $P W \ge 100$ のときに様子が異なるので，上で示した Uhlmann の結果よりも大変そうと考えています．