设盒中有n个碟子，其中蓝色有$k$个，若取出2个蓝色的概率是1/2，则有
$$\frac{k}{n}\cdot\frac{k-1}{n-1}=\frac{1}{2},$$
即
$$2k(k-1)=n(n-1),$$
从而得Pell方程
$$(2n-1)^2-2(2k-1)^2=-1,$$
解的初值是
$$a_1=2*21-1=41, \quad b_1=2*15-1=29,$$
利用公式
$$(x^2-dy^2)(u^2-dv^2)=(xu+dyv)^2-d(xv+yu)^2,$$
取$u=3$，$v=2$就可得递推式
$$a_i=3a_{i-1}+4b_{i-1}, \quad b_i=2a_i+3b_i,$$
直到$(a_i+1)/2$超过$10^{12}$且a、b均为奇数为止，此时$(b_i+1)/2$即所求之结果。
在$i=15$，$n=1070379110497$得答案，蓝色碟子的数量为$756872327473$。
a,b,i=41,29,1
while a+1 <= 2*(10**12) or a%2==0 or b%2==0:
a,b=3*a+4*b,2*a+3*b
i+=1
print i,(a+1)/2,(b+1)/2
|
