A C. 1844. matematika gyakorlat megoldása

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.