All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
A geometric gangster shooting (Posted on 2019-05-06) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Danish Ahmed Khan    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution with explanation Comment 6 of 6 |

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 utilitarian/altruistic. So they seek to minimise the harm done to human life. (Perhaps I should have indexed them with G, making them G-men).


https://www.geogebra.org/classic/vtrcjhwf

  Posted by FrankM on 2020-05-20 19:44:20
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (19)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information