2007年第48届IMO试题

• 知识点

  >

  二试组合部分

略

答案是 $3n$ 个平面．
很容易发现 $3n$ 个平面能满足要求，例如平面 $x=i,y=i$ 和 $z=i(i=1,2,\cdots,n)$，易见这 $3n$ 个平面它们的并集包含 $S$ 使不含原点．另外的例子是平面集 $x+y+z=k,(k=1,2,\cdots,3n).$
我们证明 $3n$ 是最少可能数．下面的引理是关键的．
引理：考虑 $k$ 个变量的非零多项式 $P(x_1,\cdots,x_k)$．若所有满足 $x_1,\cdots,x_k\in\{0,1,\cdots,n\}$ 且 $x_1+\cdots+x_k>0$，点 $(x_1,\cdots,x_k)$ 都是 $P(x_1,\cdots,x_k)$ 的零点，且 $P(0,0,\cdots,0)\ne 0$，则 $\mathrm{deg}P\geqslant kn$．
证明：我们对 $k$ 用归纳法：当 $k=0$ 时，由 $P\ne 0$ 知结论成立．现假设结论对 $k-1$ 成立，下证结论对 $k$ 成立．
令 $y=x_k$，设 $R(x_1,\cdots,x_{k-1},y)$ 是 $P$ 被 $Q(y)=y(y-1)\cdots(y-n)$ 除的余式．
因为多项式 $Q(y)$ 以 $y=0,1,\cdots,n$ 为 $n+1$ 个零点，所以 $P(x_1,\cdots,x_{k-1},y)=R(x_1,\cdots,x_{k-1},y)$，对所有 $x_1,\cdots,x_{k-1},y\in\{0,1,\cdots,n\}$ 成立，因此 $R$ 也满足引理的条件，进一步有 $\mathrm{deg}_yR\leqslant n$．又明显地 $\mathrm{deg}R\leqslant \mathrm{deg}P$，所以只要证明 $\mathrm{deg}R\geqslant nk$ 便可．
现在，将多项式 $R$ 写成 $y$ 的降幂形式：
$R(x_1,\cdots,x_{k-1},y)=R_n(x_1,\cdots,x_{k-1})y^n+R_{n-1}(x_1,\cdots,x_{k-1})y^{n-1}+\cdots+R_0(x_1,\cdots,x_{k-1})$
下面我们证明 $R_n(x_1,\cdots,x_{k-1})$ 满足归纳假设的条件．
事实上，考虑多项式 $T(y)=R(0,\cdots,0,y)$，易见 $\mathrm{deg}T(y)\leqslant n$，这个多项式有 $n$ 个根，$y=1,\cdots,n$；
另一方面，由 $T(0)\ne 0$ 知 $T(y)=0$．因此 $\mathrm{deg}T=n$，且它的首项系数是 $ R_n(0,\cdots,0)\ne 0$．
（特别地，在 $k=1$ 的情况下，我们得到系数 $R_n$ 是非零的）．
类似地，取任意 $a_1,\cdots,a_{k-1}\in\{0,1,\cdots,n\}$ 且 $a_1+\cdots+a_{k-1}>0$．
在多项式 $R(x_1,\cdots,x_{k-1},y)$ 中令 $x_i=a_i$，我们得到 $y$ 的多项式 $R(a_1,\cdots,a_{k-1},y)$ 以 $y=0,\cdots,n$ 为根且 $\mathrm{deg}\leqslant n$，因此它是一个零多项式．
所以 $R_i(a_1,\cdots,a_{k-1})=0,(i=0,1,\cdots,n)$，特别有 $R_n(a_1,\cdots,a_{k-1})=0$．
这样我们就证明了多项式 $R_n(x_1,\cdots,x_{k-1})$ 满足归纳假设的条件，所以 $\mathrm{deg}R_n\geqslant (k-1)n$．
故 $\mathrm{deg}R\geqslant \mathrm{deg}R_n+n\geqslant kn$．引理得证．
回到原题，假设 $N$ 个平面的并集包含 $S$ 但不包含原点，设它们的方程是：$a_ix+b_iy+c_iz+d_i=0$
考虑多项式 $\displaystyle P(x,y,z)=\prod\limits_{i=1}^N(a_ix+b_iy+c_iz+d_i)$，它的阶为 $N$．对任何 $(x_0,y_0,z_0)\in S$，这个多项式有性质 $P(x_0,y_0,z_0)=0$ 但 $P(0,0,0)\ne 0$．因此由引理我们得到 $N=\mathrm{deg}P\geqslant 3n$．