Ten gangsters are standing on a flat surface, and the distances between them are all distinct. Suddenly, each of them fatally shoots the one among the other nine gangsters that is the nearest. What is the maximum possible number of surviving gangsters?

I consider the general case of N gangsters.
Since the gangsters are not suicidal, at least two must fall. Let's try to determine the maximum N with two fallen. Put the locations of the two fallen gangsters at the points A1 and A2. Then for all k,m > 2, the distance inequalities must hold:
A1A2 < min(A1Ak, A2Ak, A1Am, A2Am)    and
max( min(A1Ak, A2Ak), min(A1Am, A2Am) ) < AkAm
Geometrically we can build up a picture as follows:
#1 Draw two circles, each of radius A1A2 and centred at A1 and A2. Then each Ak is excluded from the union of these two circles.
#2 Each selection of a new A will add new constraints, further expanding the exclusion zone for future choices as follows: Once Ak is selected (for k>2), we draw the perpendicular bisectors of A1Ak and A2Ak. This divides the plane into four sectors (non-degenerate case). One of these sectors violate one of the distance inequalities. Namely, the sector which includes Ak. This sector then has to be included with the previously identified exclusion zones.
#3 Note that in selecting Ak, not only do we have to observe the above exclusion zones, but we also have to assure that the newly computed exclusion zone associated with Ak does not encompass any of the previously drawn gangster locations. This can be done by excluding the circle, centred at Ak, and including whichever of the two points, A1 and A2 is closest.
The exclusion zone that emerges, after N gangsters, is the union of N circles and N-2 sectors, where each "sector" is one of the four (unbounded) regions cut out by the intersection of two lines. And the question that emerges, is how to arrange the gangster positions such that a maximum number of gangsters is needed before the exclusion zone includes the whole plane.
The attached image shows a solution. Instead of using A1..10, I have the two dead gangsters at A and B, with the survivors in the C gang.It's true that each of the gangsters located in the C positions have the option of shooting down two of their fellow C-ompatriots, who are just as close as one of the fellows from the AB gang. But in my solution the C-gangsters are utilitarians, and seek to minimise the harm done to human life. So, maybe I should have indexed them with G, making them G-men.

Edited on May 20, 2020, 6:59 pm

Posted by FrankM on 2019-05-07 08:42:53