每日一题[547]论证与构造

已知集合$A=\{1,2,3,\cdots ,23\}$，求最大的$m\in A$，使得$A$的任意一个包含$m$的$12$元子集中都存在两个不同的元素$a,b$，使得$a\mid b$．

---

分析与解    由于问题是求$m$的最大值，因此应该从大到小考虑．根据题意，如果我们构造出了一个任何两个元素均没有整除关系的$12$元子集，那么这个集合中的所有数均会被排除．

（1）直接取集合

$$\{12,13,14,\cdots ,23\},$$ 这样就否定了$m$的最大值是$12$到$23$的可能．

（2）由于$22=2\times 11$，因此把$22$换成$11$，就否定了$m$的最大值是$11$的可能．

（3）由于$20=2\times 10$，因此把$20$换成$10$，就否定了$m$的最大值是$10$的可能．

（4）由于$18=2\times 9$，因此把$18$换成$9$，就否定了$m$的最大值是$9$的可能．

（5）由于$16=2\times 8$，因此把$16$换成$8$，就否定了$m$的最大值是$8$的可能．

（6）由于$14=2\times 7$，然后$21=3\times 7$，因此无法用相同的手段否定$m$的最大值是$7$的可能．整理一下阶段性成果，取集合

$$\{12,13,14,15,8,17,9,19,10,21,11,23\},$$ 这样就否定了$m$的最大值是$8$到$11$的可能．

（7）我们尝试证明$m$的最大值为$7$．当子集中包含$7$时，$1,14,21$必然不能选，$13,17,19,23$必然可以选．此时将剩下的$15$个数分为以下$6$组：

$$\{22,11\},\{20,10\},\{18,9,3\},\{16,8,4,2\},\{15,5\},\{12,6\}.$$ 由于在这$15$个数中至少要选出$7$个数，因此必然会出现两个数存在整除关系．

综上所述，$m$的最大值为$7$．