Skip to content

Fewest pirates with no mutual cannon aiming

Question

There are nn pirates. Each pirate aims two cannons, at two different pirates other than himself. What is the smallest nn for which the aiming can be arranged so that no pair of pirates have cannons aimed at each other?

Short answer

55. With n≤4n\le 4 there are (n2)\binom n2 pairs but 2n2n aimed cannons, and 2n>(n2)2n>\binom n2, so some pair must aim at each other. For n=5n=5 there are exactly 1010 pairs and 1010 cannons, and pirate ii aiming at i+1i+1 and i+2i+2 (mod 5) uses each pair once.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution