At least how many gangsters will be killed?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

At least how many gangsters will be killed?

G H J

Reveal topic tags

Pythagorean Theorem

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2000, G7

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Aug 10, 2008, 1:32 AM • 3 Y

Y by Adventure10, ihatemath123, Mango247

Ten gangsters are standing on a flat surface, and the distances between them are all distinct. At twelve o’clock, when the church bells start chiming, each of them fatally shoots the one among the other nine gangsters who is the nearest. At least how many gangsters will be killed?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

635 posts

#2 h Aug 11, 2008, 9:30 AM • 3 Y

Y by me9hanics, Adventure10, Mango247

Answer: 7 ( I will post my solution when I have free time)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2049 posts

#3 h Mar 18, 2009, 3:50 PM • 1 Y

Y by Adventure10

it seems like 4 is possible if you have 6 gangsters in a large nearly-regular hexagon, with 4 in the middle in a small nearly-regular quadrilateral?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

736 posts

#4 h Mar 19, 2009, 10:42 AM • 2 Y

Y by Adventure10, Mango247

I think $3$ is least. Consider gangsters at:

$(-100,0),(0,0),(101,0),(213,0),(0,110),(0,-111),(-120,110),(-120,-111),(121,110),(121,-111)$

(the hundred's digit gives the rough position, tens digit changes the relative positions a little bit so that desired 3 people get killed and the units digit distorts the positions slightly so that any 2 distances aren't the same)

2 can't happen can't be that hard ...

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

484 posts

#5 h Mar 27, 2009, 2:35 PM • 2 Y

Y by me9hanics, Adventure10

aadil wrote:

i dont see the geometry in this problem

In the case to prove 8 doesn't work there are some angle chasing and geo inequality things.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

202 posts

fwolth

#6 h Aug 3, 2009, 10:19 PM • 1 Y

Y by Adventure10

Hmm why is everyone in this thread except not_trig answering the question "what is the maximum number of survivors" rather than "at least how many people will die"? Anyways, here's my solution - might be wrong, though:

As before, claim that $3$ is the minimum, with an example helpfully provided by Akashnil. It remains to prove that we cannot have only two deaths; one or zero is trivial.

Suppose for the sake of contradiction that we could have exactly two deaths. Then let the fated ones be $A,B$ , and the other eight $C,D,E,F,G,H,I,J$ . $A,B$ clearly must be the closest pair together, shooting each other, and each of the other eight must shoot one of $A,B$ . We claim that exactly four must shoot each; this is an easy contradiction argument - suppose five shot one ( $B$ ), and consider the second-closest gangsta to $B$ ( $C$ ); draw a circle with center $B$ and radius $BC$ . Then it's easy to show the projections of the other four must be spaced at least $\pi/3$ apart on the circle, and $A$ lies within the circle with a person being closer to $A$ if his projection onto the circle was on a certain $2\pi/3$ arc, so at least one of them must shoot $B$ rather than $A$ .

For the 4 and 4 case, let $S_A=\{C,D,E,F\}$ shoot $A$ , $S_B=\{G,H,I,J\}$ shoot $B$ , with $CA<DA<EA<FA$ , $GB<HB<IB<JB$ . Consider the circles with centers $A,B$ and radii $CA,GB$ respectively, as before, and note that again the projections of the gangstas onto their respective circles are spaced at least $\pi/3$ apart, as before. Additionally, note both radii are greater than $AB$ and hence circle $A$ contains $B$ and circle $B$ contains $A$ . We claim that there exists either a gangsta in $S_A$ who shoots someone from $S_B$ or vice versa.

Lemma: If there is a gangster $A'$ in $S_A$ which has projection onto circle $A$ which lies on circle $B$ 's side of the radical axis of the two circles, and vice versa for gangster $B'$ , then $B'$ will shoot $A'$ or vice versa.
Proof: (outline) It clearly suffices to consider when the projections are the same point and hence on the radical axis by the hinge theorem or law of cosines; WLOG $A'$ is farther from $A$ than $B$ from $B'$ ; there exist two $B''$ on $BB'$ such that $AA'=BA''$ ; one lies past $B$ by assumption and so can be discounted; it suffices to show that the other lies farther from $B$ than $B'$ by the hinge theorem again (or loc again). But this easily follows from $AA'>BB'$ as well, so the lemma is proven.

