若集合 $\{1,2,3,\cdots ,2014\}$ 的某些子集满足条件:没有一个数是另一个数的 $2$ 倍,则这样的子集中所含元素的个数最多是
【难度】
【出处】
2015年第二十六届“希望杯”全国数学邀请赛高一(一试)
【标注】
  • 数学竞赛
    >
    简单组合
    >
    简单组合
  • 题型
    >
    组合数学
    >
    集合的分划
  • 题型
    >
    组合数学
    >
    组合极值
【答案】
$1343$
【解析】
将集合 $A=\{1,2,3,\cdots ,2014\}$ 中的元素 $x$ 写成 $m\cdot 2^n$,其中 $m$ 是奇数,$n$ 是自然数,记为 $x=(m,n)$.若 $x_1=(m_1,n_1)$,$x_2=(m_2,n_2)$,则\[\dfrac{x_1}{x_2}=2\Leftrightarrow (m_1=m_2)\land (n_1=n_2+1).\]于是将集合 $A$ 中的元素按 $m$ 划分为 $P_1,P_3,\cdots,P_{2013}$,其中 $P_k$ 是所有形如 $(k,n)$ 的 $x$ 构成的集合.依照题意,将每个集合 $P_k$ 中的数从小到大排成一行,将 $P_1,P_3,\cdots,P_{2013}$ 依次排成下表.\[\begin{array}{c|ccccccccc}
m\backslash n&0&1&2&3&4&5&6&7&8&9&10\\ \hline
1& 1&2&4&8&16&32&64&128&256&512&1024\\
3&3&6&12&24&48&96&192&384&768&1536&\\
5&5&10&20&40&80&160&320&640&1280&&\\
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\
2013&2013&&&&&&&&\end{array}\]从这个表中取出 $n=0,2,4,6,8,10$ 对应的列中的元素组成的集合元素个数最多.这些列中的元素个数之和为\[\sum_{i=0}^{5}\left(\left[\dfrac{2014-2^{2i}}{2^{2i+1}}\right]+1\right)=1343.\]
题目 答案 解析 备注
0.116445s