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

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


cover

分析与解    由于问题是求$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$.

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

发表回复