math - 使用模数会偏向高数吗？

Question

添加 0-32 范围内的 6 个随机唯一数字并对结果进行模数运算是否有利于高数？

例如:9 +10 +11 +18 +25 +28 +32 = 133 % 20 = 13

Answer 1

有趣的是，有一种强大的方法可以使用 Generating Functions 的概念在计算机上手动或非常快速地(而不是使用蛮力)解决这个问题。 .

(警告:较长的帖子)

您在 0 到 19 的范围内工作，但是通过从 0 到 32 随机生成数字来获得它。

如果得到数字 i 的机会是 p(i) [注意，p(0) = p(1) = p(2) = ... = p(12) 和 p(13) = ..= p( 19) 和 p(0) = 2p(13))。

现在我们对通过生成 6 次随机数并将它们相加来获得特定总和的机会感兴趣。

这可以通过计算多项式的六次方系数来建模

P(x) = p(0) + p(1) * x + p(2) * x^2 + ... + p(r) * x^r + ... + p(19) * x^ 19

因此，我们正在查看 (P(x))^6 的系数。

对于给定的问题，我们可以忽略 1/33 因子(为了比较哪个总和更有可能)并且有 p(0) = 2, p(1) = 2, ..., p(19) =1 .

因此，我们正在查看 P(x) = 2(1 + x + x^2 + ... + x^12) + x^13 + x^14 + .. + x^19。

我们现在只需要计算它的六次幂的系数，取指数模 20 并将它们相加。这里可以使用快速多项式乘法算法，如 FFT。

事实上，我们可能可以使用一些带有复数的代数和/或确信地证明关于概率分布的陈述来手动完成。