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

答案速览

题号	结论
1	$\binom{n-1}{\lfloor(n-1)/2\rfloor}$
2	所述交点在外接圆上
3	实际上只可能 $m=0$，此时 $3\mid n$
4	$15$；下界使用完整有限状态递推证书
5	教学改编的待辨析命题不成立，见精确反例
6	可构造不超过 $pm$ 的好数倍数，再反复加倍
7	两边是两个整系数多项式的同次系数，差被 $p^p$ 整除
8	所有正整数 $n$

逐题解析

第 1 题

题目

对于非负实数 $a_1,a_2,\ldots,a_n$，考虑如下 $2^n$ 个实数

$$i_1a_1+i_2a_2+\cdots+i_na_n, \qquad i_k=\pm1\ (1\le k\le n).$$

记 $S$ 为这 $2^n$ 个数中所有正数之和。在 $\sum_{i=1}^n a_i=1$ 的条件下，求 $S$ 的最小值。

解答

每个带符号和与其相反数成对，因此

$$S(a_1,\ldots,a_n)=\frac12\sum_{\varepsilon\in\{\pm1\}^n}\left|\sum_i\varepsilon_i a_i\right|.$$

这是关于 $a_i$ 的凸函数，且交换任何变量都不改变它。将 $(a_1,\ldots,a_n)$ 的全部 $n!$ 个排列向量平均，得到 $(1/n,\ldots,1/n)$。凸性于是给出 $S(1/n,\ldots,1/n)\le S(a_1,\ldots,a_n)$，并且此向量符合条件。

令 $r=\lfloor(n-1)/2\rfloor$。等分时，负号数为 $k$ 的正项值为 $(n-2k)/n$，所以

$$S_{\min}=\sum_{k=0}^r\frac{n-2k}{n}\binom nk =\sum_{k=0}^r\left(\binom{n-1}k-\binom{n-1}{k-1}\right) =\binom{n-1}r.$$

其中下指标为 $-1$ 的组合数取零。

第 2 题

题目

在 $\triangle ABC$ 中，$D$ 为 $BC$ 的中点，$E,F$ 分别为不含 $A$ 的弧 $BC$、含 $A$ 的弧 $BC$ 的中点。记 $\triangle ABC$ 的外接圆为 $\omega$。$\triangle ADE$ 的外接圆与射线 $AB,AC$ 除 $A$ 外分别交于 $J,K$，$\triangle ADF$ 的外接圆与射线 $AB,AC$ 除 $A$ 外分别交于 $L,M$。假设上述圆及交点均存在且不退化。证明：若 $AD,JK,LM$ 共点，则 $JM,LK$ 的交点在 $\omega$ 上。

解答

以 $A$ 为原点，以沿射线 $AB,AC$ 的单位向量为斜坐标基底，记夹角余弦为 $c$、$AB=p,AC=q$。点 $(x,y)$ 的距离平方为 $x^2+y^2+2cxy$。构型不退化保证 $p\ne q$：否则含 $A$ 的弧中点就是 $A$，圆 $ADF$ 无法定义。

写 $J=(j,0),K=(0,k),L=(l,0),M=(0,m)$。任何过 $A$ 的圆都有方程 $x^2+y^2+2cxy-ux-vy=0$。由它们经过 $D=(p/2,q/2)$，得到

$$pj+qk=pl+qm=\frac{p^2+q^2+2pqc}{2}.$$

$AE,AF$ 分别为内、外角平分线，故 $E$ 的坐标满足 $x=y$，$F$ 满足 $x=-y$。将两点分别代入外接圆 $\omega:x^2+y^2+2cxy-px-qy=0$ 及另两圆，得 $j+k=p+q,l-m=p-q$。

记 $P=p+q,D_0=p-q,H=pq$，解这些一次方程可得

$$\begin{aligned} j&=P/2-H(1-c)/D_0,&k&=P/2+H(1-c)/D_0,\\ l&=D_0/2+H(1+c)/P,&m&=-D_0/2+H(1+c)/P. \end{aligned}$$

