求证|A+B|≥m+n-1的思路咨询（A,B⊂ℤ，|A|=m,|B|=n）

嘿，我明白你现在卡在这儿了——三分法确实能给出max(m,n)这个下界，但离目标的m+n-1还差一点。其实这个结论是柯西-达文波特定理在整数加法群ℤ上的特例，咱们可以用更直观的排序构造法来推导，比归纳法更直接：

核心推导步骤 #

1. 先对集合排序
   把A中的元素按从小到大排列：a₁ < a₂ < ... < aₘ；同理把B排序为b₁ < b₂ < ... < bₙ。

2. 构造两个递增的和序列

   • 第一个序列：固定A中的最小元素a₁，和B中所有元素相加，得到a₁+b₁ < a₁+b₂ < ... < a₁+bₙ，这是n个互不相同的元素，都属于A+B；
   • 第二个序列：固定B中的最大元素bₙ，和A中所有元素相加，得到a₁+bₙ < a₂+bₙ < ... < aₘ+bₙ，这是m个互不相同的元素，也都属于A+B。

3. 合并序列并统计元素数
   注意这两个序列的衔接点是a₁+bₙ——它是第一个序列的最后一个元素，也是第二个序列的第一个元素，所以合并后不同元素的总数是n + m - 1（减去重复的1个）。
   而这个合并后的序列是A+B的子集，因此必然有|A+B| ≥ m+n-1。

关于你用三分法的补充 #

你之前得到的max(m,n)是只考虑了“固定一个集合的单个元素，加另一个集合所有元素”的情况，但把两个方向的递增序列结合起来，就能得到更紧的下界。如果想用归纳法验证，也可以试试：

• 基例：当m=1或n=1时，|A+B|=max(m,n)=1+max(m,n)-1，显然成立；
• 归纳假设：假设当|A|=k-1，|B|=n时，|A+B|≥(k-1)+n-1；
• 归纳步骤：取A中最大元素aₘ，令A'=A\{aₘ}，则A+B=(A'+B)∪({aₘ}+B)。根据容斥原理，|A+B|≥|A'+B|+|{aₘ}+B|-|(A'+B)∩({aₘ}+B)|。由于aₘ是A中最大元素，{aₘ}+B里的元素整体都大于A'+B中除了aₘ₋₁+bₙ之外的元素，实际交集最多只有1个元素，代入后就能得到|A+B|≥(k-1+n-1)+n-1=k+n-1，完成归纳。

内容的提问来源于stack exchange，提问作者Anacardium