100. 排列的概率(Arranged probability)

如果一个盒子包含21个彩色的盘子,包括15个蓝色盘子和6个红色盘子,如果不放回的分两次随机取出两个盘子,可以发现连续两次取出蓝色盘子的概率是:

$$ P(BB)=(15/21)\times(14/20)=1/2 $$
下一个类似的安排是盒子中包含85个蓝色盘子和35个红色盘子,此时连续两次取出蓝色盘子的概率刚好也是50%。

请你找出当盘子的总数超过\(10^{12}\)个,第一次出现两次取出蓝色盘子概率为50%的情况时蓝色盘子的个数。

分析:这道题初看像一道概率论的题目,实际上仍是一道数论相关的题目,而且和我们六十六题已经涉及的佩尔方程有关。假设满足题目要求的总的盘子数量为\(T\),蓝色盘子数是为\(B\),则有:

$$ \frac{B}{T}\cdot \frac{B-1}{T-1}=\frac{1}{2}\Rightarrow 2\left( B^2-B \right) =T^2-T\Rightarrow \left( T^2-T \right) -2\left( B^2-B \right) =0 $$

现在我们的问题转化成求上式右侧的二元二次方程在\(T>10^{12}\)\(B\)的最小正整数解,正是我们在六十六题中研究过的丢番图方程问题。二元二次丢番图方程不存在一个一般性的解法,而是会根据方程形式不同采用不同的方法。对于这里的方程,我们可以通过适当变换把它转化成佩尔方程来求解。对上式进行配方,则有:

$$ \left( T^2-T+\frac{1}{4} \right) -2\left( B^2-B+\frac{1}{4} \right) =-\frac{1}{4} $$

两边乘以四,得到:

$$ \left( 4T^2-4T+1 \right) -2\left( 4B^2-4B+1 \right) =-1\Rightarrow \left( 2T-1 \right) ^2-2\left( 2B-1 \right) ^2=-1 $$

如果我们令\(x=2T-1,y=2B-1\),则上式右侧变为:

$$ x^2-2y^2=-1 $$

显然这个方程和佩尔方程非常相似,唯一的区别是等号右侧是\(-1\)而不是\(1\),有时也称为负佩尔方程(negative Pell equation),但在求解的原理上佩尔方程基本大同小异。我们知道对于佩尔方程,如果我们找到了它的最小正整数解,假设为\((x_1,y_1)\),则该方程其它的解满足以下递推关系:

$$ \left( x_n+y_n\sqrt{d} \right) =\left( x_{n-1}+y_{n-1}\sqrt{d} \right) \left( x_1+y_1\sqrt{d} \right) $$

对于负佩尔方程也存在类似的递推关系,假设方程\(x^2-dy^2=-1\)的最小正整数解为\((x_1,y_1)\),则各个解之间满足以下递推关系:

$$ \left( x_n+y_n\sqrt{d} \right) =\left( x_{n-1}+y_{n-1}\sqrt{d} \right) \left( x_1+y_1\sqrt{d} \right) ^2 $$

对于我们这里想要求解的负佩尔方程,已知其最小正整数解为\((1,1)\),则有:

$$ \begin{align*} x_n+y_n\sqrt{2}&=\left( x_{n-1}+y_{n-1}\sqrt{2} \right) \left( x_1+y_1\sqrt{2} \right) ^2\\ &=\left( x_{n-1}+y_{n-1}\sqrt{2} \right) \left( 3+2\sqrt{2} \right)\\ &=\left( 3x_{n-1}+4y_{n-1} \right) +\left( 2x_{n-1}+3y_{n-1} \right) \sqrt{2}\\ \end{align*} $$

因此我们可以得到递推关系:

$$ x_n=3x_{n-1}+4y_{n-1},y_n=2x_{n-1}+3y_{n-1} $$

我们再把原来关心的变量\(B,T\)代入,有:

$$ \begin{align*} 2T_n-1&=3(2T_{n-1}-1)+4(2B_{n-1}-1)\\ 2B_n-1&=2(2T_{n-1}-1)+3(2B_{n-1}-1) \end{align*} $$

化简得到:

$$ \begin{align*} T_n&=3T_{n-1}+4B_{n-1}-3\\ B_n&=2T_{n-1}+3B_{n-1}-2 \end{align*} $$

根据题意我们知道\(T_1=21,B_1=15\),则根据以上递推关系,我们计算出之后符合条件的解,我们把\(T_1,B_1\)代入递推方程,可以得到\(T_2=120,B_2=85\)正是题目给出的第二个例子。根据这个递推关系编程,可以很容易求出题目的解,不再赘述,代码如下:

# time cost = 5.73 µs ± 59.8 ns

def main(N=10**12):
    b,t = 15,21
    while t < N:
        b,t = 2*t+3*b-2,3*t+4*b-3
    return b