每日一题[3229]逐步替换

平面直角坐标系内有 $10$ 个不同点，$P_{1}\left(x_{1}, y_{1}\right), P_{2}\left(x_{2}, y_{2}\right), \cdots,P_{10}\left(x_{10}, y_{10}\right)$，若 $x_{i}=x_{j}$ 或 $y_{i}=y_{j}$，则称 $P_{i}$ 与 $P_{j}$ 为一个“同标点对”（不考虑 $P_{i}$ 与 $P_{j}$ 的次序）．若 $10$ 个不同点满足：与每个点构成“同标点对”的点均不超过 $m$ 个；无论何种情况，都可以恰好将它们分成 $5$ 个点对，每个点对都不是“同标点对”．求 $m$ 的最大值．

答案    $4$．

解析    $m$ 的最大值为 $4$，证明如下．

如果 $P_i,P_j$ 的横坐标或纵坐标不同，则称 $P_i$ 与 $P_j$ 为一个非同标点对．

若 $m\geqslant 5$，设 $P_1,P_2,\cdots,P_6$ 的横坐标相同，此时无法将这 $10$ 个点分成 $5$ 个非同标点对． 接下来证明 $m=4$ 时符合题意．将 $10$ 个点分为 $5$ 组 $(A_i,B_i)$（$i=1,2,3,4,5$），若其中有某个点对是同标点对，不妨设为 $(A_1,B_1)$，则考虑以下 $8$ 种交换方案： 将 $(A_1,B_1)$ 与 $(A_k,B_k)$ 替换为 $(A_1,A_k)$ 与 $(B_1,B_k)$ 或者替换为 $(A_1,B_k)$ 与 $(B_1,A_k)$，其中 $k$ 分别取 $2,3,4,5$，其余组不变． 由于 $A_{1}, B_{1}$ 除了 $A_{1}, B_{1}$ 外，至多各还有 $3$ 个点与之构成“同标点对”，故上述 $8$ 种方案中必存在一种，使得调整后的两个点对均为非同标点对，这样就减少了这 $5$ 组点对中同标点对的数量．因此至多经过 $5$ 次交换，就可以使得 $5$ 组点对均为非同标点对，命题得证．