每日一题[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$．