Lemma: If two circles $A$ , $B$ intersect and contain each other's centers, then each cuts off at least a $2\pi/3$ degree arc from the other.
Proof: (outline) This implies the smaller circle's radius is at least half the larger one's and the distance is between the centers is less than the smaller circle's radius; draw the radical axis and find a lower bound on its length using Pythagorean theorem; use this to prove that the arc it cuts off from either circle is at least $2\pi/3$ .

From these, the result follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

201 posts

#7 h Oct 4, 2017, 6:12 PM • 2 Y

Y by Adventure10, Mango247

Who wrote this problem -____-

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

988 posts

test20

#8 h Oct 4, 2017, 6:16 PM • 3 Y

Y by vsathiam, Adventure10, Mango247

vsathiam wrote:

Who wrote this problem -____-

The problem was proposed by Iran.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#9 h Mar 10, 2018, 7:44 PM • 7 Y

Y by Anar24, GammaFunction, v4913, HamstPan38825, samrocksnature, Adventure10, Mango247

At least three gangsters are killed.

First assume for contradiction only two gangsters, say $a$ and $b$ , die. Then, those two gangsters must be the minimal distance across the $\binom{10}{2} = 45$ pairs. Assume they are a horizontal line segment $\overline{ab}$ with $a$ to the left of $b$ .

Suppose two gangsters $x$ and $x'$ both shoot $a$ , then we must have $\angle xax' > 60^{\circ}$ to ensure that side $xx'$ is strictly longest in that triangle. Similarly for $b$ .

Now partition the eight remaining gangsters based on whether they shoot $a$ or $b$ . Suppose that $a$ is shot by $b$ , $x_1$ , \dots, $x_k$ in counterclockwise order, and $b$ is shot by $a$ , $y_1$ , \dots, $y_{8-k}$ in counterclockwise order. The ``spokes'' we get are spaced at least $60^{\circ}$ apart, and so we find one of two cases: either rays $ax_1$ and $by_1$ meet, or rays $ax_k$ and $by_{8-k}$ meet. Assume WLOG we are in the first case and let $x=x_1$ , $y=y_1$ .

Thus $\angle xab + \angle yba < 180^{\circ}$ . On the other hand:

Since $ax$ is longer than $ab$ , we have $\angle axb < \angle xba$ .
Similarly, $\angle ayb < \angle yab$ .
Since $xy$ is longer than $xa$ , we have $\angle xya < \angle xay$
Similarly, $\angle yxb < \angle xby$ .

Summing gives $\angle a + \angle b > \angle x + \angle y$ , which is impossible.

Remark: Here is a sort of ``equality case'' with two deaths if one relaxes the distinct condition and allows gangsters to shoot any of the nearest neighbors, which motivates the earlier proof. All edges below have unit length.

$[asy] size(3cm); pair O = (0,0); pair A = dir(60); pair B = dir(-60); pair C = A+B; draw(O--A--C--(A+C)--(2*C)--(2*C+A)--(3*C)--cycle, grey); draw(O--B--C--(B+C)--(2*C)--(2*C+B)--(3*C), grey); draw(A--(A+2*C), grey); draw(B--(B+2*C), grey); dot(O); dot(A); dot(A+C); dot(A+2*C); dot(B); dot(B+C); dot(B+2*C); dot(3*C); dot(C, red); dot(2*C, red); [/asy]$

There are many constructions with three deaths, for example in the earlier post.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1600 posts

Vrangr

#12 h May 13, 2018, 2:27 PM • 1 Y

Y by Adventure10

This is my 1000th post, since my keyboard is partially busted right now. I'll post the complete solution later.
Hidden because of length

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30628 posts

#13 h Jun 14, 2021, 8:33 PM

Y by

the problem has an older source with 50 gangsters here

Kalva's (official ?) solution is mentioned here

This post has been edited 2 times. Last edited by parmenides51, Jun 14, 2021, 8:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#14 h Jul 7, 2022, 11:44 PM

Y by

Mom I Solved A G7. Now how do I write up this obnoxious problem?

The answer is 3. A construction is provided above.

Obviously the answer cannot be 0 or 1. To prove that the answer cannot be 2, suppose that gangsters 1,2 are killed. Then, everyone must fire at one of them; this means that gangsters 1,2 have the closest distance among all pairs.

Consider $l$ , the perpendicular bisector of gangsters 1,2; either there is one side of $l$ with six gangsters or each side has five gangsters.

