Menu Close

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

Tinku Tara 0 Comments
Pin




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.
$$\mathrm{Let}\:{n}\:\mathrm{be}\:\mathrm{an}\:\mathrm{odd}\:\mathrm{positive}\:\mathrm{integer}.\:\mathrm{On} \\ $$$$\mathrm{some}\:\mathrm{field},\:{n}\:\mathrm{gunmen}\:\mathrm{are}\:\mathrm{placed}\:\mathrm{such} \\ $$$$\mathrm{that}\:\mathrm{all}\:\mathrm{pairwise}\:\mathrm{distances}\:\mathrm{between} \\ $$$$\mathrm{them}\:\mathrm{are}\:\mathrm{different}.\:\mathrm{At}\:\mathrm{a}\:\mathrm{signal},\:\mathrm{every} \\ $$$$\mathrm{gunman}\:\mathrm{takes}\:\mathrm{out}\:\mathrm{his}\:\mathrm{gun}\:\mathrm{and}\:\mathrm{shoots} \\ $$$$\mathrm{the}\:\mathrm{closest}\:\mathrm{gunman}.\:\mathrm{Prove}\:\mathrm{that}: \\ $$$$\left(\mathrm{a}\right)\:\mathrm{at}\:\mathrm{least}\:\mathrm{one}\:\mathrm{gunman}\:\mathrm{survives}; \\ $$$$\left(\mathrm{b}\right)\:\mathrm{no}\:\mathrm{gunman}\:\mathrm{is}\:\mathrm{shot}\:\mathrm{more}\:\mathrm{than}\:\mathrm{5} \\ $$$$\mathrm{times}; \\ $$$$\left(\mathrm{c}\right)\:\mathrm{the}\:\mathrm{trajectories}\:\mathrm{of}\:\mathrm{the}\:\mathrm{bullets}\:\mathrm{do} \\ $$$$\mathrm{not}\:\mathrm{intersect}. \\ $$
Commented by prakash jain last updated on 25/May/17
Part (a) Let gunmen be a_1 ,a_2 ,....,a_n and let us distances are a_(ij) . Since all distances are different there exist minimum a_(ij) 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≠i,k≠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. (pigeonhole principle) 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.
$$\mathrm{Part}\:\left({a}\right) \\ $$$$\mathrm{Let}\:\mathrm{gunmen}\:\mathrm{be}\:{a}_{\mathrm{1}} ,{a}_{\mathrm{2}} ,….,{a}_{{n}} \\ $$$$\mathrm{and}\:\mathrm{let}\:\mathrm{us}\:\mathrm{distances}\:\mathrm{are}\:{a}_{{ij}} . \\ $$$$\mathrm{Since}\:\mathrm{all}\:\mathrm{distances}\:\mathrm{are}\:\mathrm{different} \\ $$$$\mathrm{there}\:\mathrm{exist}\:\mathrm{minimum}\:{a}_{{ij}} \:\mathrm{for}\:\mathrm{some} \\ $$$$\mathrm{value}\:\mathrm{of}\:{i}\:\mathrm{and}\:{j}.\:\mathrm{Since}\:{a}_{{i}} \:\mathrm{will} \\ $$$$\mathrm{shoot}\:{a}_{{j}} \:\mathrm{and}\:{a}_{{j}} \:\mathrm{will}\:\mathrm{shoot}\:{a}_{{i}} . \\ $$$$\mathrm{Case}\:\mathrm{A}:\:{a}_{{k}} \left({k}\neq{i},{k}\neq{j}\right)\:\mathrm{fires}\:\mathrm{at} \\ $$$$\:\:\:\:\:\:\:\:{a}_{{i}} \:\mathrm{or}\:{a}_{{j}} . \\ $$$$\mathrm{In}\:\mathrm{this}\:\mathrm{case}\:{a}_{{i}} \:\mathrm{or}\:{a}_{{j}} \:\mathrm{get}\:\mathrm{shot}\:\mathrm{twice}. \\ $$$$\mathrm{Since}\:\mathrm{there}\:\mathrm{are}\:\mathrm{only}\:{n}\:\mathrm{bullets}\:\mathrm{and} \\ $$$$\mathrm{at}\:\mathrm{least}\:\mathrm{person}\:\mathrm{got}\:\mathrm{shot}\:\mathrm{twice}\:\mathrm{then} \\ $$$$\mathrm{there}\:\mathrm{will}\:\mathrm{be}\:\mathrm{one}\:\mathrm{person}\:\mathrm{who}\:\mathrm{does} \\ $$$$\mathrm{get}\:\mathrm{shot}\:\mathrm{at}\:\mathrm{all}.\:\left({pigeonhole}\:{principle}\right) \\ $$$$\mathrm{Case}\:\mathrm{B}:\:\mathrm{No}\:\mathrm{one}\:\mathrm{else}\:\mathrm{fires}\:\mathrm{at}\:{a}_{{i}} \:\mathrm{or}\:{a}_{{j}} \\ $$$$\mathrm{In}\:\mathrm{this}\:\mathrm{case}\:\mathrm{we}\:\mathrm{take}\:{a}_{{i}} \:\mathrm{and}\:{a}_{{j}} \:\mathrm{out}\:\mathrm{of}\:\mathrm{field} \\ $$$$\mathrm{and}\:\mathrm{consider}\:\mathrm{remaining}\:\left({n}−\mathrm{2}\right)\:\mathrm{gunmen}. \\ $$$$ \\ $$$$\mathrm{Continue}\:\mathrm{this}\:\mathrm{process}\:\mathrm{finally}\:\mathrm{there}\:\mathrm{will} \\ $$$$\mathrm{be}\:\mathrm{3}\:\mathrm{gunmen}\:\mathrm{left}\:\mathrm{where}\:\mathrm{only}\:\mathrm{case}\:\mathrm{A} \\ $$$$\mathrm{is}\:\mathrm{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 ,...,a_j_6 . consider hexagon formed by a_j_1 ...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 aa_j_2 >60° So six sides of hexagon spawn an angle >60×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 ∈{1,2,..6} than a_i is not shot 6 times.
$$\mathrm{Part}\:\left({b}\right)\:\mathrm{shot}<\mathrm{5}\:\mathrm{times}. \\ $$$$\mathrm{Consider}\:{a}_{{i}} \:\mathrm{is}\:\mathrm{shot}\:\mathrm{6}\:\mathrm{times} \\ $$$$\mathrm{by}\:{a}_{{j}_{\mathrm{1}} } ,…,{a}_{{j}_{\mathrm{6}} } . \\ $$$$\mathrm{consider}\:\mathrm{hexagon}\:\mathrm{formed}\:\mathrm{by} \\ $$$${a}_{{j}_{\mathrm{1}} } …{a}_{{j}_{\mathrm{6}} } .\: \\ $$$$\mathrm{A}:\:\mathrm{point}\:{a}_{{i}} \:\mathrm{is}\:\mathrm{inside}\:\mathrm{the}\:\mathrm{hexagom} \\ $$$$\mathrm{Make}\:\mathrm{a}\:\mathrm{traingle}\:\mathrm{with}\:{a}_{{i}} \:\mathrm{and}\:\mathrm{one} \\ $$$$\mathrm{side}\:\mathrm{of}\:\mathrm{hexagon}\:\mathrm{say}\:{a}_{{j}_{\mathrm{1}} } {a}_{{j}_{\mathrm{2}} .} \\ $$$${a}_{{j}_{\mathrm{1}} } {a}_{{i}} <{a}_{{j}_{\mathrm{1}} } {a}_{{j}_{\mathrm{2}} } \\ $$$${a}_{{j}_{\mathrm{2}} } {a}_{{i}} <{a}_{{j}_{\mathrm{1}} } {a}_{{j}_{\mathrm{2}} } \\ $$$${a}_{{j}_{\mathrm{1}} } {a}_{{j}_{\mathrm{2}} } \:\mathrm{is}\:\mathrm{largest}\:\mathrm{side}\:\mathrm{so}\:\angle{a}_{{j}_{\mathrm{1}} } {aa}_{{j}_{\mathrm{2}} } >\mathrm{60}° \\ $$$$\mathrm{So}\:\mathrm{six}\:\mathrm{sides}\:\mathrm{of}\:\mathrm{hexagon}\:\mathrm{spawn}\:\mathrm{an} \\ $$$$\mathrm{angle}\:>\mathrm{60}×\mathrm{6}=\mathrm{360}°\:\mathrm{not}\:\mathrm{possible}. \\ $$$$\mathrm{case}\:\mathrm{B}:\:{a}_{{i}} \:\mathrm{is}\:\mathrm{outside}\:\mathrm{the}\:\mathrm{hexagon}. \\ $$$$\mathrm{easy}\:\mathrm{to}\:\mathrm{prove}\:{a}_{{i}} {a}_{{j}_{{k}} } >{a}_{{j}_{{k}} } {a}_{{j}_{{l}} } \:\mathrm{for} \\ $$$$\mathrm{some}\:{k},{l}\:\in\left\{\mathrm{1},\mathrm{2},..\mathrm{6}\right\}\:\mathrm{than}\:{a}_{{i}} \:\mathrm{is}\:\mathrm{not} \\ $$$$\mathrm{shot}\:\mathrm{6}\:\mathrm{times}. \\ $$
Commented by prakash jain last updated on 25/May/17
Part (c) Let a_i shoot a_j and a_k shoots a_l . Let us say a_i a_j intersects with a_k a_l Let a_i shoot a_j and a_k shoots 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.
$$\mathrm{Part}\:\left({c}\right) \\ $$$$\mathrm{Let}\:{a}_{{i}} \:{shoot}\:{a}_{{j}} \:{and}\:{a}_{{k}} \:{shoots}\:{a}_{{l}} . \\ $$$$\mathrm{Let}\:\mathrm{us}\:\mathrm{say}\:{a}_{{i}} {a}_{{j}} \:\mathrm{intersects}\:\mathrm{with}\:{a}_{{k}} {a}_{{l}} \\ $$$$\mathrm{Let}\:{a}_{{i}} \:{shoot}\:{a}_{{j}} \:{and}\:{a}_{{k}} \:{shoots}\:{a}_{{l}} . \\ $$$$\mathrm{Consider}\:\mathrm{quadilateral}\:{a}_{{i}} {a}_{{k}} {a}_{{j}} {a}_{{l}} \\ $$$$\mathrm{so}\:{a}_{{i}} {a}_{{j}} \:\mathrm{and}\:{a}_{{k}} {a}_{{l}} \:\mathrm{are}\:\mathrm{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}} \\ $$$$\mathrm{Will}\:\mathrm{continue}\:\mathrm{to}\:\mathrm{prove}\:\mathrm{contradiction}. \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *