Question and Answers Forum

All Questions      Topic List

Logic Questions

Previous in All Question      Next in All Question      

Previous in Logic      Next in Logic      

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}. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com