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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.