UOJ Logo Vanishment的博客

博客

标签
暂无

关于由闭区间[1, n]的整数构成的满足任意两数无整除关系的集合问题的疑惑

2019-10-31 10:31:11 By Vanishment

记这个集合为$S = \{s_1, s_2, s_3 \dots s_k\}$,如果其满足:

  1. $\forall_{1 \le i \le k}\ \ s_i \in \{1, 2, 3 \dots n\}$.

  2. $\forall_{1 \le i \le k,\ 1 \le j \le k,\ i \ne j}\ \ s_i \ne s_j$.

  3. $\forall_{1 \le i \le k,\ 1 \le j \le k,\ i \ne j,\ s_i < s_j}\ \ s_i \nmid s_j$.

则:

(1) 这样的集合最大(指元素个数)大小是否是$\lceil \frac{n}{2} \rceil$?

(2) 如果这样的集合最大大小是$\lceil \frac{n}{2} \rceil$,如何证明?

(3) 对于给定的$n$有几个这样的最大集合?

(4) 如何枚举所有这样的最大集合?

共 1 篇博客