Let-n-be-an-odd-positive-integer-On-some-field-n-gunmen-are-placed-such-that-all-pairwise-distances-between-them-are-different-At-a-signal-every-gunman-takes-out-his-gun-and-shoots-the-closest-gun

Question Number 13893 by Tinkutara last updated on 24/May/17

Let n be an odd positive integer . On

some field, n gunmen are placed such

that all pairwise distances between

them are different . At a signal, every

gunman takes out his gun and shoots

the closest gunman . Prove that :

(a) at least one gunman survives;

(b) no gunman is shot more than 5

times;

(c) the trajectories of the bullets do

not intersect .

Commented by prakash jain last updated on 25/May/17

Part (a)

Let gunmen be a_{1}, a_{2}, \dots ., a_{n}

and let us distances are a_{i j} .

Since all distances are different

there exist minimum a_{i j} for some

value of i and j . Since a_{i} will

shoot a_{j} and a_{j} will shoot a_{i} .

Case A : a_{k} (k \neq i, k \neq j) fires at

a_{i} or a_{j} .

In this case a_{i} or a_{j} get shot twice .

Since there are only n bullets and

at least person got shot twice then

there will be one person who does

get shot at all . (p i g e o n h o l e p r i n c i p l e)

Case B : No one else fires at a_{i} or a_{j}

In this case we take a_{i} and a_{j} out of field

and consider remaining (n - 2) gunmen .

Continue this process finally there will

be 3 gunmen left where only case A

is possible .

Commented by prakash jain last updated on 25/May/17

Part (b) shot < 5 times .

Consider a_{i} is shot 6 times

by a_{j_{1}}, \dots, a_{j_{6}} .

consider hexagon formed by

a_{j_{1}} \dots a_{j_{6}} .

A : point a_{i} is inside the hexagom

Make a traingle with a_{i} and one

side of hexagon say a_{j_{1}} a_{j_{2} .}

a_{j_{1}} a_{i} < a_{j_{1}} a_{j_{2}}

a_{j_{2}} a_{i} < a_{j_{1}} a_{j_{2}}

a_{j_{1}} a_{j_{2}} is largest side so ∠ a_{j_{1}} {a a}_{j_{2}} > 60 °

So six sides of hexagon spawn an

angle > 60 \times 6 = 360 ° not possible .

case B : a_{i} is outside the hexagon .

easy to prove a_{i} a_{j_{k}} > a_{j_{k}} a_{j_{l}} for

some k, l \in {1, 2, . . 6} than a_{i} is not

shot 6 times .

Commented by prakash jain last updated on 25/May/17

Part (c)

Let a_{i} s h o o t a_{j} a n d a_{k} s h o o t s a_{l} .

Let us say a_{i} a_{j} intersects with a_{k} a_{l}

Let a_{i} s h o o t a_{j} a n d a_{k} s h o o t s a_{l} .

Consider quadilateral a_{i} a_{k} a_{j} a_{l}

so a_{i} a_{j} and a_{k} a_{l} are diagonals .

a_{i} a_{k} > a_{i} a_{j}

a_{i} a_{l} > a_{i} a_{j}

a_{k} a_{i} > a_{k} a_{l}

a_{k} a_{j} > a_{k} a_{l}

Will continue to prove contradiction .