Feladat:	2017. évi Kürschák matematikaverseny 3. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2018/február, 75 - 77. oldal		PDF  |  MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Számelrendezések, Irányított gráfok
Hivatkozás(ok):	Feladatok: 2018/február: 2017. évi Kürschák matematikaverseny 3. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Egy $n\times n$-es táblázat $k$-dik oszlopának hibája legyen $n-d\left(k\right)$, ahol $d\left(k\right)$ jelöli a $k$-dik oszlopbeli különböző számok számát. A táblázat összhibája pedig legyen a táblázatbeli oszlopok hibáinak összege. Azt kell igazolnunk, hogy $T$ sorain belül lehet úgy permutálni az ott álló számokat, hogy az így kapott táblázat összhibája $0$ legyen. Az alábbiakban egy olyan eljárást mutatunk, amely tetszőleges pozitív összhibájú táblázat esetén bizonyos sorok alkalmas átrendezésével csökkenti az összhibát. Mivel a szóban forgó összhiba egész szám, ezért e hibacsökkentő lépés véges sokszori alkalmazásával a táblázat összhibája $0$-ra csökkenthető, és ezzel a feladat állítása bizonyítást nyer. Tegyük fel tehát, hogy $T$-ben ‐ mondjuk ‐ az első oszlop hibája pozitív. Ennek oka, hogy legalább két azonos szám (mondjuk két $1$-es) szerepel benne. Mivel $T$ minden sorában legfeljebb egy $1$-es szerepel, ezért $T$-nek lesz olyan oszlopa, amiben nem szerepel $1$-es. Az általánosság megszorítása nélkül feltehető, hogy a második oszlop ilyen. Egy $G$ irányított gráfot definiálunk a $T$ táblázat első két oszlopában előforduló számok (mint csúcsok) halmazán úgy, hogy ha valamelyik sorban az első két elem $i$ és $j$ (ebben a sorrendben), akkor $G$-be behúzunk egy $i$-ből $j$-be vezető élt. Induljunk el az így kapott $G$ gráf $1$-es csúcsából, és haladjunk az irányított élek mentén. Két eset lehetséges. Előbb-utóbb vagy egy olyan $u$ (nyelő) csúcsba érkezünk, ahonnan nem vezet ki él vagy egy olyan $v$ csúcsba érünk, ahol már korábban jártunk. Mindkét esetben felcseréljük a bejárt éleknek megfelelő sorok első két elemét. Ezáltal az első esetben az első oszlopban csökken az $1$-esek száma, míg a második oszlopban megjelenik egy $1$-es, továbbá, a második oszlopból egy, az első oszlopban eddig nem szerepelő $u$ elem kerül át az első oszlopba. Ettől eltekintve az egyes oszlophoz tartozó számhalmazok nem változnak, tehát $T$ összhibája $2$-vel csökken. A második esetben az első két oszlophoz tartozó számhalmazok úgy változnak, hogy egy $1$-es átkerül az első oszlopból a másodikba, miközben egy ettől különböző, az első oszlopban már eddig is megtalálható $v$ szám átkerül a második oszlopból az elsőbe. Ezáltal az első oszlopban álló számok halmaza nem változik, tehát az első oszlop hibája is annyi marad amennyi volt. Emellett azonban a második oszlop hibája, és ennek megfelelően a táblázat összhibája eggyel csökken. Ezzel a hibacsökkentő lépést leírtuk, a feladat állítását igazoltuk.   II. megoldás. Készítsük el azt a $G_T$ páros gráfot, amelynek egyik színosztályának $s_1\mathrm{,}{s}_2\mathrm{,}\text{...}\mathrm{,}{s}_n$ csúcsait a $T$ táblázat sorai, a másik színosztálybeli $a_1\mathrm{,}{a}_2\mathrm{.}\text{...}$ csúcsokat pedig a $T$-ben található számok alkotják. Az $s_i$ és $a_j$ csúcsok között pedig akkor fusson él $G_T$-ben, ha az $a_j$ szám előfordul a $T$ táblázat $s_i$ sorában. Világos, hogy minden $s_i$ csúcs $G_T$-beli fokszáma pontosan $n$, míg tetszőleges $a_j$ csúcs fokszáma pedig legfeljebb $n$, hiszen egyfelől minden sorban pontosan $n$ szám áll, másfelől pedig minden szám legfeljebb $n$-szer (soronként egyszer) fordul elő a $T$-ben. Kőnig ismert élszínezési tétele szerint tehát $G_T$ élei kiszínezhetők az $\mathrm{1,2,}\text{...}\mathrm{,}n$ színek felhasználásával úgy, hogy a közös végponttal rendelkező élek különböző színt kapjanak. Ennek a színezésnek a segítségével az alábbi módon rendezzük át a $T$ táblázat sorait. Mivel $s_i$-ből $G_T$-ben $n$ különböző színű él indul, ezért ezen élek közül pontosan egy (mondjuk $s_i{a}_j$) kapta a $k$-dik színt. Legyen ekkor $a_j$ a $T^{*}$ táblázat $v_i$ sorának $k$-dik eleme. A $G_T$ definíciója miatt $a_j$ szerepel a $T$ táblázat $s_i$ sorában, tehát az imént definiált átrendezés valóban végrehajtható a $T$ táblázaton. Mivel a fenti $T^{*}$ minden egyes oszlopában azonos színre színezett éleknek megfelelő számok állnak, ezért $T^{*}$ egyetlen oszlopában sem állhat két egyforma szám. Nekünk pedig éppen ezt kellett igazolunk.   Megjegyzések. 1. A feladat ,,hátterét'' a II. megoldás mutatja: voltaképp Kőnig élszínezési tételével egyenértékű a bizonyítandó állítás. A trükk annyi, hogy a táblázat által definiált ,,szokásos'' páros gráf helyett (aholis az oszlopok és a sorok felelnek meg a színosztályoknak, és a táblázat mezői pedig az éleknek), itt az egyik színosztályt a sorok, a másikat pedig a mezőkben álló számok alkotják, az éleket pedig az oszopok segítségével határozzuk meg. Érdemes végiggondolni, hogy mit is jelent a feladat állítása a ,,szokásos'' értelmezés szerint. Azt kell igazolnunk, hogy bárhogy is adunk meg a $K_{n\mathrm{,}n}$ páros gráf $A$ színosztályának minden csúcsához $n$ különböző színt, a gráf $n^2$ éle kiszínezhető úgy, hogy az azonos csúcsból induló élek színe különböző legyen és emellett minden él színe az $A$-beli végponthoz megadott színek közül kerüljön ki. 2. Dinitz sejtése azt mondja ki, hogy ha egy $n\times n$ méretű táblázat mind az $n^2$ mezejéhez tartozik egy-egy $n$ elemű halmaz, akkor kiválasztható ezen halmazoknak egy-egy eleme úgy, hogy azonos sorban vagy oszlopban álló mezőkhöz tartozó halmazokból ne válasszunk azonos elemet. Világos, hogy a sejtésből azonnal következik a feladat állítása, ha hozzárendeljük minden mezőhöz az adott mező sorában álló számokat. Dinitz sejtését Galvin igazolta, mégpedig abban az általánosabb formában, hogy ha egy $G$ véges, páros gráf minden éléhez legalább akkora színlista tartozik, mint a $G$-beli legnagyobb fokszám, akkor minden élhez úgy választható a listájából egy-egy szín, hogy az így kapott színezésben azonos színű éleknek ne legyen közös végpontja. Érdemes még megemlíteni, hogy nem páros gráfok esetén ugyanez az állítás azzal a változtatással, hogy a színlisták mérete a $G$ gráf élkromatikus száma (ami páros gráfra Kőnig tétele szerint épp a maximális fokszám), nem más, mint az ún. listaszínezési sejtés, amire a mai napig nem ismert bizonyítás. 3. Többen próbálkoztak $n$ szerinti teljes indukció alkalmazásával oly módon, hogy az indukciós lépésben először azt érik el, hogy az utolsó oszlop elemei különbözők legyenek, majd a bal felső $\left(n-1\right)\times \left(n-1\right)$-es táblázatra alkalmazzák az indukciós feltevést. Sajnos ebben a megközelítésben semmi sem garantálja, hogy az utolsó sor valamelyik (utolsótól különböző eleme) ne egyezzen meg egy másik elemmel ugyanabban az oszlopban. Működik azonban az $n$ szerinti teljes indukció akkor, ha megfelelően általánosítjuk a feladat állítását: azt igazoljuk, hogy amennyiben egy $k\times n$ méretű táblázat mind a $k$ sorában csupa különböző szám áll, továbbá egyetlen szám sem fordul elő $n$-nél többször a táblázatban, akkor lehetséges a sorokon belül úgy permutálni a számokat, hogy minden oszlopban csupa különböző szám álljon. Világos, hogy $n=1$ esetén ez teljesül. Tegyük fel, hogy $n$-re már igazoltuk az állítást, és tekintsünk egy $k\times \left(n+1\right)$ méretű táblázatot. A célunk ekkor az, hogy az utolsó oszlopba úgy rendezzünk be különböző számokat, hogy az első $n$ oszlopra teljesüljön az indukciós feltétel. Ehhez pedig mindössze azt kell elérni, hogy az utolsó oszlopban egyrészt csupa különböző szám álljon, másrészt pedig minden olyan szám, ami pontosan $\left(n+1\right)$-szer fordul elő a táblázatban, szerepeljen az utolsó oszlopban. A ,,szokásos'' páros gráfot definiálva, a Hall-tételből könnyen látható, hogy egyrészt lehetséges az utolsó oszlopba csupa különböző számot becserélni, másrészt pedig lehetséges úgy permutálni a sorokat, hogy minden olyan szám, ami $\left(n+1\right)$-szer szerepel a táblázatban, az utolsó oszlopban is előforduljon. Az indukciós lépés igazolásához azonban a két tulajdonság együttes fennállása szükséges. Ezt pedig a Mendelsohn‐Dulmage tétel biztosítja, amely szerint ha egy $G$ páros gráfban $M_1$ és $M_2$ párosítások (azaz közös végpont nélküli élek halmazai), akkor van olyan $M$ párosítás is $G$-ben, amely fedi az $A$ színosztály minden $M_1$ által fedett csúcsát és a $B$ színosztály minden $M_2$ által fedett csúcsát. 4. Érdemes végül rámutatni egy másik, a feladathoz szorosan kapcsolódó kutatási területre. A Rota-sejtés azt állítja, hogy ha egy $n\times n$ méretű táblázat minden mezejéhez egy-egy ${\text{R}}^n$-beli vektor tartozik azzal a tulajdonsággal, hogy az egy sorban álló vektorokból bármely ${\text{R}}^n$-beli vektor előállítható skalárral való szorzás és összeadás segítségével, akkor a táblázat sorain belül lehetséges a vektorokat úgy permutálni, hogy minden oszlopra is teljesüljön, hogy bármely ${\text{R}}^n$-beli vektor előállítható skalárral való szorzás és összeadás segítségével az adott oszlopban álló vektorokból. A versenyen kitűzött feladat felfogható a Rota-sejtés egy igen speciális eseteként. Hasonlóan a listaszínezési sejtéshez, jelenleg az általános Rota-sejtésre sem ismert bizonyítás.