str 学数学 题解

Official Solution

出题人提供的非常有技巧性的解法。

$$\sum _{i=1}^n\sum _{j=1}^n\lfloor \frac{ij}{n+1}\rfloor =\frac{n^2(n-1)}{4}$$

考虑为 $\lfloor \frac{ij}{n+1}\rfloor$ 配对，

$$\begin{array}{rl}\sum _{i=1}^n\sum _{j=1}^n\lfloor \frac{ij}{n+1}\rfloor +\lfloor \frac{i(n-j+1)}{n+1}\rfloor & =\frac{n^2(n-1)}{2}\\ \sum _{i=1}^n\sum _{j=1}^n\lfloor \frac{ij}{n+1}\rfloor +\lfloor i-\frac{ij}{n+1}\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{array}$$

即要求 $n+1\nmid ij$ 对任意 $1\le i,j\le n$ 成立。因此根据质数定义，$n+1$ 就是且只能是质数了。

Alternative Solution

考场上推了一半的想法。

$$\sum _{i=1}^n\sum _{j=1}^n\lfloor \frac{ij}{n+1}\rfloor =\frac{n^2(n-1)}{4}$$

注意到 $amodb=a-b\lfloor \frac{a}{b}\rfloor$，考虑构造取模

$$\begin{array}{r}\sum _{i=1}^n\sum _{j=1}^n(n+1)\lfloor \frac{ij}{n+1}\rfloor =\frac{n^2(n-1)(n+1)}{4}\\ \sum _{i=1}^n\sum _{j=1}^{n}ij-ijmod(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}ijmod(n+1)=\frac{n^2(n-1)(n+1)}{4}\\ \sum _{i=1}^n\sum _{j=1}^{n}ijmod(n+1)=\frac{n^2(n+1)}{2}\end{array}$$

考虑固定 $i$，研究 $j$ 变化下左式的情况。方便起见，我们将上式左侧 $j$ 的取值范围扩展至 $0$ 到 $n$： $$\sum _{i=1}^n\sum _{j=0}^{n}ijmod(n+1)=\frac{n^2(n+1)}{2}$$ 细心的读者或许已经发现，当 $gcd(i,n+1)=1$ 恒成立，即 $n+1$ 为质数时，$ijmod(n+1)$ 将取遍 $0$ 到 $n$，此时左右两式相等。下面我们证明这是上式相等的充分必要条件。

仍从 $ijmod(n+1)$ 的取值下手，我们研究如下以 $j$ 和 $t$ 为变量的不定方程的解 $$ij+(n+1)t=m(0\le m<n+1)$$ 由裴蜀定理（Bézout’s identity），方程有解的充分必要条件为 $gcd(i,n+1)\mid m$。不妨记 $d=gcd(i,n+1)$，$m=kd$，方程变为 $$ij+(n+1)t=kd(0\le k<\frac{n+1}{d})$$ 写出该不定方程的通解 $$\{\begin{array}{rl}j& =j_0+s\cdot \frac{n+1}{d}\\ t& =t_0-s\cdot \frac{i}{d}\end{array}(s\in \mathbb{Z})$$ 不难发现，对 $0\le k<\frac{n}{d}$，上述不定方程在 $0\le j\le n$ 的范围内总有 $d$ 个解，这意味着 $ijmod(n+1)$ 将有 $d$ 次取到 $kd$。故我们有 $$\begin{array}{rl}\sum _{i=1}^n\sum _{j=1}^{n}ijmod(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(\frac{n+1}{d}-1)\frac{n+1}{d}\\ & =\frac{n+1}{2}\sum _{i=1}^n(n+1-d)=\frac{n^2(n+1)}{2}\end{array}$$ 化简即得 $$\begin{array}{rl}\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{array}$$ 显然上式等价于对任意 $1\le i\le n$，$gcd(i,n+1)=1$ 恒成立。因此我们证明了 $n+1$ 是质数是原方程成立的充分必要条件。