A graup of pirates had an argument and not each of them holds some other two at gunpoint.All the pirates are called one by one in some order.If the called pirate is still alive , he shoots both pirates he is aiming at ( some of whom might already be dead .) All shorts are immediatcly lethal . After all the pirates have been called , it turns out the exactly $28$ pirates got killed . Prove that if the pirates were called in whatever other order , at least $10$ pirates would have been killed anyway.
Problem
Source: MEMO 2018 T3
Tags: combinatorics
skrublord420
03.09.2018 05:41
Boom! Another hidden graph theory problem. Pirates, roads, schools, groups of students, cities, bridges, etc. Why can't we have pirate themed geometry and number theory problems?
randomusername
05.09.2018 14:43
The pirates come in order $P_1,P_2,\dots,P_n$. They start killing each other. In the end, we'll have three kinds of pirates: ones who died before they could kill anyone (1) ones who died after shooting (2) survivors (3) Suppose that we can reorder the pirates in a way that $\le 9$ pirates die in the process. Then all of groups (2) and (3) held their guns at $\le 9$ pirates. Also, group (1) has at most $9$ members, which means that $\le 9+9\cdot 2=27$ pirates are held at gunpoint. This contradicts the condition that the pirates can be ordered in a way that $28$ pirates die, proving the problem's claim.