MathLabs

第4题

设 nn、bb 为正整数。若存在由 nn 个互不相同且小于 bb 的正整数组成的集合,使不同子集 UU、VV 中元素在 UU 中的和与在 VV 中的和从不相等,则称 nn 是 bb-可辨的。(a) 证明 88 是 100100-可辨的。(b) 证明 99 不是 100100-可辨的。
第 4/4 步:与小于一百矛盾
(s4+⋯+s9)−(s1+s2+s3)≥419,(s1+s2+s3+s6+s7+s8+s9)−(s4+s5)≥399(s_4+\cdots+s_9)-(s_1+s_2+s_3)\ge419,\quad (s_1+s_2+s_3+s_6+s_7+s_8+s_9)-(s_4+s_5)\ge399
详细分析

再数含有两个、三个或四个大于 s_3 的元素的子集,共 400 个,故第二个端点差至少 399。两不等式相加得 s_6+s_7+s_8+s_9 至少为 409。但这四个数都不超过 99,和至多 394,矛盾。因此 (b) 成立。