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.

P.S The question assumes the following :

  1. If distance from any gangster A to any gangster B is x then distance from gangster B to gangster A is also x.

  2. No gangster commits suicide.

  • 5
    $\begingroup$ 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. $\endgroup$ Commented Dec 31, 2017 at 0:22
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Dec 31, 2017 at 0:34
  • 36
    $\begingroup$ So these gangsters, they are synchronized to millisecond precision? Now that's what I call organized crime. $\endgroup$
    – user856
    Commented Dec 31, 2017 at 0:51
  • 7
    $\begingroup$ Are gangsters living in three dimensional space? $\endgroup$ Commented Dec 31, 2017 at 0:55
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Dec 31, 2017 at 2:35

6 Answers 6


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.

  • 1
    $\begingroup$ It might be worthy to point out that we can rule out suicide, hence $3$ gansters is the special case, not $1$. $\endgroup$ Commented Dec 31, 2017 at 4:57
  • $\begingroup$ Even in the case of 3, of the ${3 \choose 2}$ pairs of gangsters, the pair with the shortest distance will shoot each other, so 1 is a valid base case. $\endgroup$
    – DanielV
    Commented Jun 8, 2023 at 8:46

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$.

  • 2
    $\begingroup$ You can also get smaller cycles $g_1$ shoots $g_2$ and $g_2$ shoots $g_1$. But at least one cycle is odd. $\endgroup$
    – N. S.
    Commented Dec 31, 2017 at 1:00
  • $\begingroup$ @N.S. Right! I assumed the graph was connected. $\endgroup$
    – clark
    Commented Dec 31, 2017 at 1:01
  • 1
    $\begingroup$ 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). $\endgroup$
    – N. S.
    Commented Dec 31, 2017 at 1:02
  • $\begingroup$ @N.S. thanks I included your comment in my answer $\endgroup$
    – clark
    Commented Dec 31, 2017 at 1:05
  • 5
    $\begingroup$ @N.S. Seems to me a 1-cycle is a suicide, not a survivor... $\endgroup$ Commented 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.

  • $\begingroup$ 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.) $\endgroup$ Commented Jun 23, 2021 at 7:38


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).

  • $\begingroup$ What is $d(g_i,g_j)$? $\endgroup$
    – Mr Pie
    Commented Dec 31, 2017 at 1:10
  • $\begingroup$ @user477343 This stands for the distance between gangster $i$ and gangster $j$ $\endgroup$
    – clark
    Commented Dec 31, 2017 at 1:17
  • $\begingroup$ @clark I was taught that for some value $x \in \mathbb{Z}, \ d(x) =$ the number of divisors of $x$... $\endgroup$
    – Mr Pie
    Commented Dec 31, 2017 at 1:24
  • $\begingroup$ @user477343 $\text{d}(x,y)$ is a common notation, when working in metric spaces, to denote the distance between elements $x$ and $y$. $\endgroup$
    – clark
    Commented Dec 31, 2017 at 1:26
  • $\begingroup$ @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 :) $\endgroup$
    – Mr Pie
    Commented 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.


If the gangsters shooting other is looked at as a directed graph, then it is impossible for the graph to have a cycle longer than 2. Because in a path without 2-cycles: $$G_1 \to G_2 \to G_3 \to \cdots$$

The distances between successive vertices must be decreasing. So if the cycle has $G_n \to G_1 \to G_2$ , it is saying that $G_1$ shoots $G_2$ despite $G_n$ being closer.

So the head of any path doesn't get shot, unless the path is a 2-cycle.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .