# $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. Dec 31, 2017 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? Dec 31, 2017 at 0:34
• So these gangsters, they are synchronized to millisecond precision? Now that's what I call organized crime.
– user856
Dec 31, 2017 at 0:51
• Are gangsters living in three dimensional space? Dec 31, 2017 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. Dec 31, 2017 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$. Dec 31, 2017 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. Dec 31, 2017 at 1:00
• @N.S. Right! I assumed the graph was connected. Dec 31, 2017 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). Dec 31, 2017 at 1:02
• @N.S. thanks I included your comment in my answer Dec 31, 2017 at 1:05
• @N.S. Seems to me a 1-cycle is a suicide, not a survivor... Dec 31, 2017 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 $$s$$ is surjective. Since $$G$$ is finite it follows that $$s$$ 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.

• Dear David, I have taken the liberty to correct a little typo in line 3: you had written $g$ instead of $s$. (And I upvoted your nice solution, of course.) Jun 23, 2021 at 7:38

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)$? Dec 31, 2017 at 1:10
• @user477343 This stands for the distance between gangster $i$ and gangster $j$ Dec 31, 2017 at 1:17
• @clark I was taught that for some value $x \in \mathbb{Z}, \ d(x) =$ the number of divisors of $x$... Dec 31, 2017 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$. Dec 31, 2017 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 :) Dec 31, 2017 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.