2021年北京大学金秋营数学测试 · 参考解答

答案速览

题号	结论
1	四点共圆；需排除 $AB=AC$ 时交点不唯一的退化情况
2	$2p^m<q^n$
3	好置换数是 $p$ 的倍数
4	$1\le t\le\lfloor2n/3\rfloor$
5	所给不等式成立
6	平方和至多 $26408407/95<300000$
7	两条件等价
8	实际可证 $r(G)\le nk/[2(\delta-1)^{k-1}]+k$

逐题解析

第 1 题

题目

已知锐角三角形 $ABC$ 内接于圆 $\Omega$，且 $AB\ne AC$。设 $A$ 在 $BC$ 上的投影为点 $D$，$A$ 关于 $\Omega$ 的对径点为 $E$，$\angle BAC$ 的平分线与 $BC$ 交于 $F$、与 $\Omega$ 交于 $J\ne A$。直线 $EF$ 与 $AD$ 交于 $K$，$A$ 关于 $J$ 的对称点为 $L$。证明：$B,C,K,L$ 四点共圆。

解答

题面校注：若 $AB=AC$，直线 $EF$ 与高 $AD$ 重合，$K$ 不唯一。故补明非等腰条件。

取 $A=(0,0)$，角平分线为横轴。设 $AB=c,AC=b$，$\angle A=2\theta$，记 $u=\cos\theta,v=\sin\theta$。于是

$$B=(cu,cv),\quad C=(bu,-bv).$$

再记 $s=b+c,d=c-b,h=bc,\Delta=s^2-2hu^2$。外接圆及若干点的坐标由两点代入、角平分线定理得到

$$\begin{aligned} \Omega:\quad W(x,y)&=x^2+y^2-\frac{s}{2u}x-\frac d{2v}y=0,\\ E&=\left(\frac{s}{2u},\frac d{2v}\right),\quad F=\left(\frac{2hu}{s},0\right),\quad J=\left(\frac{s}{2u},0\right),\quad L=\left(\frac{s}{u},0\right). \end{aligned}$$

高 $AD$ 的方程为 $du x+sv y=0$。联立直线 $EF$（其中 $d\ne0$），得到

$$K=\left(\frac{hus}{\Delta},-\frac{hdu^2}{v\Delta}\right).$$

下面显式写出所需圆，避免用图形猜测共圆。直线 $BC$ 的方程为 $T(x,y)=svx-duy-2hvu=0$。因此过 $B,C,L$ 的圆为

$$\Gamma:\quad W(x,y)-\frac{s^2}{2vu\Delta}T(x,y)=0.$$

确实，$T(B)=T(C)=0$，而 $W(L)=s^2/(2u^2)$、$T(L)=v\Delta/u$，均符合该式。

为核验 $K$，记 $N=s^2(1-2u^2)+4hu^4$。利用 $v^2=1-u^2,d^2=s^2-4h$，上式各部分为

$$T(K)=-\frac{huN}{v\Delta},\qquad W(K)=-\frac{hs^2N}{2v^2\Delta^2}.$$

二者恰好相消，故 $K\in\Gamma$，结论成立。这里 $u,v,\Delta$ 都为正，除以 $d$ 的步骤正是非等腰条件的用途。

第 2 题

题目

设 $p,q$ 为奇素数，$m,n$ 为正整数。已知

$$p^m\mid\prod_{i=1}^{n}(q^i-1).$$

证明：$2p^m<q^n$。

解答

若 $p=q$，每个 $q^i-1$ 都不被 $p$ 整除，与条件矛盾。故 $p\nmid q$。设 $d$ 是 $q$ 模 $p$ 的乘法阶，$h=\lfloor n/d\rfloor\ge1$，$s=v_p(q^d-1)$。只有 $d\mid i$ 的因子贡献 $p$，由奇素数的提升指数公式

$$v_p\left(\prod_{i=1}^n(q^i-1)\right)=hs+v_p(h!).$$

所用公式 $v_p(A^j-1)=v_p(A-1)+v_p(j)$（$p\mid A-1$）可由二项式展开逐次处理乘以 $p$ 和与 $p$ 互质的指数得到。

因为 $q^d-1$ 是偶数，$p^s\le(q^d-1)/2$。又由阶乘赋值公式，$v_p(h!)\le(h-1)/(p-1)$，且 $p\le2^{p-1}$，故 $p^{v_p(h!)}\le2^{h-1}$。综上

$$2p^m\le2p^{hs+v_p(h!)} \le(q^d-1)^h<q^{dh}\le q^n.$$

该证明实际上对任意大于 $1$ 的奇数 $q$ 也成立。

第 3 题

题目

设 $p$ 是一个素数，正整数 $n\ge p$。若一个 $n$ 阶置换的 $p$ 次复合为单位置换，则称其为“好的”。证明：“好的”置换的个数是 $p$ 的倍数。