直线 $JK,LM$ 与方向为 $(p,q)$ 的 $AD$ 共点，等价于 $p/j+q/k=p/l+q/m$。结合 $p(j-l)+q(k-m)=0$，得 $jl=km$。此处两圆不同，否则同一圆还经过互为对径的 $E,F$，与已知公共点 $A$ 强迫该圆为 $\omega$，但 $D$ 是 $BC$ 内部点，矛盾。

代入上式，$jl-km=0$ 即

$$(PD_0)^2=4H^2(1-c^2),\qquad jl=km=Hc=:r.$$

令 $U=p^2+q^2-2pqc>0$。联立 $JM:x/j+y/m=1$ 与 $LK:x/l+y/k=1$，利用 $p(j-l)=q(m-k)$ 及 $jl=km=r$，得到交点

$$X=\frac{r}{pl-qk}(p,-q).$$

而

$$pl-qk=\frac{PD_0}{2}+\frac{H\{c(p^2+q^2)-2H\}}{PD_0} =\frac{rU}{PD_0}.$$

所以 $X=(tp,-tq)$，其中 $t=(p^2-q^2)/U$。代入 $\omega$，左边为 $t^2U-t(p^2-q^2)=0$，故 $X\in\omega$。题设各交点在射线上且不等于 $A$，保证 $r>0$，上述分母均有意义。

第 3 题

题目

数列 $\{a_n\}$ 满足 $a_0=2$，$a_1=5$，$a_{n+1}=5a_n-a_{n-1}$（$n\ge1$）。设 $m\ge0,n\ge1$ 为整数，已知

$$a_m\mid a_{2n-2}+a_{2n-1},$$

证明：$3\mid m$ 且 $3\mid n$。

解答

题面校注：按回忆来源给出的递推及两个连续下标，整除条件对正整数 $m$ 实际不可能成立。若允许 $m=0$，则恰有 $3\mid n$；不能虚构满足整除条件的正整数例子。

先证 $a_m$ 与任意 $a_j+a_{j+1}$ 没有公共奇素因子。设奇素数 $\ell$ 同时整除二者，在有限域的代数闭包中取 $t^2-5t+1=0$ 的根。其常数项为 $1$，故 $t\ne0$，且递推给出 $a_i=t^i+t^{-i}$（模 $\ell$）。于是

$$t^{2m}=-1,\qquad (t+1)(t^{2j+1}+1)=0.$$

若 $t=-1$，第一式左边为 $1$，与 $\ell$ 为奇素数矛盾。故 $t^{2j+1}=-1$。设 $t$ 的乘法阶为 $h$。由奇次幂等于 $-1$，$h$ 恰含一个因子 $2$；但一个偶次幂等于 $-1$ 要求 $4\mid h$，矛盾。具体说，$t^r=-1$ 等价于 $r\equiv h/2\pmod h$，其奇偶性不可能同时为奇和偶。

递推模 $4$ 的一周期为 $2,1,3,2,3,1$，随后再次出现初始对 $(2,1)$。所以 $a_m$ 或为奇数，或恰含一个因子 $2$。又 $a_m\ge5$ 对所有 $m\ge1$ 成立（递推使正数列严格增加），因此每个这样的 $a_m$ 都有奇素因子，无法整除所给和。只剩 $m=0$。

模 $2$ 的周期是 $0,1,1$，两个相邻项之和为偶数恰当第一个下标为 $1\pmod3$。故 $2\mid a_{2n-2}+a_{2n-1}$ 等价于 $2n-2\equiv1\pmod3$，即 $3\mid n$；同时 $3\mid0$。

第 4 题

题目

求 $k$ 的最小值，使得将 $7\times7$ 方格挖去 $k$ 个格后，剩余图形不存在 T 字形（T 字形指一个方格与其相邻的三个方格有公共边构成的图形）。

解答

挖去 $15$ 格可以做到。下图 # 表示挖去，. 表示保留；逐点数上下左右邻居，每个保留格至多有两个保留邻居，故不存在 T 字形。

...#...
.#.#.#.
.#..#..
..#..##
#..#...
.#..##.
..#....

