Szerk
C. 1865. Az iskolai szkanderbajnokságon \(\displaystyle 17\) fő indult el. Mindenki pontosan egyszer mérkőzött meg mindenkivel, döntetlen nem született. A versenyzők egy csoportját erősnek hívjuk, ha teljesül rájuk, hogy bármely rajtuk kívüli versenyzőt legyőzött közülük valaki. Bizonyítsuk be, hogy kiválasztható legfeljebb \(\displaystyle 9\) fős erős csoport.
Javasolta: Paulovics Zoltán (Budapest)
1. megoldás. Osszuk a 17 versenyzőt tetszőlegesen 8 párra, ekkor marad egy „páratlan” játékos. Minden párból válasszuk a győztest; legyen az \(\displaystyle S\) halmaz az így kapott 8 győztes, plusz még a páratlan játékos. Tehát \(\displaystyle \lvert S \rvert=9\).
Ekkor minden, \(\displaystyle S\)-en kívüli játékos valamely pár vesztese, tehát legyőzi őt a párjának \(\displaystyle S\)-be vett győztese. Következésképpen az \(\displaystyle S\)-en kívül álló minden játékost megveri valaki \(\displaystyle S\)-ből, azaz \(\displaystyle S\) erős csoport.
Yan Zhebeier (Miskolci Herman Ottó Gimn., 11. o. t.) dolgozata alapján
2. megoldás. A 17 főből kiválasztjuk bármely 9-et. Ha ez egy erős csoport, akkor kész vagyunk.
Ha ez nem erős, akkor az azt jelenti, hogy a maradék 8 emberből van valaki, aki mind a 9-üket legyőzte.
Ekkor kiválasztjuk a másik – tehát a kezdetben nem választott – 8 embert, ők mindenképpen erősek lesznek, mert köztük van egy olyan ember aki a másik 9 emberből mindenkit legyőzött.
Bodó Rókus Dániel (Szegedi Radnóti M. Kísérleti Gimn., 9. o. t.) dolgozata alapján
3. megoldás. Az összes meccs száma: \(\displaystyle \frac{17 \cdot 16}{2}\). Mivel minden meccset megnyerte az egyik résztvevő, így a nyert meccsek átlagos száma \(\displaystyle \dfrac{\frac{17\cdot 16}{2}}{17}=8\), tehát biztosan van olyan ember, aki legalább 8 meccset nyert.
Ekkor megalkotható az erős csapat úgy, hogy annak tagja ő (az egyik legalább 8 meccset nyert diák), és még azon legfeljebb 8 ember, akiket nem győzött le. Az elsőnek kiválasztott diák ugyanis minden csoporton kívüli diákot legyőzött, ezért a kiválasztottak erős csoportot alkotnak. Tehát az állítás igaz: mindig van legfeljebb 9 fős erős csoport.
Rákóczi Bartos (Szegedi Radnóti M. Kísérleti Gimn., 9. o. t.) és Kallós Klára (Nyíregyháza, Szent Imre Kat. Gimn., Két Tan. Nyelvű Ált. Isk., Koll., 8. o. t.) dolgozata alapján
4. Megoldás. A 17 játékost tekintsük egy \(\displaystyle G\) gráf csúcsainak. Ha \(\displaystyle A\) legyőzi \(\displaystyle B\)-t, akkor rajzoljunk irányított élt \(\displaystyle A\)-ból \(\displaystyle B\) felé. Így egy 17 csúcsú irányított teljes gráfot kapunk.
Tekintsük a csúcsok egy \(\displaystyle K\) részhalmazát. \(\displaystyle G\) egy csúcsát \(\displaystyle K\) által lefedettnek fogunk nevezni, ha olyan él végpontja, amelynek kezdőpontja \(\displaystyle K\)-ban van.
Készítsük el a csúcsok egy \(\displaystyle E\) halmazát a következő módon:
Mivel egy \(\displaystyle n\)-csúcsú gráfban az összes (kimenő) él száma
\(\displaystyle \binom{n}{2}=\frac{n(n-1)}{2}, \)
ezért van legalább egy olyan csúcs, amelynek kimenő foka legalább \(\displaystyle \frac{n-1}{2}\). (És így legalább 8.) Válasszunk ki egy ilyen csúcsot, nevezzük el \(\displaystyle v_1\)-nek és „tegyük bele” az \(\displaystyle E\) halmazba. (Egyelőre ez a halmaz egyetlen eleme.) Jelölje \(\displaystyle m\) azon csúcsok számát, amelyeket \(\displaystyle E\) nem fed le, vagyis \(\displaystyle v_1\) nem győzött le. Nyilván \(\displaystyle m\leq8\). Ha \(\displaystyle m=0\), akkor készen vagyunk, \(\displaystyle E\) egy (egyfős) erős csoport. Ha \(\displaystyle m>0\), akkor tekintsük az \(\displaystyle E\) által le nem fedett csúcsokat a közöttük levő élekkel. Ez is egy irányított teljes gráf, így itt van olyan csúcs, amelynek itteni foka legalább \(\displaystyle (m-1)/2\). Egy ilyen \(\displaystyle v_2\) csúcsot is tegyünk bele \(\displaystyle E\)-be.
Ismételjük meg az eljárást a maradék csúcsokon. 17 csúcs esetén \(\displaystyle m\) az egyes lépések után legfeljebb 8, 3, 1, majd 0 lesz.
Tehát legfeljebb 4 lépés szükséges, hogy minden csúcsot lefedjünk.
Az így kiválasztott csúcsok \(\displaystyle E\) halmaza erős csoportot határoz meg, a mérete 4, tehát biztosan van legfeljebb 9 fős erős csoport.
Pap Lola (Budapest, Madách I. Gimn., 11. o. t.) dolgozata alapján
A feladatra összesen 155 versenyző és csapat küldött megoldást. 5 pontos 99, 4 pontos 5, 3 pontos 6, 2 pontos 4, 1 pontos 17.
B. 5472. Az \(\displaystyle ABCD\) konvex négyszögben \(\displaystyle AB=BC=CD\). Igazoljuk, hogy ha \(\displaystyle BCD\sphericalangle=2DAB\sphericalangle\), akkor \(\displaystyle ABC\sphericalangle=2CDA\sphericalangle\).
Javasolta: Kós Géza (Budapest) és Vígh Viktor (Sándorfalva)
A KöMaL 2025 szeptemberi számában (Tait tétele és a 3-reguláris gráfok – a B. 5403. feladat háttere) kimondtuk Tait alábbi tételét.
Tétel (Tait tétele). Legyen \(\displaystyle G\) egy 3-reguláris, hídélmentes, síkbarajzolt gráf. Ekkor \(\displaystyle G\) tartományai \(\displaystyle 4\)-színezhetők akkor és csak akkor, ha élei \(\displaystyle 3\)-színezhetők.
A tételben \(\displaystyle k\)-színezésen olyan színezést értünk, amely \(\displaystyle k\)-féle színt használ, és az egymással szomszédos tartományok (illetve élszínezés esetén az egy csúcsban találkozó élek) mindig különböző színűek.
A szeptemberi számba nem került be a tétel bizonyítása (azzal a céllal, hogy akinek van kedve, gondolkodhasson rajta), ezt most pótoljuk.
A KöMaL egy példányának ára 2025. szeptembertől 1600 Ft, előfizetése 1 évre 12500 Ft – BJMT tagoknak 12000 Ft.
Megrendelem
B. 5489. Az \(\displaystyle ABC\) derékszögű háromszögben \(\displaystyle ABC\sphericalangle=15^\circ\) és \(\displaystyle CAB\sphericalangle=75^\circ\), továbbá az \(\displaystyle AB\) átfogó felezőpontja \(\displaystyle F\). A \(\displaystyle BC\) befogón vegyük fel a \(\displaystyle D\) pontot úgy, hogy \(\displaystyle BD=CA\), a \(\displaystyle CA\) félegyenesen az \(\displaystyle A\) ponton túl az \(\displaystyle E\) pontot úgy, hogy \(\displaystyle CE=BC\) teljesüljön. A \(\displaystyle BE\) és \(\displaystyle CF\) egyenesek metszéspontja legyen \(\displaystyle M\). Bizonyítsuk be, hogy a \(\displaystyle DM\) és \(\displaystyle CM\) egyenesek érintik az \(\displaystyle AEF\) háromszög köré írt kört.
Javasolta: Bíró Bálint (Eger)
Legutóbb szeptemberi számunkban foglalkoztunk bújócska típusú ördöglakatokkal. Elkészítésre ajánlottunk olvasóinknak egy pálcás változatot, ahol a ,,szokásos'' trükk nem működik, mivel az átbújtatás után (lásd ábra) a pálca nem fér át a hurkon a zsinór rövidsége miatt. Azonban vegyük észre, hogy ebben az átbújtatott állapotban valójában annyi a célunk, hogy a hurok a dupla zsinór másik oldalára kerüljön. Ezt úgy is elérhetjük, ha a téglatest formájú ,,alapot'' bújtatjuk át a hurkon.
A KöMaL kiadásának, a versenyek teljes lebonyolításának, díjazásának és a díjkiosztóval egybekötött Ifjúsági Ankétok szervezésének költségeit 2007 óta a MATFUND Középiskolai Matematikai és Fizikai Alapítvány fizeti.
Kérjük, személyi jövedelemadója 1%-ának felajánlásával álljon a több, mint 125 éve alapított Középiskolai Matematikai és Fizikai Lapok mellé!