解答

令 $S_n$ 为全体置换组成的群，考虑

$$X=\{(g_1,\ldots,g_p)\in S_n^p:g_1g_2\cdots g_p=e\}.$$

前 $p-1$ 个置换任取，最后一个唯一确定，所以 $|X|=(n!)^{p-1}$，被 $p$ 整除。

把每个元组循环左移。若原乘积为 $e$，移位后乘积为 $g_1^{-1}eg_1=e$，所以移位仍在 $X$ 内。因 $p$ 为素数，每个循环轨道大小只能为 $1$ 或 $p$。大小为 $1$ 的轨道恰为常值元组 $(g,\ldots,g)$，其条件是 $g^p=e$。于是好置换的个数模 $p$ 等于 $|X|$，即为 $0$。

第 4 题

题目

给定正整数 $n$。求所有非负整数 $t\le n$，使得存在 $n$ 个实数 $a_0,a_1,\ldots,a_{n-1}$，其中有 $t$ 个为正数、$n-t$ 个为负数，且多项式

$$f(x)=x^n+\sum_{i=0}^{n-1}a_ix^i$$

有 $t$ 个互异正实数根和 $n-t$ 个互异负实数根。

解答

答案为 $1\le t\le\lfloor2n/3\rfloor$，当上界为 $0$ 时无解。

必要性：从首项到常数项读系数符号，共有 $t+1$ 个正号、$n-t$ 个负号，且首号为正。记其变号数为 $V$。相邻次数差为 $1$，所以 $f(-x)$ 的变号数为 $n-V$。笛卡尔符号法则分别给出 $t\le V$、$n-t\le n-V$，故 $V=t$。若 $t=0$，所有符号都为正，与存在 $n$ 个负系数矛盾。若 $t\ge1$，正号开头且变号 $t$ 次的符号串至少有 $\lceil t/2\rceil$ 个负号块，故 $n-t\ge\lceil t/2\rceil$，等价于 $3t\le2n$。

充分性：满足此条件时，可写出首号为正、含 $t+1$ 个正号及 $n-t$ 个负号、恰变号 $t$ 次的符号串：先写 $t+1$ 个交替的非空符号块，再将多余正负号放进对应符号块。记符号为 $\sigma_n=1,\sigma_{n-1},\ldots,\sigma_0$。

构造互异实根 $r_j=\varepsilon_j R^{n+1-j}$，其中 $\varepsilon_j=-\sigma_{n-j}/\sigma_{n-j+1}$，$1\le j\le n$，$R>1$ 充分大。在 $\prod_j(x-r_j)$ 的 $x^{n-j}$ 系数中，绝对值最大的乘积唯一为 $(-1)^jr_1\cdots r_j$，它的符号正是 $\sigma_{n-j}$。其余项与它的比值都趋于 $0$，故充分大的同一个 $R$ 保证全部系数非零且具有指定符号。$\varepsilon_j=1$ 恰对应符号串变号，故恰有 $t$ 个正根，其余为负根，且根的绝对值两两不同。

第 5 题

题目

已知实数 $x,y,z\ge0$，记

$$a=x^2(y-z)^4,\qquad b=y^2(z-x)^4,\qquad c=z^2(x-y)^4.$$

证明：

$$(a+b+c)^3\ge\frac92\bigl(a\sqrt b+b\sqrt c+c\sqrt a\bigr)^2.$$

解答

记 $X=\sqrt a=x(y-z)^2,Y=\sqrt b=y(z-x)^2,Z=\sqrt c=z(x-y)^2$，$Q=X^2+Y^2+Z^2$。先证 $(X+Y+Z)^2\le2Q$。

为证明这个对称结论，可设 $x\ge y\ge z$，写 $x-y=u,y-z=v$。若 $u+v>0$，则 $y=(vx+uz)/(u+v)$；平方根的凹性给出

$$v\sqrt x+u\sqrt z\le(u+v)\sqrt y,$$

即 $\sqrt X+\sqrt Z\le\sqrt Y$。所以 $Y-X-Z\ge2\sqrt{XZ}$，平方后为 $Q\ge2(XY+YZ+ZX)$，所需结论即得。若 $u=v=0$，三个量全为零，同样成立。

再证明对任意非负 $X,Y,Z$ 都有

$$3(X^2Y+Y^2Z+Z^2X)\le(X+Y+Z)Q.$$

循环调整变量，使 $Z$ 最小，写 $X=Z+u,Y=Z+v$，$u,v\ge0$。右边减左边等于

$$2Z(u^2+v^2-uv)+u(u-v)^2+v^3\ge0.$$

两式合并，得 $(X^2Y+Y^2Z+Z^2X)^2\le2Q^3/9$，正是原不等式。

第 6 题

题目

教室里有 $95$ 个人，其中有 $2021$ 对互相认识的两人；除此之外，没有人认识另外的人。证明：所有人在该教室内认识人数的平方和不超过 $300000$。

