Szerk
C. 1844 Ági pirossal, Laci kékkel színezgeti egy \(\displaystyle n \times n\)-es (\(\displaystyle n>1\)) fehér táblázat mezőit, amely \(\displaystyle i\)-edik sorának \(\displaystyle j\)-edik mezőjét \(\displaystyle (i;j)\)-vel jelöljük. Első lépésben Ági pirosra festi a főátló (bal felsőtől a jobb alsóig) mezőit. Ezután felváltva jönnek: ha Laci \(\displaystyle (i;j)\)-t színezi, akkor Ági \(\displaystyle (j;i)\)-t. Minden mezőt pontosan egyszer színeznek be. A \(\displaystyle k\)-adik sort különlegesnek hívjuk, ha bármely kék \(\displaystyle (k;j)\) esetén létezik \(\displaystyle l\), hogy \(\displaystyle (k;l)\) és \(\displaystyle (l;j)\) is piros. Bizonyítsuk be, hogy a színezgetés végeztével Ági talál különleges sort.
Javasolta: Paulovics Zoltán (Budapest)
1. megoldás. Tegyük fel, hogy nem talál. Válasszunk ki egy olyan sort, amelyben maximális számú piros van. Ez a sor legyen a \(\displaystyle k\)-adik, és legyen benne \(\displaystyle m\) darab piros négyzet.
Mindenképpen lesz legalább egy olyan kék \(\displaystyle (k;j)\) mező, amihez nem talál megfelelő \(\displaystyle l\)-et, különben a sor különleges lenne.
A \(\displaystyle k\)-adik sorból válasszunk egy ilyen kék \(\displaystyle (k;j)\)-t. Ekkor nézzük meg az összes \(\displaystyle l\)-re, hogy \(\displaystyle (k;l)\) piros-e. Összesen \(\displaystyle m\) darab olyan \(\displaystyle l\) van, amelyre piros. Ekkor, mivel nincs megfelelő \(\displaystyle l\), ezért mind az \(\displaystyle m\) darab \(\displaystyle (l;j)\) kék lesz.
Viszont mivel minden \(\displaystyle (l;j)\) kék, ezért minden \(\displaystyle (j;l)\) piros (\(\displaystyle m\) darab) a színezési szabály szerint. Valamint \(\displaystyle (j;k)\) is biztosan piros, mivel \(\displaystyle (k;j)\) kék. Tehát a \(\displaystyle j\)-edik sorban legalább \(\displaystyle m+1\) darab piros négyzet van, ami ellentmond annak, hogy a \(\displaystyle k\)-adikban maximális számú \(\displaystyle m\) van.
Bodó Rókus Dániel (Szegedi Radnóti M. Kísérleti Gimn., 8. o. t.) dolgozata alapján
2. megoldás. Képzeljük el ezt a táblázatot úgy, mintha egy focibajnokság táblázatát látnánk. Ekkor ha az \(\displaystyle (i, j)\)-edik piros, akkor az \(\displaystyle i\)-edik csapat megverte a \(\displaystyle j\)-edik csapatot, ha pedig kék, akkor meg a \(\displaystyle j\)-edik csapat verte meg az \(\displaystyle i\)-edik csapatot. (Tegyük fel, hogy nem születhet döntetlen, továbbá a piros \(\displaystyle (i;i)\) mezők jelentésével ne foglalkozzunk.) Ekkor igazából az a kérdés, hogy ha \(\displaystyle n\) csapat van, akkor biztosan van-e olyan csapat, amelyik minden csapatot vagy megvert, vagy legyőzött egy olyan csapatot, amelyik legyőzte azt a csapatot, amelyik legyőzte őt. Hiszen, ha egy különleges sor valamely (például a \(\displaystyle j\)-edik) eleme kék (tehát valakitől kikapott), de létezik egy olyan eleme (például az \(\displaystyle l\)-edik), amely piros – azaz az \(\displaystyle l\)-edik csapatot legyőzte –, és ráadásul \(\displaystyle (l;j)\) is piros – azaz az \(\displaystyle l\)-edik csapat legyőzte a \(\displaystyle j\)-edik csapatot –, akkor a különleges sorunkra valóban teljesül, hogy az őt legyőző csapat egyik legyőzőjét legyőzte.
Jelöljön \(\displaystyle X\) egy olyan csapatot, amelyik a legtöbbször győzött, bebizonyítjuk, hogy \(\displaystyle X\) teljesíti ezeket a feltételeket, vagyis \(\displaystyle X\) sora különleges.
Most vizsgáljuk azokat a csapatokat, amelyek legyőzték \(\displaystyle X\)-et. Ha \(\displaystyle X\) nem teljesíti a feltételeket, akkor valamelyik csapat, amelyik megverte \(\displaystyle X\)-et biztos, hogy megvert minden olyan csapatot is, amit \(\displaystyle X\) megvert, így ekkor ez a csapat többet nyert volna, mint \(\displaystyle X\), tehát ez ellentmondás. Tehát mindig lesz ilyen csapat. Így egy olyan sort kell kiválasztania Áginak, ahol maximális számú piros mező van. Így beláttuk, hogy a színezgetés végeztével Ági talál különleges sort.
Molnár-Sáska Tamás (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 7. o. t.) dolgozata alapján
3. megoldás. Teljes indukcióval bizonyítjuk az állítást. Az állítás \(\displaystyle n=2\), 3-ra igaz, ez könnyen ellenőrizhető.
Tegyük fel, hogy igaz az állítás (azaz létezik különleges sor) \(\displaystyle n\)-re. Ekkor bebizonyítjuk, hogy igaz \(\displaystyle (n+1)\)-re is.
Tekintsünk tehát egy tetszőleges \(\displaystyle (n+1) \times (n+1)\)-es, a feladat szerint kiszínezett táblázatot, és vizsgáljuk annak első \(\displaystyle n\) sorából és oszlopából képzett \(\displaystyle n \times n\)-es résztáblázatát.
Az indukciós feltétel miatt ennek a résztáblázatnak van különleges sora, legyen ez a \(\displaystyle p\)-edik sor. Ha a \(\displaystyle p\)-edik sor a teljes táblázatban is különleges, akkor készen vagyunk. Ha nem az, akkor van olyan kék \(\displaystyle (p;j)\) mezője a sornak, amelyre bármely \(\displaystyle l\) esetén a \(\displaystyle (p;l)\) vagy az \(\displaystyle (l;j)\) kék. Melyik szám lehet a \(\displaystyle j\)?
Mivel a résztáblázatban ez a sor különleges volt, ezért minden \(\displaystyle 1 \leq j \leq n\) számra, ha \(\displaystyle (p;j)\) kék, úgy a teljes, \(\displaystyle (n+1) \times (n+1)\)-es táblázatunkban is megfelelő lesz ugyanaz az \(\displaystyle l\), amelyre teljesült, hogy \(\displaystyle (p;l)\) és \(\displaystyle (l;j)\) piros. Tehát \(\displaystyle j=n+1\).
Ha tehát \(\displaystyle j=n+1\) „rontotta el” a \(\displaystyle p\)-edik sort, akkor az \(\displaystyle (n+1)\)-edik sor olyan, hogy \(\displaystyle (p;n+1)\) kék (így \(\displaystyle (n+1;p)\) piros), továbbá bármely \(\displaystyle l\)-re, ha \(\displaystyle (p,l)\) piros, úgy \(\displaystyle (l;n+1)\) kék. Ám ha \(\displaystyle (l;n+1)\) kék, akkor \(\displaystyle (n+1;l)\) piros. Tehát arra jutottunk, hogy az \(\displaystyle (n+1)\)-edik sorban minden olyan mező piros, amely a \(\displaystyle p\)-edik sorban is piros. Ekkor könnyű ellenőrizni a különlegesség feltételét az \(\displaystyle (n+1)\)-edik sorra – mivel \(\displaystyle (n+1;n+1)\) piros, ezért elég a sor \(\displaystyle 1 \leq j \leq n\) mezőire. Ha ugyanis a \(\displaystyle j\)-edik mezője kék, akkor \(\displaystyle (p;j)\) is kék, így – a \(\displaystyle p\)-edik sor résztáblázatban való különlegessége miatt – létezik olyan \(\displaystyle l\), amelyre \(\displaystyle (p;l)\) és \(\displaystyle (l;j)\) is piros, de ekkor \(\displaystyle (n+1;l)\) és \(\displaystyle (l;j)\) is piros. Ezzel beláttuk, hogy amennyiben a \(\displaystyle p\)-edik sor nem különleges a teljes táblázatban, úgy az \(\displaystyle (n+1)\)-edik sor az.
Bencze Mátyás (Székelyudvarhely, Tamási Á. Gimn., 12. o. t.) ötlete alapján
A feladatra összesen 71 versenyző és csapat küldött megoldást. 5 pontos 10, 4 pontos 3, 3 pontos 5, 1 pontos 50 dolgozat.
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.
C. 1842. Oldjuk meg a valós számok halmazán a \(\displaystyle 9^x+(6x-23)\cdot 3^x+5x^2-39x+76=0\) egyenletet.
Javasolta: Bencze Mihály (Brassó
Nem kell túl sokáig keresgélnünk az interneten a fejtörő feladatok között ahhoz, hogy sík vagy tér kitöltésére vonatkozó feladványra bukkanjunk. Ezek egyik fajtája az, amikor néhány síkidom vagy test valamilyen keretben van elhelyezve úgy, hogy látszólag teljesen kitöltik azt, de van még külön egy további eleme a játéknak.
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)
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.
