# $55$ gangsters shoot the nearest gangster to them, where all the distances between them are different. Prove that at least one gangster will survive.

My thinking was that if gangster A shoots gangster B, then gangster B will also shoot gangster A since they are the closest together, forming a pair. Since 55 is odd, then one must survive since 55 is 1 mod 2.

• Not necessarily true. Place three gangsters, A, B, and C, collinearly with B between A and C and B closer to C. A shoots B but B doesn't shoot A, meaning that your reasoning is false. – Franklin Pezzuti Dyer Dec 31 '17 at 0:22
• This must be my stupidest comment but if $A$ shoots $B$, how can $B$ also shoot $A$? Dead men with guns? Especially as the question is related to survival. Or did I miss a key piece of information? – Mohammad Zuhair Khan Dec 31 '17 at 0:34
• So these gangsters, they are synchronized to millisecond precision? Now that's what I call organized crime. – user856 Dec 31 '17 at 0:51
• Are gangsters living in three dimensional space? – Fimpellizieri Dec 31 '17 at 0:55
• Seems to me that the closest gangster to each gangster is going to be that same gangster. We'll see 55 suicides and no survivor. – SomeoneSomewhereSupportsMonica Dec 31 '17 at 2:35

The pair of gangsters with lowest pairwise distance will shoot each other. If some other gangster shoots any of those two, then there will be at most $52$ bullets aimed at the remaining $53$ gangsters, and hence at least one will survive.

If no other gangster shoots any of those two, the problem is reduced to the case of $53$ gangsters and we proceed by induction. At this point, it boils down to checking that the case for $3$ gangsters always ends up with one alive.

• It might be worthy to point out that we can rule out suicide, hence $3$ gansters is the special case, not $1$. – WorldSEnder Dec 31 '17 at 4:57

We will argue by contradiction. Assume everyone died.

Nobody can shoot the same guy twice since there are only 55 bullets and 55 people to kill.

So, WLOG$^{\ast}$,by renumbering $g_1$ shoots $g_2$, $g_2$ shoots $g_3$, ..., $g_{55}$ shoots $g_1$.

$^\ast$As N.S. noted there there can be different connected components, however since $55$ is odd one them must of length at least 3, or 1.

Denote $l_i$ the distance between $g_i$ and $g_{i+1}$, for $1\leq i\leq 54$ and $l_{55}$ the distance between $g_{55}$ and $g_1$.

Notice that $l_1>l_2$ since $g_2$ shoots $g_3$ and not $g_1$. Similarly $l_i>l_{i+1}$ which leads to a contradiction since $l_1>l_{54}>l_{55}$ and $l_{55}>l_1$.

• You can also get smaller cycles $g_1$ shoots $g_2$ and $g_2$ shoots $g_1$. But at least one cycle is odd. – N. S. Dec 31 '17 at 1:00
• @N.S. Right! I assumed the graph was connected. – clark Dec 31 '17 at 1:01
• Your argument works as long as there is a cycle of length $>2$. And the odd cycle must have lenght at least three (or is a 1-cycle, i.e. survivor). – N. S. Dec 31 '17 at 1:02
• @N.S. thanks I included your comment in my answer – clark Dec 31 '17 at 1:05
• @N.S. Seems to me a 1-cycle is a suicide, not a survivor... – David C. Ullrich Dec 31 '17 at 1:12

Say $G$ is the set of gansters. Define $s:G\to G$ by saying that $g$ shoots $s(g)$. We need to show $g$ is not surjective.

Suppose $g$ is surjective. Since $G$ is finite it follows that $g$ is injective.

And since $s$ is a bijection, the simple inductive argument in the deleted answer works: Say $d(g_1,g_2)$ is the smallest distance. Them $s(g_1)=g_2$ and $s(g_2)=g_1$. Since $s$ is a bijection on $G$ it follows that $s$ maps $G'=G\setminus\{g_1,g_2\}$ to itself. (This last point was not clear in the deleted answer, which is presumably why it was deleted.) It follows by induction that there exists $g$ with $s(g)=g$.

Of course if each gangster literally shoots the nearest gagnster then $s(g)=g$ for all $g$. But clearly what was intended is that each gangster shoots the nearest other gangster, in which case $s(g)=g$ iis a contradiction.

Hint

For each gangster $g_i$ define $$M_i= \min \{ d(g_i, g_j) \mid j \neq i \}$$

Since all the distances are different, $M= \max \{ M_i \}$ is exactly one of these distances, and hence can be attained at most twice.

Case 1: $M$ is attained exactly once. Let $i$ be the point where it is reached. Show that $g_i$ survives.

Case 2: $M$ is attained exactly twice. Let $i,j$ be the points where it is reached, i.e. $M_i=M_j=M$.

Show that $g_i$ shoots $g_j$, $g_j$ shoots $g_i$ and no other $g_k$ shoots either $g_i$ or $g_j$.

Thus the problem reduces to 53 gangsters shoot the nearest gangster to them, where all the distances between them are different. As you observed, the number being odd is the key for this reduction (i.e. induction over $n$ odd).

• What is $d(g_i,g_j)$? – Mr Pie Dec 31 '17 at 1:10
• @user477343 This stands for the distance between gangster $i$ and gangster $j$ – clark Dec 31 '17 at 1:17
• @clark I was taught that for some value $x \in \mathbb{Z}, \ d(x) =$ the number of divisors of $x$... – Mr Pie Dec 31 '17 at 1:24
• @user477343 $\text{d}(x,y)$ is a common notation, when working in metric spaces, to denote the distance between elements $x$ and $y$. – clark Dec 31 '17 at 1:26
• @clark ahh, so perhaps $\text{d}(n)$ for some integer $m$ would be the number of divisors of $m$, but if we have $\text{d}(n)$ for some ordered pair $n$ then this is different. Thanks for that :) – Mr Pie Dec 31 '17 at 1:38

As we are given an odd number 55 so, we can prove by taking any odd number. Let us take 5 for easy understating.

So, we have 5 gangsters and they are A, B, C, D and E.

Step 1 : If A shoots B and C shoots D then we are left with 3 gangsters A, C and E.

Step 2: Now its the turn of E. As there us no D so, E is closest to C and it will shoot C. Now we are left with A and E.

Step 3 : There is no one between A and E so, if A shoots E then A would survive.

So, each of 5 gangsters shoot their nearest gangster and one survived.

Similar is the case with 55 gangsters because 55 is also an odd number and if all 55 gangsters shoot their nearest gangster then, one will survive.