海盗互不对指：最小 n

Shootout

专题: Brainteaser / 脑筋急转弯
难度: L2
来源: QuantQuestion

题目详情

有 $n$ 个海盗，每个海盗有 2 门炮，分别指向其余 $n-1$ 个海盗中的两个不同人。

问：最小的 $n$ 是多少，才能做到“没有任何两名海盗互相指向对方”（不存在 A 指向 B 且 B 指向 A）？

$n$ pirates all stole some gold! However, all of them are greedy, so they each are loaded with $2$ cannons. Each of the $n$ pirates has $2$ cannons that they point at $2$ distinct pirates among the other $n-1$ pirates. What is the minimum value of $n$ such that it is possible to have a situation where no two pirates are mutually pointing cannons at one another?

解析

当 $n=4$ 时共有 $\binom{4}{2}=6$ 对海盗，但需要指向的炮共有 8 次指向，鸽巢原理可知必出现互指。

当 $n=5$ 时可构造：海盗 $i$ 指向 $(i+1)\bmod 5$ 与 $(i+2)\bmod 5$ ，则不存在互指。

因此最小 $n=5$ 。

Original Explanation

With $n = 2$ , clearly the pirates can only point at one another. With $n = 3$ , there are also only $2$ options for the pirates to point at. Therefore, $n \geq 4$ .

Note that there are $\binom{n}{2}$ pairs of pirates when we have $n$ pirates total. With $n = 4$ , there would be $6$ pairs of pirates but $8$ cannons that need to be pointed. Therefore, by Pigeonhole Principle, at least $2$ pirates will be pointing at one another. If $n = 5$ , then there would be $10$ pairs of pirates and $10$ cannons that need to be pointed. Therefore, the way we can match is that pirate $i$ , $1 \leq i \leq 5$ , points at pirates $(i+1) \text{ mod } 5$ and $(i+2) \text{ mod } 5$ . This satisfies our criterion, so $n = 5$ is our answer.