下面给出完整有限递推下界证书，所用是精确枚举而非抽样或贪心。把一行七格记为集合 $v\subseteq\{1,\ldots,7\}$。设 $h_v(j)=\mathbf1_{j-1\in v}+\mathbf1_{j+1\in v}$，边界外的指示数取零。相邻三行 $u,v,w$ 合法的充要条件是

$$\mathbf1_{j\in u}+h_v(j)+\mathbf1_{j\in w}\le2\quad(j\in v).$$

这是每个保留格不能有三个保留邻居的精确翻译，没有遗漏任何 T 的朝向。

令 $F_r(u,v)$ 为前 $r$ 行中最大保留数，最后两行为 $u,v$，且前 $r-1$ 行已经检验合法。初始化 $F_1(\varnothing,v)=|v|$，其余不可能状态记为 $-\infty$。递推为

$$F_{r+1}(v,w)=|w|+\max_{u:\,(u,v,w)\text{ 合法}}F_r(u,v).$$

结束时加上全空的下一行，取 $M_r=\max_{(u,v,\varnothing)\text{ 合法}}F_r(u,v)$。每一行只有 $128$ 种状态，完整递推得到

$r$	1	2	3	4	5	6	7
$M_r$	7	11	16	20	24	29	34

递推归纳保证每个合法棋盘都在且只在某个最后两行状态中被考虑，故保留数不超过 $34$，至少挖去 $49-34=15$ 格。上面的构造达到该数。可用随附的 精确行状态复算程序 从零复算所有状态；程序还独立检查构造中每格的邻居数。此下界是有限计算证书，不冒称不依赖计算的简短手证。

第 5 题

题目

（教学改编·命题辨析）在 $\triangle ABC$ 内部取一点 $O$，直线 $AO,BO,CO$ 分别交对边于 $D,E,F$。

判断下列命题是否成立，并给出证明或精确反例：若凸四边形 $AEOF,BFOD,CDOE$ 都有内切圆，则 $O$ 在 $\triangle ABC$ 的内心和垂心所在直线上。

解答

题面校注：回忆稿三块四边形的顶点顺序错误，按实际边界修正为 $AEOF,BFOD,CDOE$。即使作此修正，所声称的共线结论仍不成立，所以本题明确改为命题辨析。

取

$$A=(0,3),\quad B=(0,0),\quad C=(4,0),\quad O=(20/23,21/23).$$

$O$ 的三个正重心坐标为 $7:11:5$，故严格在三角形内部。三条线的对边交点为

$$D=(5/4,0),\quad E=(5/3,7/4),\quad F=(0,7/6).$$

有关直线依次为

$$\begin{aligned} AB&:x=0,&BC&:y=0,&CA&:3x+4y-12=0,\\ AD&:12x+5y-15=0,&BE&:21x-20y=0,&CF&:7x+24y-28=0. \end{aligned}$$

三块四边形的内切圆如下。

四边形	圆心	半径	四条边到圆心的距离
$AEOF$	$(2/3,5/3)$	$2/3$	到 $AB,AC,BE,CF$ 均为 $2/3$
$BFOD$	$(1/2,1/2)$	$1/2$	到 $AB,BC,AD,CF$ 均为 $1/2$
$CDOE$	$(7/4,3/4)$	$3/4$	到 $BC,CA,AD,BE$ 均为 $3/4$

这些距离由点到直线公式分别除以 $1,5,13,29,25$ 得到。例如第一圆心到 $BE,CF$ 的距离为 $(58/3)/29=2/3$、$(50/3)/25=2/3$。

还须排除仅与延长线相切的情形。第一圆心满足 $x>0,3x+4y<12,21x-20y<0,7x+24y-28>0$；第二圆心满足 $x>0,y>0,12x+5y-15<0,7x+24y-28<0$；第三圆心满足 $y>0,3x+4y<12,12x+5y-15>0,21x-20y>0$。这些恰是三块凸四边形的内部半平面。等距的闭圆盘因此均包含在对应四个闭半平面的交中，其切点属于该交与边所在直线的交，即属于边线段本身，确为内切圆。

但该直角三角形的内心为 $I=(1,1)$，垂心为 $H=B=(0,0)$，直线 $IH$ 为 $y=x$。$O$ 的两坐标不相等，故不在 $IH$ 上，原结论被严格反驳。

