2014年清华大学金秋营数学试题 · 参考解答

答案速览

题号	答案
1	不存在
2	$n^2$
3	$k_{\max}=5$
4	$1$
5	不变非空子集数为 $2^c-1$，其中 $c$ 为函数图的有向环数
6	$\frac{a^p+(p-1)a}{p}$；$\frac{a^{p^2}+(p-1)a^p+(p^2-p)a}{p^2}$

逐题解析

第 1 题

题目

给定整数 $n\ge4$。证明：不存在正 $n$ 边形 $A_1A_2\cdots A_n$，使得对任意 $1\le i<j\le n$，线段 $A_iA_j$ 的长度都是整数。

解答

假设所有距离为整数。对连续三个顶点使用余弦定理，可知 $2\cos(2\pi/n)$ 为有理数。令 $\zeta=e^{2\pi i/n}$，$u=\zeta+\zeta^{-1}=2\cos(2\pi/n)$。由递推 $P_0=2,P_1=X,P_{j+1}=XP_j-P_{j-1}$，$P_j$ 为首一整系数多项式，且 $P_n(u)=\zeta^n+\zeta^{-n}=2$。因此 $u$ 是整系数首一多项式的有理根，必为整数。

$n\ge4$ 时 $0\le u<2$，所以 $u=0$ 或 $1$，对应 $n=4$ 或 $6$。正方形的对角线等于边长的 $\sqrt2$ 倍，正六边形的隔一个顶点的弦等于边长的 $\sqrt3$ 倍；正整数边长不可能同时使这些长度为整数。矛盾。

第 2 题

题目

设 $n\ge2$ 为正整数。用 $r(i)$ 表示 $n$ 除以 $i$ 所得的余数，即

$$n=q_i i+r(i),\qquad 0\le r(i)<i.$$

又以 $\sigma(m)$ 表示正整数 $m$ 的所有正因数之和。计算

$$r(1)+r(2)+\cdots+r(n)+\sigma(1)+\sigma(2)+\cdots+\sigma(n).$$

解答

由 $r(i)=n-i\lfloor n/i\rfloor$，以及把每个因数 $d$ 对其倍数的贡献相加，

$$\sum_{m=1}^n\sigma(m)=\sum_{d=1}^n d\left\lfloor\frac nd\right\rfloor.$$

两式相加后取整项完全抵消，剩下 $n$ 个 $n$，所以答案为 $n^2$。

第 3 题

题目

设 $k$ 为正整数，并且对每个整数 $n\ge2$ 都有

$$\left\lfloor\frac n{\sqrt3}\right\rfloor+1> \frac{n^2}{\sqrt{3n^2-k}}.$$

求 $k$ 的最大值。

解答

令 $m=\lfloor n/\sqrt3\rfloor+1$，则 $3m^2>n^2$。平方数模 $3$ 只能为 $0,1$，故正整数 $3m^2-n^2$ 不可能为 $1$，至少为 $2$，于是 $m\ge\sqrt{(n^2+2)/3}$。

当 $n=5$ 时 $m=3$，原不等式要求 $3>25/\sqrt{75-k}$，即 $k<50/9$，所以整数 $k\le5$。

证明 $k=5$ 可行。对于 $n\ge4$，

$$\frac{n^2+2}{3}>\frac{n^4}{3n^2-5} \iff n^2>10.$$

因分母为正，开方得 $m>n^2/\sqrt{3n^2-5}$。$n=2,3$ 分别直接为 $2>4/\sqrt7$、$2>9/\sqrt{22}$，均成立。因此最大值为 $5$。

第 4 题

题目

设

$$f(x,y,z)=x^l y^m z^n+\sum_{s=1}^{t}A_sx^{p_s}y^{q_s}z^{r_s},$$

其中 $l,m,n$ 为正整数，$A_s$ 为实数，$p_s,q_s,r_s$ 为非负整数，并且对每个 $s$ 都有

$$\min\{p_s-l,\ q_s-m,\ r_s-n\}<0.$$

给定严格递增的实数列

$$a_0<a_1<\cdots<a_l,\quad b_0<b_1<\cdots<b_m,\quad c_0<c_1<\cdots<c_n,$$

定义

$$N(a_i,b_j,c_k)= \prod_{\substack{0\le i'\le l\\i'\ne i}}(a_i-a_{i'}) \prod_{\substack{0\le j'\le m\\j'\ne j}}(b_j-b_{j'}) \prod_{\substack{0\le k'\le n\\k'\ne k}}(c_k-c_{k'}).$$

求

$$\sum_{i=0}^{l}\sum_{j=0}^{m}\sum_{k=0}^{n} \frac{f(a_i,b_j,c_k)}{N(a_i,b_j,c_k)}.$$

解答

先证明一维恒等式：对互异的 $a_0,\ldots,a_l$，

$$\sum_{i=0}^l\frac{a_i^d}{\prod_{i'\ne i}(a_i-a_{i'})} =\begin{cases}0,&0\le d<l,\\1,&d=l.\end{cases}$$

这是对 $X^d$ 作拉格朗日插值后比较 $X^l$ 的系数得到的，插值成立因为两边次数不超过 $l$，且在 $l+1$ 个不同点相等。

题中三重和对每个单项式分解成三个这样的一维和。主项 $x^ly^mz^n$ 的贡献为 $1\cdot1\cdot1=1$；每个其余项至少有一个指数严格小于相应的 $l,m,n$，该因子的和为零。因此总和为 $1$，其他两个指数即使很大也不影响这一结论。

第 5 题

题目

设 $f$ 是集合 $\{1,2,\ldots,n\}$ 到自身的映射。对其非空子集 $A$，定义

$$f(A)=\{b\mid \text{存在 }a\in A,\ f(a)=b\}.$$

若 $f(A)=A$，则称 $A$ 为 $f$ 的不变子集。证明：$f$ 的不变子集共有奇数个。

解答

在有限有向图中画出每个顶点 $v$ 到 $f(v)$ 的箭头，每点出度为一，必至少有一个有向环，且不同有向环互不相交。设环数为 $c\ge1$。

若 $f(A)=A$，映射 $f|_A$ 是有限集到自身的满射，因而也是双射，所以 $A$ 中每点都有唯一前驱，并且反复迭代都位于某个有向环上。因此 $A$ 只能是若干完整有向环的并；反之这样的并必满足不变性。选取非空环子集共有 $2^c-1$ 种，是奇数。

第 6 题

题目

考虑所有从集合 $\{0,1,\ldots,n-1\}$ 到集合 $\{1,2,\ldots,a\}$ 的映射。若两个映射可由定义域的循环平移相互得到，则称它们等价。记等价类数为 $M(n,a)$。设 $p$ 为素数，求 $M(p,a)$ 与 $M(p^2,a)$。

解答

对循环群的每个平移，数它固定的映射，再除以群的大小即可得轨道数：这个平均公式来自双重计数“映射及固定它的群元素”，每条轨道对总计数恰贡献群的大小。

平移 $r$ 在 $n$ 个位置上有 $\gcd(n,r)$ 个循环，固定映射必须在各循环取常值，故固定数为 $a^{\gcd(n,r)}$。

$n=p$ 时，恒等平移固定 $a^p$ 个，其余 $p-1$ 个平移各固定 $a$ 个，得到第一式。$n=p^2$ 时，恒等平移固定 $a^{p^2}$ 个；非零的 $p$ 倍数平移有 $p-1$ 个，各固定 $a^p$ 个；其余 $p^2-p$ 个平移各固定 $a$ 个。相加除以 $p^2$ 即得第二式。