已知含 $q=2p$ 个未知数的 $p$ 个方程组成的方程组：
$\begin{cases}
& {{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+\cdots +{{a}_{1q}}{{x}_{q}}=0 \\
& {{a}_{21}}{{x}_{1}}+{{a}_{22}}{{x}_{2}}+\cdots +{{a}_{2q}}{{x}_{q}}=0 \\
& \cdots\cdots \\
& {{a}_{p1}}{{x}_{1}}+{{a}_{p2}}{{x}_{2}}+\cdots +{{a}_{pq}}{{x}_{q}}=0 \\
\end{cases}$ ①
其中 ${a}_{ij}\in\{-1,0,1\},i=1,2,\cdots,p;j=1,2,\cdots,q$．
求证：方程组 ① 有一个具有下述性质的解 $({x}_{1},{x}_{2},\cdots,{x}_{q})$：
$(a)$ ${x}_{j}(j=1,2,\cdots,q)$ 都是整数；
$(b)$ 至少有一个 $x_j(1\leqslant j\leqslant q)$ 不等于零；
$(c)$ $\left| {{x}_{j}} \right|\leqslant q(j=1,2,\ldots ,q)$．（荷兰）
$\begin{cases}
& {{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+\cdots +{{a}_{1q}}{{x}_{q}}=0 \\
& {{a}_{21}}{{x}_{1}}+{{a}_{22}}{{x}_{2}}+\cdots +{{a}_{2q}}{{x}_{q}}=0 \\
& \cdots\cdots \\
& {{a}_{p1}}{{x}_{1}}+{{a}_{p2}}{{x}_{2}}+\cdots +{{a}_{pq}}{{x}_{q}}=0 \\
\end{cases}$ ①
其中 ${a}_{ij}\in\{-1,0,1\},i=1,2,\cdots,p;j=1,2,\cdots,q$．
求证：方程组 ① 有一个具有下述性质的解 $({x}_{1},{x}_{2},\cdots,{x}_{q})$：
$(a)$ ${x}_{j}(j=1,2,\cdots,q)$ 都是整数；
$(b)$ 至少有一个 $x_j(1\leqslant j\leqslant q)$ 不等于零；
$(c)$ $\left| {{x}_{j}} \right|\leqslant q(j=1,2,\ldots ,q)$．（荷兰）
【难度】
【出处】
1976年第18届IMO试题
【标注】
【答案】
略
【解析】
如将一整数组 $({x}_{1},{x}_{2},\cdots,{x}_{q})$ 代入 ① 的第一个方程，且满足 $\left| {{x}_{j}} \right|\leqslant p$，由条件可知有 $|a_{11}x_1+a_{12}x_2+\cdots+a_{1q}x_q|\leqslant pq$．
由此可知，$a_{11}x_1+a_{12}x_2+\cdots+a_{1q}x_q$ 至多只能取 $2pq+1$ 个可能的值．从而 ① 式至多只能取 $(2pq+1)^p$ 个可能的整数组 $(x
_1,x_2,\cdots,x_q)$．
今对每个 $x_j$，令其取遍一 $p$ 至 $p$ 之间的 $2p+1$ 的值，这样得到 $(2p+1)^q$ 个整数组 $(x_1,x_2,\cdots,x_q)$．
由于
$\begin{aligned}
(2p+1)^q&=(2p+1)^{2p}\\
&=(4p^2+4p+1)^p\\
&>(4p^2+1)^p\\
&=(2pq+1)^p
\end{aligned}$
由抽屉原则，必定存在两个数组 $(x_1^{\prime},x_2^{\prime},\cdots,x_q^{\prime})$ 和 $(x_1^{\prime\prime},x_2^{\prime\prime},\cdots,x_q^{\prime\prime})$，它们代入方程左边得到 $p$ 个对应相同的数值，让我们来看数组 $(x_1^{\prime\prime}-x_1^{\prime},x_2^{\prime\prime}-x_2^{\prime},\cdots,x_q^{\prime\prime}-x_q^{\prime})$，它显然满足方程组 ① 的条件 $(a),(b)$．又因为 $|x_j^{\prime}|\leqslant q,|x_j^{\prime\prime}|\leqslant q$，故 $|x_q^{\prime\prime}-x_q^{\prime}|\leqslant 2p=q$，于是条件 $(c)$ 也被满足．命题获证．
由此可知，$a_{11}x_1+a_{12}x_2+\cdots+a_{1q}x_q$ 至多只能取 $2pq+1$ 个可能的值．从而 ① 式至多只能取 $(2pq+1)^p$ 个可能的整数组 $(x
_1,x_2,\cdots,x_q)$．
今对每个 $x_j$，令其取遍一 $p$ 至 $p$ 之间的 $2p+1$ 的值，这样得到 $(2p+1)^q$ 个整数组 $(x_1,x_2,\cdots,x_q)$．
由于
$\begin{aligned}
(2p+1)^q&=(2p+1)^{2p}\\
&=(4p^2+4p+1)^p\\
&>(4p^2+1)^p\\
&=(2pq+1)^p
\end{aligned}$
由抽屉原则，必定存在两个数组 $(x_1^{\prime},x_2^{\prime},\cdots,x_q^{\prime})$ 和 $(x_1^{\prime\prime},x_2^{\prime\prime},\cdots,x_q^{\prime\prime})$，它们代入方程左边得到 $p$ 个对应相同的数值，让我们来看数组 $(x_1^{\prime\prime}-x_1^{\prime},x_2^{\prime\prime}-x_2^{\prime},\cdots,x_q^{\prime\prime}-x_q^{\prime})$，它显然满足方程组 ① 的条件 $(a),(b)$．又因为 $|x_j^{\prime}|\leqslant q,|x_j^{\prime\prime}|\leqslant q$，故 $|x_q^{\prime\prime}-x_q^{\prime}|\leqslant 2p=q$，于是条件 $(c)$ 也被满足．命题获证．
答案
解析
备注