第 6 题

题目

若正整数 $N$ 可以写成若干个互不相同的自身正因数之和，且其中含有 $1$，称 $N$ 为好数。证明：对任意整数 $m>1$，存在无穷多个是好数的 $m$ 的正倍数，且最小的此类倍数不大于 $pm$，其中 $p$ 是 $m$ 的最大奇素因数；若 $m$ 是 $2$ 的幂，则规定 $p=3$。

解答

先证明一个因数覆盖引理。若某正整数 $N$ 的不同因数可用子集和表示 $0$ 至 $\sigma(N)$ 的所有整数，且素数 $q\nmid N$ 满足 $q\le\sigma(N)+1$，则 $Nq^e$ 也具有此性质。因为它的因数分成 $D(N),qD(N),\ldots,q^eD(N)$；各层都能提供从 $0$ 到 $\sigma(N)$ 的系数，且相邻的区间没有空隙。具体地，从层数 $j-1$ 到 $j$，原覆盖区间长度至少为 $q^j-1$，平移间距为 $q^j$，故所有平移区间相接。$2^a$ 本身满足此性质，其因数是二进制位权。

若 $m$ 有奇素因子，设最大者为 $p$，选取 $t=2^a$ 使 $t\le p<2t$，于是 $t\le p$ 且 $p\le2t-1$。令 $N=tm/p$。$N$ 的 $2$ 幂部分至少为 $t$，所有奇素因子均不超过 $p\le2t-1$；用引理逐个加入不同奇素数的全部幂次，可知 $N$ 的因数子集和能表示每个 $0\le u\le\sigma(N)$，特别是 $N-1$。

取这样的表示 $N-1=\sum d_i$。则

$$tm=pN=p+\sum_i pd_i.$$

将第一个 $p$ 改写为其二进制展开：它是 $1,2,\ldots,t$ 中若干不同数之和，因 $p$ 为奇数，其中含有 $1$。这些二进制位权都是 $tm$ 的因数；各 $pd_i$ 也是互异因数，并都有奇素因子 $p$，故不会与二进制位权重复。得到 $tm$ 的好数表示，且 $tm\le pm$。

若 $m=2^a$，其中 $a\ge1$，则

$$3m=1+2+3(1+2+\cdots+2^{a-1})$$

已经是互不相同的因数之和，含有 $1$，且达到允许的上界 $pm=3m$。

最后，若 $M>1$ 是好数，它的表示中不可能含因数 $M$ 本身；在原表示中再加入 $M$，便得到 $2M$ 的好数表示。因此从已构造的好数倍数连续加倍，得到无穷多个所需倍数。

第 7 题

题目

设 $p$ 为奇素数，$1\le k\le p$ 为整数。证明

$$\sum_{r=0}^{p}\sum_{t=1}^{p}(-1)^{t-1}\binom tr\binom pt\binom{p(p-t)}{p(k-r)} \equiv\binom{p^2}{kp}\pmod{p^p}.$$

约定组合数在下指标为负或大于上指标时为 $0$。

解答

记 $A(x)=1+x^p,B(x)=(1+x)^p$。二项式定理给出

$$\sum_{t=1}^p(-1)^{t-1}\binom pt A(x)^tB(x)^{p-t} =B(x)^p-(B(x)-A(x))^p.$$

左侧 $x^{kp}$ 的系数恰为题设双重和：从 $A(x)^t$ 选 $r$ 个 $x^p$ 后，另一个因子应贡献 $x^{p(k-r)}$。

因为 $p$ 为素数，$B(x)-A(x)=\sum_{j=1}^{p-1}\binom pjx^j$ 的每个系数都被 $p$ 整除，所以它的 $p$ 次幂的每个系数都被 $p^p$ 整除。另一方面，$B(x)^p=(1+x)^{p^2}$ 的 $x^{kp}$ 系数为 $\binom{p^2}{kp}$。比较系数便得所求同余。

第 8 题

题目

求所有正整数 $n$，使得平面上存在 $n$ 个全等的凸多边形 $P_1,\ldots,P_n$，且对每个非空指标集 $I\subseteq\{1,\ldots,n\}$，区域

