返回题库

用最小整数子集表示 1..40（每数最多用一次，可加可减

Find the smallest subset of integers

专题
Discrete Math / 离散数学
难度
L4

题目详情

求最小规模的整数子集，使得可仅用“+”或“-”（且每个数最多使用一次）表示出 1,2,…,401,2,\ldots,40。

Find the smallest subset of integers that you can use to produce 1,2,..., 40 by only using “+” or “- ” (each number in the subset can be used at most one time).

解析

若子集有 kk 个数，每个数可“+用 / -用 / 不用”三种状态，所以最多得到 3k3^k 个不同和值。

要覆盖 1∼401\sim 40（连同对应负数与 0，至少需要 81 个值：−40∼40-40\sim 40），故

3k≥81⇒k≥4.3^k\ge 81\Rightarrow k\ge 4.

4 个数是否可行？取

{1,3,9,27}.\{1,3,9,27\}.

任意系数取 −1,0,1-1,0,1，可得到平衡三进制表示，覆盖区间

−(1+3+9+27)∼(1+3+9+27)=−40∼40.-(1+3+9+27)\sim (1+3+9+27)= -40\sim 40.

因此最小规模为 4，最小子集可取

{1,3,9,27}.\boxed{\{1,3,9,27\}}.