每日一题[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$ 组点对均为非同标点对,命题得证.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复