解答

建立简单图的邻接矩阵 $(a_{ij})$，令 $d_i=\sum_j a_{ij}$，$n=95,m=2021$，所以 $\sum_i d_i=2m$、$\sum_{i,j}a_{ij}^2=2m$。考察非负平方和

$$0\le\sum_{i,j}\left(a_{ij}-\frac{d_i}{n}-\frac{d_j}{n}+\frac{2m}{n^2}\right)^2 =2m-\frac2n\sum_i d_i^2+\frac{4m^2}{n^2}.$$

展开时使用 $a_{ij}=a_{ji}$ 及行列和均为 $d_i$。于是

$$\sum_i d_i^2\le nm+\frac{2m^2}{n} =\frac{26408407}{95}<300000.$$

第 7 题

题目

设 $p,q$ 是两个不同的奇素数。证明：$p$ 为模 $q$ 的原根，当且仅当多项式

$$\frac{x^q-1}{x-1}$$

在模 $p$ 的意义下不可约。

解答

在 $\mathbb F_p$ 的代数闭包中取本原 $q$ 次单位根 $\zeta$。因为 $p\ne q$，$x^q-1$ 的导数 $qx^{q-1}$ 与它互质，故所有根互异；所给多项式的根恰是 $\zeta,\ldots,\zeta^{q-1}$。

Frobenius 映射 $z\mapsto z^p$ 将 $\zeta$ 依次送到 $\zeta^p,\zeta^{p^2},\ldots$。这个轨道第一次返回的步数恰为 $d=\operatorname{ord}_q(p)$。轨道根的乘积多项式

$$M(x)=\prod_{j=0}^{d-1}(x-\zeta^{p^j})$$

的系数被 Frobenius 固定，所以属于 $\mathbb F_p$。任意以 $\zeta$ 为根的 $\mathbb F_p$ 多项式都必须含全部这些互异根，故次数至少为 $d$；因此 $M$ 是最小多项式且不可约。对其他非平凡 $q$ 次单位根也一样，每个不可约因子的次数都是 $d$。

所以所给次数 $q-1$ 的多项式不可约，当且仅当 $d=q-1$，这恰好是 $p$ 为模 $q$ 原根的定义。

第 8 题

题目

设 $G$ 是一个有 $n$ 个顶点的连通简单图，$G$ 的围长为 $2k$，最小度数为 $\delta\ge2$。围长是指图 $G$ 的最小圈长。令

$$r(G)=\min_{u\in V(G)}\left\{\max_{v\in V(G)}\operatorname{dist}(u,v)\right\}.$$

证明：

$$r(G)\le \frac{nk}{2(\delta-1)^{k-1}}+4k.$$

解答

题面校注：来源图的分子为 $nk$，不是 $nk^k$；此处采用图半径的标准定义。把每条边看作长为 $1$ 的线段，暂允许在线段中点量距离，记 $s=(\delta-1)^{k-1}$。

任取一条边的中点 $c$。距 $c$ 不超过 $k-1/2$ 的顶点至少有

$$2\bigl(1+(\delta-1)+\cdots+(\delta-1)^{k-1}\bigr)\ge2s$$

个：从边的两端各向外逐层扩展，排除来路后每个点至少有 $\delta-1$ 个后继；若在这些层出现重复顶点，便产生长度不超过 $2k-1$ 的圈，违反围长条件。

现贪心选取边中点 $c_1,\ldots,c_t$。从任意一个开始，只要存在距已选集合至少 $2k$ 的边中点，就选取一个距该集合恰为 $2k$ 的中点。这样的点一定存在，因为相邻边中点距离为 $1$，沿一条最短路从近处走向远处必经过距离 $2k$。每个新点向距离为 $2k$ 的某个旧点连一条抽象树边，并赋长 $2k$。

各已选中点间距至少 $2k$，因而上述半径 $k-1/2$ 的顶点集两两不交，得 $2st\le n$。停止时，每条边中点距某个 $c_i$ 至多 $2k-1$；因此每个顶点距某个 $c_i$ 至多 $2k-1/2$。

所得抽象树的总边长为 $2k(t-1)$，直径不超过总边长。取其一条最长路径的中点 $z$，它到所有树顶点的距离至多半个直径，即不超过 $k(t-1)$：否则从更远顶点到最长路径的分支可延长原直径。这是树中心性质的直接证明。

将每条树边映到原图中相应两中点之间的最短路径，树上的 $z$ 也映到原图某条边上的点；图距离不大于对应树上距离。再取距该点至多 $1/2$ 的原图顶点 $z_0$，则对任意原图顶点 $v$，

$$\operatorname{dist}(z_0,v)\le\frac12+k(t-1)+2k-\frac12 =kt+k\le\frac{nk}{2(\delta-1)^{k-1}}+k.$$

此式强于所求上界，证明完成。