str 学数学 题解
考场上当然是打表找规律了,但非常愚钝地没看出来……
结论是,\(n\) 是一个幸运数字,当且仅当 \(n+1\) 是一个质数。下面提供两种证明方法。
Official Solution
出题人提供的非常有技巧性的解法。
\[ \sum_{i=1}^n \sum_{j=1}^n \left \lfloor \frac {ij} {n+1} \right \rfloor = \frac {n^2 (n-1)}{4} \]
考虑为 \(\lfloor \frac {ij} {n+1} \rfloor\) 配对,
\[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^n \left \lfloor \frac {ij} {n+1} \right \rfloor + \left \lfloor \frac {i(n-j+1)} {n+1} \right \rfloor &= \frac {n^2 (n-1)}{2} \\ \sum_{i=1}^n \sum_{j=1}^n \left \lfloor \frac {ij} {n+1} \right \rfloor + \left \lfloor i - \frac {ij} {n+1} \right \rfloor &= \frac {n^2 (n-1)}{2} \\ \sum_{i=1}^n \sum_{j=1}^n i - [ n+1 \nmid ij ] &= \frac {n^2 (n-1)}{2} \\ \frac{n^2 (n+1)}{2} - \sum_{i=1}^n \sum_{j=1}^n [ n+1 \nmid ij ] &= \frac {n^2 (n-1)}{2} \\ \sum_{i=1}^n \sum_{j=1}^n [ n+1 \nmid ij ] &= n^2 \end{aligned} \]
即要求 \(n+1 \nmid ij\) 对任意 \(1 \leq i,j \leq n\) 成立。因此根据质数定义,\(n+1\) 就是且只能是质数了。
Alternative Solution
考场上推了一半的想法。
\[ \sum_{i=1}^n \sum_{j=1}^n \left \lfloor \frac {ij} {n+1} \right \rfloor = \frac {n^2 (n-1)}{4} \]
注意到 \(a \bmod b = a - b \lfloor \frac a b \rfloor\),考虑构造取模
\[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^n (n+1) \left \lfloor \frac {ij} {n+1} \right \rfloor = \frac {n^2 (n-1)(n+1)}{4} \\ \sum_{i=1}^n \sum_{j=1}^n ij - ij \bmod (n+1) = \frac {n^2 (n-1)(n+1)}{4} \\ \left( \frac {n(n+1)}{2} \right)^2 - \sum_{i=1}^n \sum_{j=1}^n ij \bmod (n+1) = \frac {n^2 (n-1)(n+1)}{4} \\ \sum_{i=1}^n \sum_{j=1}^n ij \bmod (n+1) = \frac {n^2 (n+1)} {2} \end{aligned} \]
考虑固定 \(i\),研究 \(j\) 变化下左式的情况。方便起见,我们将上式左侧 \(j\) 的取值范围扩展至 \(0\) 到 \(n\): \[ \sum_{i=1}^n \sum_{j=0}^n ij \bmod (n+1) = \frac {n^2 (n+1)} {2} \] 细心的读者或许已经发现,当 \(\gcd(i,n+1) = 1\) 恒成立,即 \(n+1\) 为质数时,\(ij \bmod (n+1)\) 将取遍 \(0\) 到 \(n\),此时左右两式相等。下面我们证明这是上式相等的充分必要条件。
仍从 \(ij \bmod (n+1)\) 的取值下手,我们研究如下以 \(j\) 和 \(t\) 为变量的不定方程的解 \[ ij + (n+1) t = m \pod{0 \leq m < n+1} \] 由裴蜀定理(Bézout’s identity),方程有解的充分必要条件为 \(\gcd(i,n+1) \mid m\)。不妨记 \(d = \gcd(i,n+1)\),\(m = k d\),方程变为 \[ ij + (n+1) t = kd \pod{0 \leq k < \frac {n+1} d} \] 写出该不定方程的通解 \[ \left \{ \begin{aligned} j &= j_0 + s \cdot \frac{n+1}{d}\\ t &= t_0 - s \cdot \frac{i}{d} \end{aligned} \right . \pod{s \in \mathbb Z} \] 不难发现,对 \(0 \le k < \frac n d\),上述不定方程在 \(0 \leq j \leq n\) 的范围内总有 \(d\) 个解,这意味着 \(ij \bmod (n+1)\) 将有 \(d\) 次取到 \(kd\)。故我们有 \[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^n ij \bmod (n+1) &= \sum_{i=1}^n d \sum_{k=0}^{\frac {n+1}{d} -1} kd \\ &= \sum_{i=1}^n d^2 \sum_{k=0}^{\frac {n+1}{d} -1} k \\ &= \frac 1 2 \sum_{i=1}^n d^2 \left( \frac {n+1} d - 1 \right) \frac {n+1} d \\ &= \frac {n+1} 2 \sum_{i=1}^n (n+1-d) = \frac{n^2 (n+1)}{2} \end{aligned} \] 化简即得 \[ \begin{aligned} \sum_{i=1}^n (n+1-d) &= n^2 \\ \sum_{i=1}^n d &= n \\ \sum_{i=1}^n \gcd(i, n+1) &= n \end{aligned} \] 显然上式等价于对任意 \(1 \leq i \leq n\),\(\gcd(i, n+1) = 1\) 恒成立。因此我们证明了 \(n+1\) 是质数是原方程成立的充分必要条件。