棋盘格苍蝇拍击杀苍蝇的拓展数学问题：能否击杀全部6只？

嘿，这个苍蝇拍的问题挺巧妙的，咱们从原问题开始，一步步拆解清楚：

原问题：证明总能击杀至少5只苍蝇 #

先明确问题背景：

6只苍蝇停在桌面上。现有尺寸远大于桌面的棋盘格图案苍蝇拍，需证明总能通过调整其位置与朝向，击杀至少5只苍蝇。规则为：苍蝇尺寸远小于拍面方格，若被黑色方格任意部分覆盖则被击杀。（来源：2017年华盛顿大学数学小时奥林匹克竞赛）

证明思路 #

核心用鸽巢原理结合棋盘格的两种基础形态：轴对齐的方格棋盘，和旋转45度后的菱形棋盘。

我们可以把平面上的每个点对应到四种“颜色组合”：

• 在轴对齐棋盘里是黑格，旋转45度棋盘里也是黑格
• 在轴对齐棋盘里是黑格，旋转45度棋盘里是白格
• 在轴对齐棋盘里是白格，旋转45度棋盘里是黑格
• 在轴对齐棋盘里是白格，旋转45度棋盘里也是白格

现在有6只苍蝇，分到4种组合里，根据鸽巢原理，至少有一个组合里有至少2只苍蝇。

反过来想：如果假设存在6只苍蝇，无论怎么调棋盘格都最多击杀4只，那就意味着每个棋盘格至少有2只苍蝇存活。但6只苍蝇的两两组合有15种，而棋盘格的可能配置是无限的，必然存在一种配置，使得只有1只苍蝇在白格——换句话说，至少5只被击杀。

直白点说：6只苍蝇不可能在所有棋盘格配置里都有2只存活，必然存在一种配置最多1只存活，也就是至少5只被击杀。

技术问询1：是否总能击杀全部6只苍蝇？ #

答案是不能。我们可以构造出6只苍蝇的位置，让你无论怎么调棋盘格，都没法全杀。

比如，把6只苍蝇分成四组：两组各2只，另外两组各1只，每组对应上面说的一种颜色组合。这时候，无论你选哪种棋盘格（轴对齐或旋转45度，怎么平移），至少会有一组的苍蝇落在白格——要么是那两组2只的其中一组（击杀6-2=4只），要么是那两组1只的其中一组（击杀6-1=5只）。总之，最多只能击杀5只，没法全杀。

技术问询2：一般情况：n只苍蝇最多能保证击杀多少只？ #

这个问题的最优结论是：最多能保证击杀⌈3n/4⌉只（⌈x⌉表示向上取整），换句话说就是n减去⌊n/4⌋（向下取整）。

为什么这个数是对的？ #

• 存在性：用鸽巢原理，n只苍蝇分到4种颜色组合里，至少有一个组合有⌈n/4⌉只苍蝇。我们可以调整棋盘格，让这个组合的苍蝇落在黑格，同时让其他组合里的苍蝇尽可能多落在黑格，最终击杀数至少是n - ⌊n/4⌋ = ⌈3n/4⌉。
• 最优性：我们可以构造对应的苍蝇位置，比如把n只苍蝇平均（或尽可能平均）分到4种颜色组合里，这样任何棋盘格最多只能击杀3组的苍蝇，也就是⌈3n/4⌉只，没法更多。

举几个例子验证：

• n=4：⌈12/4⌉=3，确实最多保证杀3只（4只各占一种组合，任何棋盘格都有1只存活）
• n=5：⌈15/4⌉=4，最多保证杀4只
• n=6：⌈18/4⌉=5，和原问题结论一致

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