In the former case, assume WLOG that gangster 1 is shot by 5 other gangsters (excluding gangster 2). Then, consider gangster 1 as the origin of a polar coordinate system. The range of possible arguments of those who shot gangster 1 is $(60^\circ,300^\circ)$ , meaning that two of them are less than 60 degrees apart, which forces another death.

Hence, both gangsters 1,2 are shot by 4 gangsters excluding themselves. Consider the perpendiculars $l_1,l_2$ to the segment connecting gangsters 1,2 at the locations of gangsters 1,2. Suppose they divide the plane into finite width region $R$ and infinite width regions $r_1,r_2$ . If any four gangsters are in $r_1$ or $r_2$ , then two of them are less than 60 degrees apart with respect to one of gangsters $1,2$ Hence, there must be at least two gangsters in $R$ .

Now, let the segment connecting gangsters 1,2 divide $R$ into $R_1,R_2$ . Then, it's easy to see by pythag that neither can contain two gangsters. Assume that gangsters 3,4 are in $R_1,R_2$ and shot gangsters 1,2, respectively. Use letters instead of numbers from this point onward, with gangster $1$ as A and so on.

Assume $\angle CAB\ge \angle DBA$ . Then, since no two gangsters are less than 60 degrees apart, the line $AC$ and its parallel through $B$ bounds another $A$ -aligned gangster $E$ on the same side of segment $AB$ as $D$ . We also arrive at $ED<EA$ in this case, which cannot happen.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1677 posts

awesomeming327.

#15 h May 18, 2023, 7:18 PM

Y by

Post #14 by mathleticguyyy

Mood.

At least three gangsters will be killed. Exactly three can be achieved by doing the following: let $A_1$ through $A_{10}$ be the locations of the gangsters. Construct almost equilateral triangle $A_1A_2A_3$ . Extend a ray of the angle bisector of $A_1$ going to the outside of the triangle, and two rays from $A_1$ that are just over sixty degrees apart from the angle bisector ray.

Pick points $A_4$ on the ray close to $A_2$ , $A_5$ on the angle bisector, and $A_6$ on the ray close to $A_3$ so that they are nearly equidistant from $A_1$ and just over the length of each side in $A_1A_2A_3$ . The sixty degree condition ensures that each of the gangsters at $A_4$ , $A_5$ , and $A_6$ shoot the one at $A_1$ .

Draw the same three rays from $A_2$ , but with just over thirty degrees of separation between the rays. Pick $A_7$ and $A_8$ on the rays closest to $A_1$ and $A_3$ , respectively, such that they are almost equidistant from $A_2$ and their distances is just over each side length of $A_1A_2A_3$ . Note that $\angle A_7A_2A_1$ is just under $120^\circ$ and $\angle A_4A_1A_2$ is just under $90^\circ$ , so $A_7$ and $A_8$ will both shoot $A_2$ .

Repeat on $A_3$ . Note that $\angle A_8A_2A_3$ and $\angle A_9A_3A_2$ are both just under $120^\circ$ so $A_8A_9$ is not too short of a distance. Furthermore, $A_1A_2A_3$ will shoot each other, so only $A_1$ , $A_2$ , and $A_3$ are shot.

Now, suppose only two gangsters are shot. Clearly, the gangsters at the ends of the shortest distance will shoot each other. WLOG let them be $A_1$ and $A_2$ . Let $A_i$ and $A_j$ be gangsters that will shoot $A_1$ then clearly $A_iA_j$ must be the longest length, so $\angle A_iA_1A_j>60^\circ$ .

Thus, if there are at least five gangsters that shoot $A_1$ , along with $A_2$ there will be an angle at most sixty degrees. Hence, there are four gangsters each that shoot $A_1$ . Let them be $A_3$ , $A_4$ , $A_5$ , $A_6$ shooting $A_1$ and $A_7$ , $A_8$ , $A_9$ , $A_{10}$ shooting $A_2$ , in that order, going clockwise.

Since each angle is at least sixty, $\angle A_3A_1A_2+\angle A_6A_1A_2 < 180^\circ\text{ and }\angle A_7A_2A_1+\angle A_{10}A_2A_1 < 180^\circ$ Thus, either $\angle A_3A_1A_2+\angle A_1A_2A_{10}$ or $\angle A_6A_1A_2+\angle A_7A_2A_1$ is less than $180^\circ$ , resulting in one of them being less than $A_1A_2$ , contradiction to $A_1A_2$ being shortest length.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a