每日一题[2855]有限覆盖

设 $M$ 为正整数,区间 $I_k=[a_k,a_k+1]$(其中 $a_k\in\mathbb R$,$k=1,2,\cdots,M$)同时满足下列两个条件:

① 对任意 $x\in [0,100]$,存在 $k$ 使得 $x\in I_k$;

② 对任意 $k\in\{1,2,\cdots,M\}$,存在 $x\in[0,100]$,使得 $x\notin \bigcup\limits_{i\ne k}I_i$,其中 $\bigcup\limits_{i\ne k}I_i$ 表示除 $I_k$ 外的 $M-1$ 个集合的并集.

1、若 $M=100$,直接写出下列两个数列是否满足条件:

① $a_k=k-1$($k=1,2,\cdots,100$);_______.

② $a_k=\dfrac k2-1$($k=1,2,\cdots,100$);_______.

2、求 $M$ 的最小值.

3、判断 $M$ 是否存在最大值,若存在,求 $M$ 的最大值;若不存在,请说明理由.

解析

1、① $I_k:~[0,1],[1,2],[2,3],\cdots,[99,100]$,符合题意;

② $I_k:~\left[-\dfrac 12,\dfrac 12\right],\left[\dfrac 12,\dfrac 32\right],\cdots,\left[49,50\right]$,于是 $51$ 不在任何区间 $I_k$ 中($k=1,2\cdots,M$),不符合题意.

2、$M$ 的最小值为 $100$.

首先,第 $(1)$ 小题中 ① 即为 $M=100$ 的例子;

其次,若 $M\leqslant 99$,不妨设 $a_1\leqslant a_2\leqslant\cdots\leqslant a_M$.显然 $a_1\leqslant 0$,否则 $0\in [0,100]$,且 $0$ 不在任何 $I_k$($k=1,2,\cdots,M$)中.进一步\[a_{k+1}-a_k\leqslant 1,\]否则若 $a_{k_0+1}-a_{k_0}>1$,则\[I_{k_0}=\left[a_{k_0},a_{k_0}+1\right],\quad I_{k_0+1}=\left[a_{k_0+1},a_{k_0+1}+1\right],\]取 $x\in\left(a_{k_0}+1,a_{k_0+1}\right)$,则 $x$ 不在任何 $I_k$($k=1,2,\cdots,M$)中,不符合题意. 进而\[a_M+1\leqslant a_{M-1}+2\leqslant \cdots\leqslant a_1+M\leqslant M\leqslant 99 ,\]这样就有 $100\in [0,100]$,且 $100$ 不在任何 $I_k$($k=1,2,\cdots,M$)中,不符合题意.

综上所述,$M$ 的最小值为 $100$.

备注    即要覆盖长度为 $100$ 的区间,至少需要 $100$ 个长度为 $1$ 的区间.

3、根据题意,条件 ① 即\[[0,100]\subseteq\bigcup_{1\leqslant i\leqslant M} I_i,\]条件 ② 即\[ [0,100]\not\subseteq \bigcup\limits_{i\ne k}I_i,~k=1,2,\cdots,M,\]也即去掉 $I_k$($k=1,2,\cdots,M$)中的任意一个区间,都不能覆盖 $[0,100]$.

不妨设 $a_1\leqslant a_2\leqslant \cdots a_M$,则\[I_k\not\subseteq I_{k-1}\cup I_{k+1},~k=2,\cdots,M-1,\]因此\[a_{k-1}+1<a_{k+1},~k=2,\cdots,M-1.\]此外 $a_2>0$ 且 $a_{M-1}+1<100$,否则去掉 $I_1$ 或 $I_M$,仍可以覆盖 $[0,100]$.

接下来给出 $M=200$ 的例子,为\[I_{2k-1}:~[-0.999,0.001],[0.002,1.002],[1.003,2.003],\cdots,[97.099,98.099],[98.100,99.100],\]而\[I_{2k}:~[0.001,1.001],[1.002,2.002],\cdots,[98.099,99.099],[99.100,100.100],\]也即 $I_{2k-1}$ 在 $0,1,2,\cdots,99$ 右侧附近各留宽度为 $0.001$ 的缝,然后用 $I_k$ 去补这些缝,如图(为 $M=8$ 的例子).

若 $M\geqslant 201$,则\[a_{M-1}>a_{M-3}+1>\cdots>a_{M-199}+99\geqslant a_2+99>99,\]矛盾. 综上所述,$M$ 的最大值为 $200$.

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

发表回复