A C. 1855. matematika gyakorlat megoldása

Szerk

C. 1855. Egy \(\displaystyle 19\) drónból álló csapat repül egy gyakorlótér felett, a biztonsági előírásoknak megfelelően olyan rögzített alakzatban, ahol bármely két gépnek különböző a távolsága. Egy hackertámadás következtében a drónok egymásra nyitnak tüzet: mindegyik drón lő egyet a hozzá legközelebbi drónra, és ezzel megsemmisíti azt. (Feltételezzük, hogy minden drón tudott lőni, a drónok pontszerűnek tekinthetők, továbbá hogy a drónok csak azután semmisülnek meg, miután minden golyó becsapódott.)

Van-e köztük túlélő drón?

Egy drónt legfeljebb hány azonos (őt is tartalmazó) síkból származó lövedék találhatott el?

Javasolta: Paulovics Zoltán (Budapest)

Megoldás. Először arra a kérdésre adunk választ, hogy van-e köztük túlélő. Ráadásul kétféle módon.

1. módszer. Az alábbiakban bebizonyítjuk, hogy a drónok között mindig van legalább egy túlélő. Indirekt bizonyítunk, ehhez feltételezzük, hogy nincsen túlélő drón.

Mivel bármelyik két gépnek különböző a távolsága, egyértelműen beazonosítható az a drónpáros, amelyek távolsága a legkisebb. Jelöljük ezt a két drónt \(\displaystyle A\)-val és \(\displaystyle B\)-vel. Ezek alapján az \(\displaystyle A\)-hoz legközelebbi drón \(\displaystyle B\) és a \(\displaystyle B\)-hez legközelebbi drón \(\displaystyle A\), azaz egymást kölcsönösen lelövik. Ezen kívül még 17 drón marad, amelyek összesen 17 lövést adnak le. Ezek közül egyik sem találhatja el \(\displaystyle A\)-t vagy \(\displaystyle B\)-t, hiszen ebben az esetben kevesebb mint 17 lövés irányulna a maradék 17 drónra, azaz lenne köztük túlélő. Így a megsemmisített \(\displaystyle A\) és \(\displaystyle B\) drónok a maradéktól függetlenek, nem köti őket össze lövés, tehát ez a drónpáros figyelmen kívül hagyható.

Ezt a gondolatmenetet elismételhetjük 17-re, illetve \(\displaystyle C\) és \(\displaystyle D\) legkisebb távolságra lévő drónokra. És így tovább...

Látható, hogy itt egy lépésben mindig egy drónpáros, azaz két drón távolítható el a csapatból, azaz mindig csak a maradék 17, 15, 13, 11, 9, 7, 5, 3, 1 drónt kell figyelembe vennünk. Így a végén marad 1 drón, amelyre még nem lőtt semmi, így túléli a támadást. Ez ellentmond annak a feltevésnek, hogy nincs túlélő drón, így beláttuk, hogy van legalább egy túlélő drón.

Fülöp Magdaléna Hasian (Pécs, Pécsi Leőwey K. Gimn., 10. o. t.) dolgozata alapján

2. módszer. Teljes indukcióval általános esetben adunk választ a kérdésre, azaz megmutatjuk, hogy \(\displaystyle 2n+1\) darab drón esetén lesz túlélő.

\(\displaystyle n=1\) esetén nyilvánvaló, hogy lesz túlélőnk, hiszen „körbelövés” nem lehetséges, mert ha az \(\displaystyle X\) drónhoz \(\displaystyle Y\) van a legközelebb, \(\displaystyle Y\)-hoz \(\displaystyle Z\), \(\displaystyle Z\)-hez pedig \(\displaystyle X\), úgy \(\displaystyle X\) és \(\displaystyle Y\) távolságánál kisebb \(\displaystyle Y\) és \(\displaystyle Z\) távolsága, amelynél kisebb \(\displaystyle Z\) és \(\displaystyle X\) távolsága, ami ellentmondásra vezet: \(\displaystyle X\)-nek nem \(\displaystyle Y\)-ra, hanem \(\displaystyle Z\)-re kellett volna céloznia.

Tegyük fel, hogy igaz az állítás \(\displaystyle n\)-re, megmutatjuk, hogy \(\displaystyle (n+1)\)-re is teljesülni fog.

Vezessünk be egy irányított gráfot: a pontjai a drónok legyenek, és fusson az \(\displaystyle u\) csúcsból irányított él a \(\displaystyle v\) csúcsba, ha az \(\displaystyle u\)-nak megfeleltetett drón rálőtt a \(\displaystyle v\)-nek megfeleltetett drónra. Továbbá írjuk az élekre a csúcsoknak megfeleltetett drónok távolságait, amelyet egy \(\displaystyle (u;v)\) él esetén jelöljön \(\displaystyle d(u;v)\).

