每日一题[3320]解耦合

称集合 $X$ 为 $Q$ 集合,如果 $X$ 满足如下三个条件:

条件一:$X$ 中有 $20$ 个元素;

条件二:$X$ 中的每个元素都是包含于 $[0,1]$ 的闭区间;

条件三:对任意实数 $r\in[0,1]$,$X$ 中包含 $r$ 的元素个数不超过 $10$.

对于 $Q$ 集合 $A,B$,$I\in A$,$J\in B$,满足 $I\cap J\neq\varnothing$ 的区间对 $(I,J)$ 的个数的最大值为_____.

答案    $300$.

解析   

 $Q$ 集合的几何直观    将 $X$ 中的元素(即闭区间 $[a,b]$)看作数轴上连接 $(a,0),(b,0)$ 的线段,则根据题意 $X$ 是线段 $OT$($O(0,0)$,$T(1,0)$)内(包括端点)内部的 $20$ 条线段,其在任何一个位置 $t\in[0,1]$ 处覆盖的线段条数不超过 $10$.

定义变换 $T$     若 $Q$ 集合 $X$ 中有元素 $[a,b],[c,d]$,且 $0<a<c<b<d<1$,则将其置换为 $[a,d],[c,b]$,此时得到的新集合仍然是 $Q$ 集合,且不影响所求的区间对个数.

利用变换 $T$ 化简问题    不断对集合 $A,B$ 使用 $T$ 变换,则 $A,B$ 均为转化为若干组线段,其中组内线段依次包含、组间线段没有公共点.根据条件三,每组线段的条数最大值不超过 $10$. 设变换完成的集合 $A,B$ 按顺序依次有 $m,n$ 组线段,且各组线段条数分别为 $a_1,a_2,\cdots,a_m$ 以及 $b_1,b_2,\cdots,b_n$,满足\[a_1+a_2+\cdots+a_m=b_1+b_2+\cdots+b_n=20,\]构造 $20\times 20$ 的正方形,两边分别划分成 $m,n$ 份,形成 $m\cdot n$ 个矩形.若线段组有公共部分,则将对应的矩形染色,则满足条件 $I\cap J\neq\varnothing$ 的区间对 $(I,J)$ 的个数即染色矩形面积之和.根据题意,每个矩形的长和宽都不超过 $10$,因此上下重叠的面积不超过 $\dfrac 12\cdot 10\cdot 20=100$,因此染色矩形面积之和不超过 $300$.

构造组合极值情形    如图,设 $0<a_1<b_1<c_1<d_1<1$,集合 $A$ 由 $10$ 条起点为 $0$,终点均在 $a_1,b_1$ 之间的线段,以及 $10$ 条终点为 $1$,起点均在 $c_1,d_1$ 之间的线段组成; 设 $0<a_2<b_2<c_2<d_2<1$,集合 $A$ 由 $10$ 条起点为 $0$,终点均在 $a_2,b_2$ 之间的线段,以及 $10$ 条终点为 $1$,起点均在 $c_2,d_2$ 之间的线段组成; 当 $d_1<a_2$ 时,$(I,J)$ 的个数为 $300$(除了 $A_1\sim A_{10}$ 与 $B_{11}\sim B_{20}$ 形成的线段对没有公共点外,其余线段对均有公共点).

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

发表回复