100 Arranged Probability
如果一个盒子里有 21 个有色的碟子,15 个蓝色的和 6 个红色的。从中随机取两个,可知取到两个蓝碟子的几率是 。
下一个满足此条件(即随机取两个碟子的情况下取到两个蓝色碟子的几率是 50%)的情况是 85个蓝碟子和 35 个红碟子。
对于包含超过 个碟子的情况中,存在满足上述条件的并包含最少碟子的情况,该情况下共需要多少个蓝碟子?
假设碟子总数是 ,蓝色盘子总数是 ,那么它们需要满足 。
可以转化为求方程
的整数解。
两边同时乘以 4 令 其中, 是奇数。
方程转化为 这是一个 Pell 方程,最小的正整数解是 根据 Pell 方程的通解 可以算出整数解,不难看出, 都是奇数。
用程序计算得到第一个超过 的 ,这样对应满足题意 ,通过对应的 计算得到我们要求的答案 。
公式里的 是 2。
double sqrt2 = Math.Sqrt(2);
for (int i = 1; ; i++)
{
long x = (long)((Math.Pow(1 + sqrt2, 2 * i - 1) + Math.Pow(1 - sqrt2, 2 * i - 1)) / 2) + 1;
long y = (long)((Math.Pow(1 + sqrt2, 2 * i - 1) - Math.Pow(1 - sqrt2, 2 * i - 1)) / 2 / sqrt2) + 1;
if (x > 2000000000000)
{
return (y + 1) / 2;
}
}
程序中,在计算 x
和 y
的时候都 +1
了,因为前面的 double
类型运算可能会损失精度,强转成 long
的时候少了 1,所以最后又加了个 1。