
%%TEXT_BEGIN%%
划块估计.
为了估计集合 $X$ 的具有某种性质的子集 $A$ 中含有元素的个数, 可将 $X$ 划分为若干块 $X_1, X_2, \cdots, X_t$. 然后讨论每个 $X_i$ 至多(或至少)含有 $A$ 的多少个元素, 由此得到 $|A|$ 的范围估计.
常有如下 3 种基本情形:
情形 1 若 $X$ 的子集 $A$ 满足: $A$ 中任何 $r$ 元组都具有性质 $p$, 求 $|A|$ 的最大值.
则可将 $X$ 划分为若干块 $X_1, X_2, \cdots, X_t$, 使 $X_i$ 中任何 $r$ 元组都不具有性质 $p$, 从陑每个 $X_i$ 至多含有 $A$ 的 $r-1$ 个元素.
情形 2 设 $X=X_1 \cup X_2 \cup \cdots \cup X_t$, 且每个 $X_i$ 至多含有 $A$ 的 $k_i$ 个元素, 从而 $|A| \leqslant k_1+k_2+\cdots+k_t$. 显然, $k_1+k_2+\cdots+k_t$ 越小, 估计越精确(等号越有可能达到). 因此, 在 $X$ 的划分中, 应使 $k_1+k_2+\cdots+k_t$ 尽可能小, 这就要使 $k_i$ 在 $A_i$ 中占的"比重": $\frac{k_i}{\left|A_i\right|}$ 较小.
这常常可通过列表试验, 找到估计较为精确的划分.
情形 3 有些数集具有这样的性质: 只要集合 $A=\left\{a_1, a_2, \cdots, a_n\right\}$ 具有性质 $p$, 则集合 $A+a=\left\{a_1+a, a_2+a, \cdots, a_n+a\right\}$ 也具有性质 $p$, 我们称集合 $A$ 的这种性质 $p$ 具有平移不变性.
此时, 可对 $X$ 进行均匀 (各块的元素个数相等)的划分,然后分块进行估计.
%%TEXT_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例1. 设 $M=\{1,2, \cdots, 2005\}, A$ 是 $M$ 的子集,若对任何 $a_i, a_j \in A$, $a_i \neq a_j$, 都能以 $a_i 、 a_j$ 为边长唯一地确定一个等腰三角形, 求 $|A|$ 的最大值.
%%<SOLUTION>%%
分析:题在前一节中用"间距估计"给出过解答, 现考虑用划块估计求解.
其基本想法是, 将 $M$ 划分为若干块, 使 $A$ 在每一块中至多含有 1 个元素.
注意到 $A$ 满足的条件是:对任何 $a_i<a_j \in A$, 都有 $2 a_i \leqslant a_j$. 因此,在对 $M$ 分块时,可使每一块中的任何两个元素 $x, y(x<y)$,都有 $2 x>y$.
解将 $M$ 划分为 11 个子集: $A_1=\{1\}, A_2=\{2,3\}, A_3=\left\{2^2, 2^2+\right. \left.1, \cdots, 2^3-1\right\}, \cdots, A_{11}=\left\{2^{10}, 2^{10}+1, \cdots, 2005\right\}$, 因为对每个集合 $A_i$ 中的任何元素 $x, y(x<y)$, 都有 $2 x>y$, 从而 $\left|A \cap A_i\right| \leqslant 1(i=1,2,3, \cdots, 11)$, 所以 $|A| \leqslant 11$. 又 $A=\left\{1,2,2^2, \cdots, 2^{10}\right\}$ 合乎条件, 故 $|A|$ 的最大值为 11 .
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例2. 设 $A$ 是正整数集合 $\mathbf{N}^*$ 的子集,对任何 $x, y \in A, x \neq y$, 有 $\mid x- y \mid \geqslant \frac{x y}{25}$. 求 $|A|$ 的最大值.
%%<SOLUTION>%%
分析:题在前一节中用"间距估计"给出过解答, 现考虑用划块估计求解.
其基本想法是: 将 $\mathbf{N}^*$ 划分为若干块, 使 $A$ 在每一块中至多含有 1 个元素.
注意到 $A$ 满足的条件是: 对任何 $a_i<a_j \in A$, 都有 $a_j-a_i \geqslant \frac{a_i a_i}{25}$. 因此,在对 $\mathbf{N}^*$ 分块时, 可使每一块中的任何两个元素 $x, y(x<y)$, 都有 $y-x<\frac{x y}{25}$.
解令 $X_1=\{1\}, X_2=\{2\}, X_3=\{3\}, X_4=\{4\}, X_5=\{5,6\}$, $X_6=\{7,8,9\}, X_7=\{10,11, \cdots, 16\}, X_8=\{17,18, \cdots, 53\}, X_9=\{54$, $55, \cdots\}=\mathbf{N}^* \backslash\{1,2, \cdots, 53\}$.
对于 $X_9$, 当 $x, y \in X_9$ 时, $x>25$, 所以 $y-x<y<y \cdot \frac{x}{25}=\frac{x y}{25}$. 而对于 $X_i(i=1,2, \cdots, 8)$, 当 $x, y \in X_i$ 时, 显然有 $y-x<\frac{x y}{25}$. 于是 $A$ 最多只能含有上述每个集合中的一个数, 所以 $n \leqslant 9$.
又 $A=\{1,2,3,4,5,7,10,17,54\}$ 合乎条件, 所以 $|A|$ 的最大值为 9 .
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例3. 设 $A \subseteq\{0,1,2, \cdots, 29\}$, 满足: 对任何整数 $k$ 及 $A$ 中任意数 $a$ 、 $b$ ( $a 、 b$ 可以相同), $a+b+30 k$ 均不是两个相邻整数之积.
试求出所有元素个数最多的 $A$.
%%<SOLUTION>%%
解:求的 $A=\{3 t+2 \mid 0 \leqslant t \leqslant 9, t \in \mathbf{Z}\}$.
设 $A$ 满足题中条件且 $|A|$ 最大.
因为对两个相邻整数 $a 、 a+1$, 有 $a(a-1) \equiv 0,2,6,12,20,26(\bmod 30)$. 于是对任一 $a \in A$, 取 $b=a, k=$ 0 , 可知 $2 a \neq 0,2,6,12,20,26(\bmod 30)$, 即 $a \neq 0,1,3,6,10,13,15$, $16,18,21,25,28(\bmod 30)$. 因此, $A \subseteq M=\{2,4,5,7,8,9,11,12,14$, $17,19,20,22,23,24,26,27 , 29\}$, 而 $M$ 可分拆成下列 10 个子集的并: $A_1=\{2,4\}, A_2=\{5,7\}, A_3=\{8,12\}, A_4=\{11,9\}, A_5=\{14,22\}$, $A_6=\{17,19\}, A_7=\{20\}, A_8=\{23,27\}, A_9=\{26,24\}, A_{10}=\{29\}$. 其中每一个子集 $A_i$ 至多包含 $A$ 中一个元素, 故 $|A| \leqslant 10$.
若 $|A|=10$, 则每个子集 $A_i$ 恰好包含 $A$ 中一个元素, 于是, $20 \in A$, $29 \in A$. 由 $20 \in A$ 知 $12 \notin A, 22 \notin A$, 从而 $8 \in A, 14 \in A$, 这样 $4 \notin A$, $24 \notin A$. 因此 $2 \in A, 26 \in A$. 由 $29 \in A$ 知 $7 \notin A, 27 \notin A$, 从而 $5 \in A$, $23 \in A$, 这样 $9 \notin A, 19 \notin A$, 因此 $11 \in A, 17 \in A$.
综上所述,所求的集合 $A=\{2,5,8,11,14,17,20,23,26,29\}$, 经验证, $A$ 满足要求.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例4. 设 $A$ 是 $X=\{1,2,3, \cdots, 1989\}$ 的子集, 对任何 $x, y \in A$,有 $|x-y| \neq 4$ 和 7. 求 $|A|$ 的最大值.
%%<SOLUTION>%%
分析: 设$A$ 是 $X=\{1,2,3, \cdots, 1989\}$ 的子集,若对任何 $x, y \in A$,有 $|x-y| \neq 4$ 和 7 , 则称 $A$ 是好子集.
显然,好子集具有平移不变性, 即 $A$ 是好子集,则对任何 $a, A+a$ 也是好子集.
所以可进行均匀划块估计.
设 $X=P_1 \cup P_2 \cup \cdots \cup P_k$, 注意题目的目标是 $|A| \leqslant r, r$ 越小, 估计越精确.
因此应使 "好" 元素 (属于 $A$ ) 在 $P_i$ 中所占的比例尽可能小.
设 $P= \{1,2, \cdots, t\}$, 列表观察:
\begin{tabular}{c|ccccccccccccc}
$t=|P|$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
$|A \cap P|$ & 1 & 2 & 3 & 4 & 4 & 4 & 4 & 4 & 5 & 5 & 5 & 6 & 7 \\
\hline
$\frac{|A \cap P|}{|P|}$ & 1 & 1 & 1 & 1 & $\frac{4}{5}$ & $\frac{2}{3}$ & $\frac{4}{7}$ & $\frac{1}{2}$ & $\frac{5}{9}$ & $\frac{1}{2}$ & $\frac{5}{11}$ & $\frac{1}{2}$ & $\frac{7}{13}$
\end{tabular}
其中以 $P=\{1,2, \cdots, 11\}$ 时得到的比值 $\frac{5}{11}$ 最小, 猜想以 $\{1,2, \cdots, 11\}$ 为一个子集的划分是最佳的.
解设 $A$ 是合乎题意的子集, 对 $P=\{1,2, \cdots, 11\}$, 我们证明 $\mid A \cap P \mid \leqslant 5$.
实际上, 将 $P$ 划分为 6 个子集 $\{1,5\} 、\{2,9\} 、\{3,7\} 、\{4,8\} 、\{6,10\}$ 、 $\{11\}$, 对所划分的每个子集, $A$ 最多含有它的一个元素, 所以 $|A \cap P| \leqslant 6$. 若 $|A \cap P|=6$, 则 $A$ 在每个划分的子集中都至少含有一个元素, 于是 $11 \in A, \Rightarrow 4 \notin A, \Rightarrow 8 \in A, \Rightarrow 1 \notin A, \Rightarrow 5 \in A, \Rightarrow 9 \notin A, \Rightarrow 2 \in A, \Rightarrow 6 \notin A, \Rightarrow 10 \in A, \Rightarrow 3 \notin A, \Rightarrow 7 \in A$, 但 $11-7=4$,矛盾.
所以 $|A \cap P| \leqslant 5$.
令 $P_k=\{11 k+1,11 k+2, \cdots, 11 k+11\}(k=0,1,2, \cdots, 179)$, $P_{180}=\{1981,1982, \cdots, 1989\}$. 则同样可知, $A$ 至多含有 $P_k(k=0,1$, $2, \cdots, 180)$ 中的 5 个元素, 所以 $|A| \leqslant 5 \times 181=905$.
最后, 令 $A_k=\{11 k+1,11 k+3,11 k+4,11 k+6,11 k+9\}(k=0,1$, $2, \cdots, 180), A=A_0 \cup A_1 \cup \cdots \cup A_{180}$, 则 $A$ 合乎题意, 此时 $|A|=905$, 故 $|A|$ 的最大值为 905 .
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例5. 设 $p$ 为给定的正整数, $A$ 是 $X=\left\{1,2,3,4, \cdots, 2^p\right\}$ 的子集, 且具有性质: 对任何 $x \in A$, 有 $2 x \notin A$. 求 $|A|$ 的最大值.
%%<SOLUTION>%%
分析:解将 $X$ 划块, 对 $p$ 归纳.
当 $p=1$ 时, $X=\{1,2\}$, 取 $A=\{1\}$,于是 $f(1)=1$;
当 $p=2$ 时, $X=\{1,2,3,4\}$, 将 $X$ 划分为 3 个子集 $\{1,2\} 、\{3\} 、\{4\}$, 则 $A$ 至多含每个子集中的一个数, 于是 $|A| \leqslant 3$. 取 $A=\{1,3,4\}$, 于是 $f(2)=3$;
当 $p=3$ 时, $X=\{1,2, \cdots, 8\}$. 将 $X$ 划分为 5 个子集:\{1,2\}、\{3,6\}、 $\{4,8\} 、\{5\} 、\{7\}$, 则 $A$ 至多含有每个子集中的一个数, 于是 $|A| \leqslant 5$. 取 $A=\{1,5,6,7,8\}$, 则 $f(3)=5$.
一般地, 当 $X_p=\left\{1,2,3, \cdots, 2^p\right\}$ 时, 可进行划块估计.
注意到 $2^{p-1}+1$, $2^{p-1}+2, \cdots, 2^p$ 都可属于 $A$, 于是想到划块: $X=\left\{1,2,3, \cdots, 2^{p-1}\right\} \cup\left\{2^{p-1}+\right. \left.1,2^{p-1}+2, \cdots, 2^p\right\}=X_{p-1} \cup M$, 其中 $X_{p-1}=\left\{1,2,3, \cdots, 2^{p-1}\right\}, M=\left\{2^{p-1}+\right. \left.1,2^{p-1}+2, \cdots, 2^p\right\}$. 这样, 问题在于 $X_{p-1}=\left\{1,2,3, \cdots, 2^{p-1}\right\}$ 中至多有多少个属于 $A$, 这是否为原问题在 $p-1$ 的情形? 问题没有这么简单! 试想: $M$ 中的数 $2^{p-1}+1,2^{p-1}+2, \cdots, 2^p$ 都属于 $A$ 时, $X_{p-1}$ 中有很多数不能属于 $A$, 比如: $2^{p-2}+1,2^{p-2}+2, \cdots, 2^{p-1}$ 都不属于 $A$; 但未必 $2^{p-1}+2,2^{p-1}+4, \cdots, 2^p$ 都属于 $A$. 因此, 还要作更细的划块: $M$ 中的部分数 $2^{p-1}+2,2^{p-1}+4, \cdots, 2^p$ 与 $X_{p-1}$ 中的有关数 ( 2 倍关系) 搭配构造集合: $\left\{2^{p-1}+2,2^{p-2}+1\right\},\left\{2^{p-1}+4\right.$, $\left.2^{p^{-2}}+2\right\}, \cdots,\left\{2^p, 2^{p-1}\right\}$, 由此得到 $X_p$ 的一个划分:
$$
X_{p-2}=\left\{1,2,3, \cdots, 2^{p-2}\right\}, M_t=\left\{2^{p-1}+2 t, 2^{p-2}+t\right\} \quad(t=1,2, \cdots,
$$
$\left.2^{p-2}\right), M_0=\left\{2^{p-1}+1,2^{p-1}+3,2^{p-1}+5, \cdots, 2^{p-1}+2^{p-1}-1\right\}$.
因为 $A$ 至多含 $M_t\left(t=1,2, \cdots, 2^{p-2}\right)$ 中一个元素, 至多含 $X_{p-2}$ 中 $f(p-2)$ 个元素, 至多含 $M_0$. 中 $2^{p-2}$ 个元素, 于是 $f(p) \leqslant f(p-2)+2^{p-2}+ 2^{p-2}=f(p-2)+2^{p-1}$.
下面考虑, 能否构造集合 $A$, 证明 $f(p) \geqslant f(p-2)+2^{p-1}$.
设 $X=\left\{1,2,3, \cdots, 2^{p-2}\right\}$ 的合乎题意的最大子集为 $A_1$, 令 $A_2= \left\{2^{p-1}+1,2^{p-1}+2, \cdots, 2^p\right\}$, 则对任何 $x \in A_1$, 有 $2 x \leqslant 2 \cdot 2^{p-2}=2^{p-1}< 2^{p-1}+1 \notin A_2$, 于是, $A=A_1 \cup A_2$ 是合乎题意的子集, 故 $f(p) \geqslant|A|= f(p-2)+2^{p-1}$.
综上所述, $f(p)=f(p-2)+2^{p-1}$.
下面用两种方案解此递归关系.
方案 1: 迭代 ( $p$ 个等式相加), 得 $f(p-1)+f(p)=f(1)+f(2)+ 2^2+2^3+\cdots+2^{p-1}=1+\left(2^0+2^1\right)+2^2+2^3+\cdots+2^{p-1}=2^p$.
再迭代 (第 $p-1$ 个等式减第 $p-2$ 个等式, 加第 $p-3$ 个等式等等), 得
$$
f(p)+(-1)^p f(1)=2^p-2^{p-1}+\cdots+(-1)^p \cdot 2^2,
$$
所以
$$
f(p)=2^p-2^{p-1}+\cdots+(-1)^p \cdot 2^2+(-1)^{p+1},
$$
注意到 $(-1)^{p+1} \cdot 2^1+(-1)^{p+2} \cdot 2^0=(-1)^{p+1}(2-1)=(-1)^{p+1}$,
所以 $f(p)=2^p-2^{p-1}+\cdots+(-1)^p \cdot 2^2+(-1)^{p+1} \cdot 2^1+(-1)^{p+2} \cdot 2^0$
$$
=\frac{2^p\left[1-\left(-\frac{1}{2}\right)^{p+1}\right]}{1+\frac{1}{2}}=\frac{2^{p+1}+(-1)^p}{3} .
$$
方案 2: 分类求解.
当 $p$. 为奇数时, $f(p)=f(p-2)+2^{p-1}=f(p-4)+2^{p-3}+2^{p-1}= f(1)+2^2+2^4+\cdots+2^{p-1}=2^0+2^2+2^4+\cdots+2^{p-1}=\frac{2^{p+1}-1}{3}$;
当 $p$ 为偶数时, $f(p)=f(p-2)+2^{p-1}=f(p-4)+2^{p-3}+2^{p-1}= f(2)+2^3+2^5+\cdots+2^{p-1}=1+2^1+2^3+2^5+\cdots+2^{p-1}=\frac{2^{p+1}+1}{3}$.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例6. 设 $X=\{1,2, \cdots, 2001\}$, 求最小的正整数 $m$, 使其适合要求: 对 $X$ 的任何一个 $m$ 元子集 $W$, 都存在 $u, v \in W$ ( $u 、 v$ 可以相同),使得 $u+v$ 是 2 的方幂.
%%<SOLUTION>%%
分析:解为叙述问题方便, 如果 $u+v$ 是 2 的方幂, 则称 $u 、 v$ 是一个对子.
我们从反面考虑, 如果 $X$ 的子集 $W$ 不含对子, 则 $W$ 最多有多少个元素? 显然, 我们如果能将 $X$ 划分成若干块, 使每一块中任何 2 个数是对子, 则 $W$ 只能含每一块中的一个元素.
于是, 令 $A_i=\{1024-i, 1024+i\}{ }^{\prime \prime}(i=1,2, \cdots$, $977), B_j=\{32-j, 32+j\}(j=1,2, \cdots, 14), C=\{15,17\}, D_k=\{8- k, 8+k\}(k=1,2, \cdots, 6), E=\{1,8,16,32,1024\}$ .假定 $W$ 不含有对子, 则 $W$ 不能含有 $E$ 中的元素, 且最多只能含有各 $A_i 、 B_j 、 D_k$ 与 $C$ 中的一个元素, 于是, $|W| \leqslant 977+14+6+1=998$. 这表明, 当 $|W| \geqslant 999$ 时, $W$ 中必有对子, 也就是说, $m=999$ 合乎条件.
其次, 若 $|W|=998$ 且 $W$ 不含有对子, 则 $W$ 恰含各 $A_i 、 B_j 、 D_k$ 与 $C$ 中的一个元素, 令 $W=\{1025,1026, \cdots$, $2001\} \cup\{33,34, \cdots, 46\} \cup\{17\} \cup\{9,10,11,12,13,14\}$, 容易验证 $W$ 中没有对子.
于是, 当 $m<999$ 时,取 $W$ 的一个 $m$ 元子集,则该子集中没有对子.
综上所述, $m$ 的最小值为 999 .
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例7. 设 $n$ 是一个固定的正偶数,考虑一个 $n \times n$ 的正方形棋盘,如果两个方格至少有一条公共边, 则称它们是相邻的.
现在, 将棋盘上 $N$ 个方格作上标记, 使得棋盘上任何一个方格(作上标记的和未作上标记的) 都与至少一个作上标记的方格相邻.
试确定 $N$ 的最小值.
%%<SOLUTION>%%
解: $n \times n$ 棋盘按如下方式染色: 如果 $n$ 不被 4 整除,则如图(<FilePath:./figures/fig-c7i1.png>)染色,
否则如图(<FilePath:./figures/fig-c7i2.png>) 染色.
考虑所有黑色方格, 若 $n=4 k$, 如图(<FilePath:./figures/fig-c7i2.png>) 染色后, 共有 $4 \times 3+4 \times 7+\cdots+4 \times(4 k-1)=2 k(4 k+2)$ 个黑色方格; 若 $n=4 k+2$, 染色后, 共有 $4 \times 1+4 \times 5+\cdots+4 \times(4 k+1)=2(k+1)(4 k+2)$ 个黑色方格.
不论哪种情形, 黑色方格都是 $\frac{1}{2} n(n+2)$ 个, 而其中任意三个都不能与同一个方格相邻.
而由条件, 它们中任意一个应与某个作了标记的方格相邻, 于是 $N \geqslant \frac{1}{4} n(n+2)$.
另一方面, 我们证明, 可适当标记 $N=\frac{1}{4} n(n+2)$ 个格, 使之合乎题目要求.
事实上, 如图(<FilePath:./figures/fig-c7i3.png>), 我们将棋盘的 "第一层边框" 的 4(n-1) 个方格从左上角开始, 按顺时针方向依次编号为 $1,2, \cdots, 4 n-4$, 将编号被 4 除余 $1 、 2$ 的方格作标记(图(<FilePath:./figures/fig-c7i3.png>) 中阴影部分).
去掉棋盘的外围两层边框, 对剩下的棋盘仍从左上角开始, 沿顺时针方向进行类似编号, 又将编号被 4 除余 $1 、 2$ 的方格作上标记, 如此下去, 直到此步骤不能再进行为止.
这样, 我们恰对一半的黑色方格作了标记, 故共有 $\frac{1}{4} n(n+2)$ 个方格作了标记.
下面证明这种标记方法符合要求.
事实上,如图(<FilePath:./figures/fig-c7i3.png>) 不难看出任意两个标记方格不会有一个公共的"邻格", 假设这些标记的方格为 $A_1, \cdots, A_N$, 其中 $N=\frac{1}{4} n(n+2)$, 与 $A_i$ 相邻的方格集合为 $M_i$, 则 $M_i(i=1,2, \cdots, N)$ 两两不交.
且对位于棋盘角上的格 $A_i,\left|M_i\right|=2$ (共有 2 个这样的格); 对位于棋盘边上的格 $A_i,\left|M_i\right|=3$ (共有 $2 n-4$ 个这样的格); 对位于非棋盘边界上的格 $A_i,\left|M_i\right|=4$ (共有 $\frac{n^2-6 n+8}{4}$ 个这样的格). 于是 $\left|M_1 \cup M_2 \cup \cdots \cup M_N\right|=\frac{n^2-6 n+8}{4} \times4+(2 n-4) \times 3+2 \times 2=n^2$, 故 $M_1 \cup M_2 \cup \cdots \cup M_N$ 包含了所有的方格, 即每个方格都与某一个标记方格相邻.
综上所述, $N_{\min }=\frac{1}{4} n(n+2)$.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例8. 在 $x O y$ 平面上有 2002 个点, 它们组成一个点集 $S$, 已知 $S$ 中任意两点的连线都不与坐标轴平行.
对 $S$ 中的任意两个点 $P 、 Q$, 考虑以 $P Q$ 为对角线, 其边平行于坐标轴的矩形 $M_{P Q}$, 用 $W_{P Q}$ 表示 $S$ 在矩形 $M_{P Q}$ 内 (不含 $P$ 、 $Q)$ 的点的个数.
当命题: " $S$ 中的点无论在坐标平面上如何分布, 在 $S$ 中至少有一对点 $P$ 、 $Q$, 满足 $W_{P Q} \geqslant N$ " 为真时, 求 $N$ 的最大值.
%%<SOLUTION>%%
解:$N_{\max }=400$. 先证明必有 $P 、 Q$ 使得 $W_{P Q} \geqslant 400$. 事实上, 设 $A$ 是 $S$ 中纵坐标最大的点, $B$ 是 $S$ 中纵坐标最小的点, $C$ 是 $S$ 中横坐标最大的点, $D$ 是 $S$ 中横坐标最小的点.
如果 $A 、 B 、 C 、 D$ 中有两点重合, 结论显然成立 (此时不妨设 $A=C$, 则 $M_{A B} 、 M_{B D} 、 M_{A D}$ 覆盖了 $S$, 从而 $\max \left\{W_{A B}, W_{B D}, W_{A D}\right\} \geqslant \left.\frac{2002-3}{3}>400\right)$. 如果 $A 、 B 、 C 、 D$ 两两不重合, 则它们的分布如图(<FilePath:./figures/fig-c7i4.png>) 所示.
对于情形(1)(4), $M_{A C} 、 M_{B C} 、 M_{A D} 、 M_{B D}$ 覆盖了 $S$, 从而 $\max \left\{W_{A C}, W_{B D}\right.$, $\left.W_{A D}, W_{B C}\right\} \geqslant \frac{2002-4}{4}>400$.
对于情形(2)(3), $M_{A C} 、 M_{B C} 、 M_{A D} 、 M_{B D} 、 M_{A B}$ 覆盖了 $S$, 从而 $\max \left\{W_{A C}\right.$, $\left.W_{B D}, W_{A D}, W_{B C}, W_{A B}\right\} \geqslant \frac{2002-4}{5}>399$, 从而 $\max \left\{W_{A C}, W_{B D}, W_{A D}\right.$, $\left.W_{B C}, W_{A B}\right\} \geqslant 400$. 于是必有 $P 、 Q$ 使得 $W_{P Q} \geqslant 400$.
下面证明存在这样的 $S$, 使得对所有 $P 、 Q \in S$ 都有 $W_{P Q} \leqslant 400$. 事实上, 如图(<FilePath:./figures/fig-c7i5.png>) 所示, 将 $S$ 中的 2002 个点分成 5组 $E$ 、 $F 、 G 、 H 、 I$, 其中 $H 、 F$ 中各有 401 个点, 而 $E$ 、 $I 、 G$ 中各有 400 个点, 每组中的点都位于相应方格的对角线上.
显然, 对任何一个矩形 $M_{P Q} (P 、 Q \in S)$, 它至多含有一个组中的点.
如果它包含的点属于组 $I$, 则 $W_{P Q} \leqslant 400$. 如果矩形 $M_{P Q}$ 包含了 $I$ 外的其他组中的点, 则点 $P 、 Q$ 中至少有一个属于这个组, 于是 $W_{P Q} \leqslant 401-1=400$.
综上所述, $N_{\text {max }}=400$.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例9. 在 $7 \times 8$ 的方格棋盘中, 每个方格都放有一只棋.
如果两只棋所在的方格有公共顶点, 则称这两只棋是相连的.
现在从这些棋中取出 $r$ 只棋, 使剩下的棋中没有 5 只棋在一条直线 (横、坚、斜 $45^{\circ}$ 或 $135^{\circ}$ 方向) 上依次相连, 求 $r$ 的最小值.
%%<SOLUTION>%%
解:称去掉棋的方格为"空", 并设棋盘中共有 $k$ 个空.
如图(<FilePath:./figures/fig-c7i6.png>),用 4 条直线将棋盘划分为 $A 、B 、 C 、 D 、 E 、 F 、 G 、 H 、 O$ 共 9 个区域.
由条件, $A \cup G$ 中至少 2 个空, $E \cup O$ 中至少 3 个空, $C \cup H$ 中至少 2 个空, $D \cup F$ 中至少 3 个空, 从而 $k \geqslant 2+3+2+3=10$.
如果 $k=10$, 则区域 $D$ 中没有空, 由对称性, 区域 $A 、 B 、 C 、 D$ 中都没有空.
进而, 因为 $A \cup G$ 中至少 2 个空,而 $A$ 中没有空, 从而 $G$ 中至少 2 个空, 同理, $H$ 中至少 2 个空, 因为 $A \cup E$ 中至少 3 个空, 而 $A$ 中没有空, 从而 $E$
中至少 3 个空, 同理, $F$ 中至少 3 个空, 于是, $E 、 F 、 G 、 H$ 中共至少 10 个空, 又棋盘中恰有 10 个空, 从而 $E 、 F$ 中各有 3 个空, $G 、 H$ 中各有 2 个空, 区域 $O$ 中没有空.
因为 $A \cup E$ 中每列至少 1 个空, 而 $A$ 中没有空, 从而 $E$ 中每列至少 1 个空.
又 $E$ 中只有 3 个空, 所以 $E$ 中每列恰有 1 个空, 于是格 $1 、 2$ 中至少有一个
不是空, 于是, 图中 2 条直线中有一条是 5 子相连,矛盾, 所以 $k \geqslant 11$.
当 $k=11$ 时, 如图(<FilePath:./figures/fig-c7i7.png>)
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline 1 & & & & & 6 & & \\
\hline & & & 5 & & & & \\
\hline & 2 & & & & & 9 & \\
\hline & & & & 8 & & & \\
\hline & & 3 & & & & & 11 \\
\hline 7 & & & & & 10 & & \\
\hline & & & 4 & & & & \\
\hline
\end{tabular}
(比"评分标准"中的构造更自然), 我们采用 "马步" 布子, 则棋盘中没有同一直线上的 5 子相连.
综上所述, $k_{min}=11$.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例10. 设集合 $S=\{1,2, \cdots, 50\}, X$ 是 $S$ 的任意子集, $|X|=n$. 求最小正整数 $n$, 使得集合 $X$ 中必有三个数为直角三角形的三条边长.
%%<SOLUTION>%%
解:直角三角形三边长分别为 $x, y, z$, 有 $x^2+y^2=z^2$, 其正整数解可表示为
$$
x=k\left(a^2-b^2\right), y=2 k a b, z=k\left(a^2+b^2\right), \label{eq1}
$$
其中 $k, a, b \in \mathbf{N}^*$ 且 $(a, b)=1, a>b$.
首先, $x, y, z$ 中必有一个为 5 的倍数.
否则, 若 $a, b, c$ 均不是 5 的倍数, 则 $a, b, c$ 都是形如 $5 m \pm 1,5 m \pm 2$ 的数 $(m \in \mathbf{N})$, 则 $a^2 \equiv \pm 1(\bmod 5)$, $b^2 \equiv \pm(\bmod 5), c^2 \equiv \pm 1(\bmod 5)$, 而 $c^2=a^2+b^2 \equiv 0$ 或士2,矛盾!
令集 $A=\{S$ 中所有与 5 互质的数 $\}$, 则 $\operatorname{Card} A=40$. 若以 10, 15, 25, 40,45 分别作直角三角形的某边长, 则由 式\ref{eq1} 知可在 $A$ 中找到相应的边构成如下直角三角形: $(10,8,6),(26,24,10),(15,12,9),(17,15,8)$, (39, $36,15),(25,24,7),(40,32,24),(41,40,9),(42,27,36)$, 此外, $A$ 中再没有能与 $10,15,25,40,45$ 构成直角三角形三边的数.
令 $M=A \cup\{10,15,25,40,45\} \backslash\{8,9,24,36\}$, 则 $\operatorname{Card} M=41$.
由以上知, $A$ 中三数不能组成直角三角形, 由于 $M$ 中不含 $8,9,24,36$, 所以 $10,15,25,40,45$ 在 $M$ 中找不到可搭配成直角三角形三边的数, 即 $M$ 中任三数均不构成直角三角形三边,故 $n \geqslant 42$.
另外, 由 式\ref{eq1} 的整数解可作集合: $B=\{3,4,5,17,15,8,29,21,20$, $25,24,7,34,16,30,37,35,12,50,48,14,41,40,9,45,36,27\}$, 其中横线上三数可作直角三角形三边, Card $B=27$.
$S \backslash B$ 中元素的个数为 $50-27=23$, 在 $S$ 中任取 42 个数, 因 $42-23=19$, 于是, 取的 42 个数中必含有 $B$ 中的 19 个数, 因此 $B$ 中至少有一条横线上的三个数在所选的 42 个数中, 即任取 42 个数, 其中至少有三数可作直角三角形三边, 因此, $n$ 的最小值为 42 .
%%PROBLEM_END%%


