(1)设 $X = {1,2,…,100}$,$A$ 是 $X$ 的子集.若对 $A$ 中任何两个元素 $x,y(x < y)$,都有 $y≠3x$,求 $|A|$ 的最大值.
(2)如果一个集合不包含满足 $x + y = z$ 的三个数 $x,y,z$(可以相同)则称之为单纯的.设 $M = {1,2,…,2n+1}$,$A$ 是 $M$ 的单纯子集,求 $|A|$ 的最大值.
【难度】
【出处】
【标注】
【答案】
【解析】
(1)令
$A=\{3k+1|k=0,1,2,\cdots,33\}\bigcup \{3k+2|k=0,1,2,\cdots ,32\}\bigcup \{9,18,36,45,63,72,81,90,99\}$,
则 $A$ 显然合乎条件,此时 $|A|=76$ 。
另一方面,考察24个集合 ${{A}_{k}}=\{k,3k\}$ $(k=1,2,12,13,\cdots33)$,它们含有48个互异的数,去掉这些数外,$X$ 中还有52个数,将这52个数中的每一个数都作成一个单元素集合,连同前面24个集合共76个集合。若 $|A|>76$,则 $A$ 必含有某个集合 ${{A}_{k}}$ 中的2个数,其中 较大的数是其较小的数的3倍,矛盾。
综上所述,$|A|$ 的最大值是76.
(2)取 $A=\{1,3,5,\cdots,2n+1\}$,则 $A$ 是单纯的,此时 $|A|=n+1$ 。下面证明:对任何单纯子集 $A$,有 $|A|\leqslant n+1$ 。用反证法。假设 $|A|>n+1$,则 $A$ 中至少有 $n+2$ 个元素,设为:${{a}_{1}}<{{a}_{2}}<\cdots<{{a}_{n+2}}$ 。
设 $A$ 中有 $p$ 个奇数 ${{a}_{1}}<{{a}_{2}}<\cdots<{{a}_{p}}$ 和 $n+2-p$ 个偶数 ${{b}_{1}}<{{b}_{2}}<\cdots<{{b}_{n+2-p}}$ 。注意到 $M$ 中共有 $n+1$ 个奇数,$n$ 个偶数,所以 $p\geqslant 2$ 。
考察:${{a}_{2}}-{{a}_{1}}<{{a}_{3}}-{{a}_{1}}<\cdots<{{a}_{p}}-{{a}_{1}}$ 。它们都是正偶数,连同 ${{b}_{1}}<{{b}_{2}}<\cdots<{{b}_{n+2-p}}$,共有 $(p-1)+(n+2-p)=n+1>n$ 个正偶数。由抽屉原理,必有两个元素相等,且只能是某个 ${{b}_{i}}$ 与某个 ${{a}_{j}}-{{a}_{1}}$ 相等,于是 ${{a}_{1}}+{{b}_{i}}={{a}_{j}}$,所以 $A$ 不是单纯的。
答案 解析 备注
0.108854s