Sum-free subset 老题

一个集合 \(S\) 被称为 sum-free set 当且仅当 \(\forall a, b \in S, a + b \not\in S\)。

试证明：对于任何一个集合 \(A \subseteq \ZZ\backslash\{0\}\)，其最大的 sum-free subset 大小至少为 \(|A| / 3\).

（有一个和题面差不多长度的解答）

解答

对于 \(t \sim U[0, 1]\)，令 \(A_t := \{x \in A: 1/3 < xt \bmod 1 < 2/3 \}\)。显然 \(A_t\) 为 sum-free set. 最后再注意到 \(\max_t |A_t| \geq \mathbb{E}_t [|A_t|] = |A|/3\) 即可。

解法来自 Erdos。