100 Arranged Probability

Problem 100

如果一个盒子里有 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;
    }
}

程序中,在计算 xy 的时候都 +1 了,因为前面的 double 类型运算可能会损失精度,强转成 long 的时候少了 1,所以最后又加了个 1。