Problem C. 1855. (April 2025)

C. 1855. 19 drones flew over enemy territory following the security protocol requiring the distances of all pairs of drones being different. Since the drones were hacked, they start to fire at each other: each one eliminates the drone that is the nearest to them. (We suppose that each drone managed to fire, the drones can be considered points, and the drones only explode after all the shots reached their goals.) Will there be a survivor among the drones? What is the maximum number of bullets a drone can be hit by from the same plane (that also contains the given drone)?

Proposed by: Zoltán Paulovics, Budapest

(5 pont)

Deadline expired on May 12, 2025.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Biztosan lesz közöttük túlélő. Tekintsük a legkisebb páronkénti távolságot, mely vétessen fel \(\displaystyle X\) és \(\displaystyle Y\) drónok között (ezek tehát egymásra lőttek). Az első eset, ha érkezett rájuk további lövés. Ekkor a maradék 17 drón által leadott 17 lövedék közül legalább az egyik nem a 17 drón valamelyikét találta el, így közülük legfeljebb 16 semmisülhetett meg. A második eset, ha rájuk (\(\displaystyle X\)-re és \(\displaystyle Y\)-ra) nem lőtt más. Ekkor hagyjuk el őket, és alkalmazzuk a gondolatmenetünket kettővel kevesebb drónra. Ezt ismételve vagy találunk egy drónt, mely az egymásra lövők valamelyikét vette célba, s ekkor alkalmazhatjuk az első eset gondolatmenetét. Vagy eljutunk három drónig, melyek esetén nyilvánvaló, hogy lesz egy túlélő: az egymásra lövők valamelyikére fog lőni a harmadik, rá tehát nem nyitnak tüzet.

Megmutatjuk, hogy egy tetszőleges \(\displaystyle X\) drónra legfeljebb öt, azonos (őt is tartalmazó) síkban lévő másik drón lőhetett. Indirekt bizonyítunk, tegyük fel, hogy \(\displaystyle X\)-re tüzelt \(\displaystyle Y_1, Y_2, \ldots Y_5\) és \(\displaystyle Y_6\) is. \(\displaystyle X\) és \(\displaystyle Y_i\) távolságát \(\displaystyle XY_i\)-vel jelölve – a feltételek miatt – kapjuk, hogy \(\displaystyle XY_1 < Y_1Y_2\) (hiszen \(\displaystyle Y_1\) \(\displaystyle X\)-re tüzelt \(\displaystyle Y_2\) helyett) és hasonlóan \(\displaystyle XY_2 < Y_1Y_2\). Vizsgáljuk meg az \(\displaystyle XY_1Y_2\) háromszöget! Mivel egy háromszögben a legnagyobb (itt éppen \(\displaystyle Y_1Y_2\)) oldallal szemben található a legnagyobb szög, így \(\displaystyle Y_1XY_2 \sphericalangle > 60^{\circ}\). Ez bármely másik két \(\displaystyle X\)-et célbavevő drónra igaz, így tehát bármely \(\displaystyle i, j \in \{1;2;\ldots;6\}\) esetén \(\displaystyle Y_iXY_j \sphericalangle > 60^{\circ}\). Mivel \(\displaystyle X\) is a golyót lövő drónok síkjában található, így nyilvánvaló ellentmondásra jutottunk, hiszen az \(\displaystyle Y_i\)-k konvex burka által meghatározott sokszög belső \(\displaystyle X\) pontja körül több, mint \(\displaystyle 6 \cdot 60^{\circ} = 360^{\circ}\) összeget adó (egymást nem fedő) szögeket találtunk. Tehát legfeljebb öt drón lőhet ugyanarra a célpontra.

Öt pedig lőhet: könnyű példát mutatni rá. Vegyünk egy pontból kiinduló félegyeneseket, melyek \(\displaystyle 72^\circ\)-os szöget zárnak be, majd ezekre a közös pontból mérjünk fel közel azonos, de nem egyenlő hosszúságú szakaszokat. (Például a hosszok: \(\displaystyle 100+k\), ahol \(\displaystyle k=0,\pm 1,\pm2\).) Ekkor a keletkező háromszögekben a közös csúccsal szemközti oldalak lesznek a leghosszabbak (hiszen ez az oldal van a legnagyobb, \(\displaystyle 72^\circ\)-kal szemben), így tehát a félegyenesen felvett pontoknak megfeleltetett drónok mind a középsőre lőnek.

Statistics:

133 students sent a solution.
5 points:	Bencze Mátyás, Blaskovics Bálint, Bodó Rókus Dániel, Budai Máté, Farkas András, Fülöp Magdaléna, Halász Tamás, Hetyei Dániel, Iván Máté Domonkos, Kallós Klára, Lovas Márk, Maróti Olga, Miszori Márton, Molnár Lili, Molnár-Sáska Tamás, Pázmándi Renáta , Tóth Luca.
4 points:	Aaishipragya Kahaly, Albert Luca Liliána, Bara Boglárka , Bense Tamás, Kámán-Gausz Péter, Kérdő Vilmos, Kókai Ákos, Móricz Zsombor, Nelissen Sámuel Zalán, Pánovics Máté, Poczai Dorottya, Rózsa Zsombor.
3 points:	10 students.
2 points:	20 students.
1 point:	19 students.
0 point:	30 students.
Not shown because of missing birth date or parental permission:	16 solutions.

Problems in Mathematics of KöMaL, April 2025