集合{1,2,…,100}的75元子集S必含三个连续整数吗？鸽巢原理分析存疑

你的直觉完全正确！不过你一开始选的鸽巢划分方式（重叠的98个三元组）不太适合用鸽巢原理推导，咱们换个不相交的鸽巢划分就能把逻辑理得明明白白：

• 第一步：构造合适的鸽巢
  把集合{1,2,…,100}拆成34个不相交的子集（也就是鸽巢）：

  • 前33个是完整的三元组：(1,2,3), (4,5,6), ..., (97,98,99)
  • 最后一个是单独的元素：{100}

• 第二步：计算不含三个连续整数的子集最大规模
  对于每个完整的三元组，我们最多只能选2个元素（选3个就直接出现三个连续整数了），所以33个三元组最多能选出 33×2=66 个元素；再加上最后一个单独的100，总共最多能凑出 66+1=67 个元素，组成一个完全不含三个连续整数的子集。

• 第三步：用鸽巢原理推导结论
  现在我们的子集S有75个元素，75 > 67，这意味着必然至少有一个完整的三元组里，我们选了超过2个元素——也就是选了全部3个元素，这三个就是一组连续整数。

顺便补充下你最初思路的问题：你选的98个三元组是重叠的（比如(1,2,3)和(2,3,4)共享元素2和3），这种重叠的鸽巢没法直接用鸽巢原理计数，因为一个元素可能属于多个鸽巢，没法精准限制每个鸽巢里的“鸽子”数量。而我们用的不相交鸽巢，每个元素只属于一个鸽巢，就能准确算出最大无连续三元组的子集规模啦。

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