$$\left(\bigcap_{i\in I}P_i\right)\setminus\left(\bigcup_{j\notin I}P_j\right)$$

的闭包都是非退化凸多边形。

解答

答案是所有正整数。$n=1$ 时任取一个非退化凸多边形即可，下面对任意 $n\ge2$ 给出构造。

先构造一个长度为 $M=2^n$ 的循环二进制序列 $b_0,b_1,\ldots,b_{M-1}$，使每个长度为 $n$ 的二进制串恰好作为连续窗口出现一次（下标均模 $M$）。为此，以长度 $n-1$ 的二进制串为有向图的顶点，每个长度 $n$ 的串 $a_1\cdots a_n$ 给出一条从 $a_1\cdots a_{n-1}$ 到 $a_2\cdots a_n$ 的边。每个顶点入度、出度均为 $2$；从任意顶点逐位添加目标串，可以到达任意另一顶点，所以图强连通。沿未用边行走形成闭路，再把尚未使用的闭路拼入，得到经过每条边恰一次的 Euler 回路。相邻边的串重叠 $n-1$ 位，故依次读取它们的首位，就得到所需循环序列。例如 $n=3$ 可用循环串 $00010111$，八个窗口依次是

$$000,\ 001,\ 010,\ 101,\ 011,\ 111,\ 110,\ 100.$$

取边长为 $s$ 的正 $M$ 边形 $G$，顶点按顺序编号为 $V_0,\ldots,V_{M-1}$。在 $V_j$ 的两条邻边上各取距 $V_j$ 为 $s/4$ 的点，连接后截去该角，所得角帽的闭包记为三角形 $T_j$，保留一侧的闭半平面记为 $H_j$。由于 $G$ 为正多边形，该截线只与这两条邻边相交，其他顶点均在 $H_j$ 内。每个 $T_j$ 都包含在以 $V_j$ 为圆心、$s/4$ 为半径的闭圆盘中；不同顶点间距离至少为 $s$，故这些角帽两两不相交。

令

$$K=G\cap\bigcap_{j=0}^{M-1}H_j,\qquad C_j=G\setminus H_j.$$

$K$ 是把所有顶点都截角后留下的非退化凸多边形，$C_j$ 是第 $j$ 个角帽去掉底边，且 $\overline{C_j}=T_j$。任意选择一些角恢复，仍得到凸多边形，因为恢复后的区域正是 $G$ 与其余截角半平面的交。现在定义

$$P_i=G\cap\bigcap_{j:\,b_{j+i-1}=0}H_j =K\cup\bigcup_{j:\,b_{j+i-1}=1}C_j, \qquad 1\le i\le n.$$

这里空交不增加限制。令 $R$ 表示绕正多边形中心旋转 $2\pi/M$，则 $R(V_j)=V_{j+1}$，并且 $P_i=R^{-(i-1)}P_1$，所以这 $n$ 个多边形全等，且均包含 $K$，因而非退化。

对任意 $x\in C_j$，它属于哪些 $P_i$，恰由窗口

$$(b_j,b_{j+1},\ldots,b_{j+n-1})$$

决定：第 $i$ 位为 $1$ 当且仅当 $x\in P_i$。每个窗口仅出现一次，所以对每个非空真子集 $I\subsetneq\{1,\ldots,n\}$，题设区域恰为唯一一个 $C_j$，其闭包是非退化三角形 $T_j$。这里没有遗漏位于截角底边上的点：底边属于 $K$，因此属于全部 $P_i$，不会落入真子集对应的区域；$G$ 外的点不属于任何 $P_i$。

最后，设 $j_*$ 是唯一的全 $1$ 窗口位置。全体 $P_i$ 的公共区域为

$$\bigcap_{i=1}^nP_i=K\cup C_{j_*} =G\cap\bigcap_{j\ne j_*}H_j.$$

它是只恢复第 $j_*$ 个角所得的非退化凸多边形，本身已经闭合。因此全指标集对应的区域也符合要求。构造覆盖任意 $n\ge2$，连同 $n=1$，结论为 $\boxed{n\in\mathbb Z_{>0}}$。