codechef 2018July Challenge div1 - Reach Equilibrium

未分类

---

题意:
给定正整数$n,k$,$A$和$B$玩游戏,$A$随机把长度为$n$的线段分为$k$份(每份长度都是实数),如果$B$能构造出分别以这$k$个实数为长度的二维向量使得这$k$个二维向量向量和为零向量,则$B$胜.问$B$胜的概率.

解析:
由于长度可以为实数,那么显然这里的长度$n$是多余的.
考虑此题的几何条件,如果$k$个向量的向量和为零向量,那么必定可以将这个$k$个向量首尾相接构成一个闭环.换言之,这k条线段可以构成一个多边形(或退化成闭合线段).$k$条线段可以构成多边形(或退化成闭合线段)的充要条件是最长边小于等于其他边之和.
假设原线段有$2n$个单位,那么将原线段分成$k$份的方案数是$C_{2n-1}^{k-1}$,将原线段分成$k$份且其中一份长度大于原线段的一半的方案数是$kC_{n-1}^{k-1}$.(根据挡板法)
那么$B$负的概率是:

$$\begin{align*} P &= \frac{kC_{n-1}^{k-1}}{C_{2n-1}^{k-1}} \\ &= \frac{ k\frac{(n-1)!}{(k-1)!(n-k)!} }{ \frac{(2n-1)!}{(k-1)!(2n-k)!} } \\ &= k*\frac{ (n-1)!(2n-k)! }{ (2n-1)!(n-k)! } \\ &= k*\frac{ (n-1)!(2n-k)! }{ (n-k)!(2n-1)! } \\ &= k* \frac{(n-k+1)*(n-k+2)*...*(n-1)}{ (2n-k+1)*(2n-k+2)*...*(2n-1) } \end{align*}$$
当$x \to + \infty$,$\frac{x+n}{2x+n} \to \frac{1}{2}$.
所以 $$P_{n \to +\infty} = k*(\frac{1}{2})^{k-1} = \frac{k}{2^{k-1}}$$ .
所以$B$胜的概率是$1-\frac{k}{2^{k-1}}$.