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 levelezős versenyei azon kevesek közé tartoznak, amelyek ingyenesek – immár több mint 130 éve! Sajnos azonban a KöMaL állami támogatásának rendszere az elmúlt évben jelentősen átalakult, a következő években az előre látható bevételeink várhatóan nem tudják fedezni a költségeinket.
Ezért kérünk mindenkit, aki szereti a KöMaL-t, létezését fontosnak tartja, hogy lehetőségéhez mérten támogassa a KöMaL-t kiadó MATFUND Alapítványt. Ha teheti, rendelkezzen adója 1%-áról az Alapítvány javára. Ezen kívül pedig, ha saját vagy céges lehetőségei megengedik, támogassa a KöMaL kiadását, a KöMaL tudáskincsének gondozását!
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é!
Ha egy négyzetet a két átlójával felosztunk négy háromszögre, majd ezeket kiszínezzük három színnel az összes lehetséges módon, akkor megkapjuk a négyzetes színdominókat.
A színdominókat először a múlt század elején írta le Percy Alexander MacMahon, a kalandos életű matematikus. Ő rögtön megadott több nehéz feladatot is hozzájuk.
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.