Válasszuk ki a gráfunk egy tetszőleges csúcsát, és a belőle induló irányított élen lépjünk át egy másik csúcsba. Folytassuk a lépkedést egészen addig, amíg egy olyan csúcsba nem jutunk, ahol már jártunk. Ez bizonyosan bekövetkezik, hiszen minden csúcsból tovább tudunk lépni (ugyanis minden csúcsból indul ki irányított él), így legfeljebb \(\displaystyle 2(n+1)+1\) lépést követően elakadunk. Ekkor egy irányított kört találtunk, amelynek csúcsait rendre jelölje: \(\displaystyle v_1\), \(\displaystyle v_2\), \(\displaystyle \ldots\), \(\displaystyle v_k\), és az utolsó lépésünk \(\displaystyle v_k\)-ból \(\displaystyle v_1\)-be vezetett (ahol \(\displaystyle {k>1}\) pozitív egész). Először vizsgáljuk azt az esetet, amikor \(\displaystyle {k\geq3}\). Mivel minden drón a hozzá legközelebbi drónra lőtt, így a kör mentén vizsgálva a távolságokat azt kapjuk, hogy: \(\displaystyle d(v_1;v_2) > d(v_2;v_3) > \ldots > d(v_k;v_1)\). Ami viszont azt jelenti, hogy a \(\displaystyle v_1\)-gyel jelölt drónhoz közelebb van a \(\displaystyle v_k\)-val jelölt drón, mint a \(\displaystyle v_2\)-vel jelölt, és mégis a távolabbira nyitott tüzet. Ez ellentmond a feladat feltételeinek, így arra jutottunk, hogy \(\displaystyle k<3\), tehát \(\displaystyle k=2\).

A \(\displaystyle k=2\) jelentése az, hogy van két drón (a \(\displaystyle v_1\)-gyel és \(\displaystyle v_2\)-vel jelölt), amelyek egymásra tüzeltek. Ha a gráfunk többi csúcsából irányított úton nem érhető el sem \(\displaystyle v_1\), sem \(\displaystyle v_2\), úgy ezeket elhagyva egy, a feltételeknek megfelelő, \(\displaystyle 2n+1\) csúcsú gráfot kapunk, amelyre az indukciós feltétel miatt teljesül az állítás: létezik túlélő. Ekkor persze a \(\displaystyle 2n+3\) csúcsú gráfnak megfeleltetett dróncsapatban is ugyanaz a drón túlél.

Amennyiben valamely másik csúcsból vezet irányított út \(\displaystyle v_1\)-be vagy \(\displaystyle v_2\)-be, úgy a többi \(\displaystyle 2n+1\) csúcs között futó (azaz az általuk feszített) élek száma kevesebb, mint \(\displaystyle 2n+1\). Ez pedig azt jelenti, hogy nem mutathat minden csúcsba él, tehát lesz túlélő drón.

Kallós Klára (Nyíregyháza, Szent Imre Kat. Gimn., Két Tan. Nyelvű Ált. Isk., Koll., 7. o. t.),

Hetyei Dániel (Győr, Révai M. Gimn., 11. o. t) és

Lovas Márk (Pécs, Pécsi Janus Pannonius Gimn., 9. o. t.) dolgozata alapján

Válasz a feladat második részére: Egy drónt legfeljebb hány azonos (őt is tartalmazó) síkból származó lövedék találhatott el?

Ha egy drónt \(\displaystyle n\) másik drón eltalálhatott, akkor \(\displaystyle n\)-nél kevesebb is eltalálhatta, ha pedig \(\displaystyle n\) drón már nem találhatta el, akkor \(\displaystyle n\)-nél több sem. Tegyük fel, hogy létezik olyan drón, amelyet 6 lövedék talált el, és nevezzük el \(\displaystyle D\)-nek. Tekintsük a \(\displaystyle D\)-ből és a rá lövőkből álló drónhetest. Ekkor ha minden szög \(\displaystyle 60^{\circ}\)-os a \(\displaystyle D\) körül, úgy – mivel egyik hármas sem feszíthet szabályos háromszöget – \(\displaystyle D\) és valamely másik két (\(\displaystyle D\)-re lövő) drón által alkotott háromszögben az egyik szög biztosan nagyobb lesz, mint \(\displaystyle 60^{\circ}\). Ismert, hogy egy háromszögben nagyobb szöggel szemben nagyobb oldal van, tehát az egyik drón a 6 közül nem \(\displaystyle D\)-t fogja lőni, hanem azt, amelyik közelebb van hozzá, ami ellentmondás. Ha pedig nem mindegyik szög \(\displaystyle 60^{\circ}\)-os, akkor van egy kevesebb mint \(\displaystyle 60^{\circ}\)-os, de ekkor – az előzőekhez hasonlóan – megint arra jutunk, hogy az egyik \(\displaystyle D\)-re lövő drónhoz nem is \(\displaystyle D\) áll a legközelebb. Így \(\displaystyle n\leq 5\). Az ábra mutatja, hogy az \(\displaystyle {n=5}\) eset megvalósítható. (Az ábrán nem látható drónok nagyon messze vannak az ábrázolt pontoktól.)

Molnár-Sáska Tamás (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 7. o. t) és

emphBodó Rókus Dániel (Szegedi Radnóti M. Kís. Gimn., 8. o. t.) dolgozata alapján

A feladatra összesen 133 dolgozat érkezett. 5 pontos 19, 4 pontos 12, 3 pontos 15, 2 pontos 24, 1 pontos 24. 0 pontot 39 beküldő kapott.