Feladat: 1981. évi Kürschák matematikaverseny 2. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bali János ,  Dósa György ,  Gellér János ,  Király Zoltán ,  Magyar Ákos ,  Nacsa János ,  Simonyi Gábor ,  Szabó Endre ,  Szenes András ,  Tardos Gábor 
Füzet: 1982/február, 54 - 58. oldal  PDF  |  MathML 
Témakör(ök): Maradékos osztás, Egyéb szinezési problémák, Sakk, Kombinatorikai leszámolási problémák, Egészrész, törtrész függvények, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1982/február: 1981. évi Kürschák matematikaverseny 2. 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. Két bástya akkor ütheti egymást, ha egy sorban vagy egy oszlopban vannak. Mivel n bástyát kell elhelyeznünk, ezért olyan elhelyezéseket keresünk, amelyeknél minden sorban és minden oszlopban egy bástya áll, továbbá mindegyik bástya mezeje más-más színű. Válasszuk külön a kétféle követelményt: számláljuk először össze, hányféleképpen helyezhetünk el n bástyát úgy, hogy ne üthessék egymást, azután vizsgáljuk meg, hány olyan lehet az elhelyezések közül, amelyik nem tesz eleget a mezők színére tett követelménynek.
Kezdjük a bástyák elhelyezését az első sorral, ide n-féleképpen tehetjük le az első bástyát. Mind az n kezdést (n-1)-féleképpen folytathatjuk, mivel a második sorba ‐ a már letett bástya oszlopát kivéve ‐ bármelyik mezőre tehetjük a következő bástyát. Az első két sorba tehát n⋅(n-1)-féleképpen helyezhetünk bástyát úgy, hogy ne üthessék egymást. Ezután a harmadik sorban mindig (n-2) hely áll rendelkezésre a harmadik bástya számára, és így tovább. Az első (n-2) bástya megfelelő elhelyezése után az (n-1)-edik sorban még két hely áll rendelkezésre az utolsó előtti bástya elhelyezésére, és ha ezt is letettük az egyikre, ezzel az utolsó bástya helye is már meg van határozva. Az n bástyát tehát1

n⋅(n-1)⋅(n-2)⋅...⋅2=n!
elrendezésben helyezhetjük az n×n-es sakktáblára úgy, hogy semelyik kettő ne üthesse egymást.
Ha mármost egy ilyen elhelyezésben két bástya azonos színű mezőn áll, akkor az elhelyezés megsérti a színezésre vonatkozó kívánalmat, bárhogy helyezkedjék is el a többi bástya. A további (n-2) bástyát (n-2)!-féleképpen helyezhetjük el. Mivel n2/2 szín mindegyikével két-két mezőt színeztünk ki, és ezeknek a mezőpároknak bármelyikén állhat a kívánalmat megsértő két bástya, ezzel már elrontva a bástyaelhelyezést, így legfeljebb
(n-2)!⋅n22
bástyaelhelyezés nem felel meg a színezési feltételnek az n! közül. A mindkét követelményt kielégítő bástyaelhelyezések száma tehát nem kevesebb, mint
n!-(n-2)!⋅n22=(n-2)!⋅[n(n-1)-n22]=(n-2)!n2⋅(n-2).
Ez pozitív egész szám minden 2-nél nagyobb páros n-re, és ezekre mindig van a feltételeket kielégítő bástyaelhelyezés, amint azt a feladat állította.
Hozzátesszük, hogy n=2-re a feladat állítása nem igaz, amint azt a 2×2-es táblának a 4. ábra szerinti színezése mutatja. (Lásd 56. oldal).
 

Megjegyzések. 1. A továbbiakban kényelmes lesz felhasználni a következő észrevételt. A feladat szempontjából lényegtelen a sorok és az oszlopok sorrendje, mert ha van egy bástyaelhelyezés és két sort vagy két oszlopot felcserélünk a bennük elhelyezett bástyákat velük mozgatva, akkor a keletkezett új bástya-elhelyezésben két bábu akkor és csak akkor ütheti egymást, ha az eredeti elhelyezésben is üthették egymást; továbbá nem változik az sem, hogy milyen színű mezőn álltak az egyes bástyák.
2. A problémát kiterjeszthetjük páratlan n-ekre úgy, hogy (n2-1)/2 szín mindegyikével 2-2 mezőt színezünk ki és a fennmaradó mezőnek vagy egy további színt adunk, vagy megtiltjuk, hogy arra bástya kerüljön.
Az első esetben a fenti módon számolva azt kapjuk, hogy a mindkét követelményt kielégítő bástyaelhelyezések száma nem kevesebb, mint
n!-(n-2)!⋅n2-12=(n-1)!⋅n-12.
Ez minden 1-nél nagyobb páratlan számra pozitív egész, n=1-re pedig magától értetődő módon igaz a feladat állítása. Az első értelmezés mellett tehát minden páratlan n számra elhelyezhető n bástya az n×n-es sakktáblán úgy, hogy különböző színű mezőkön álljanak, és semelyik kettő ne üthesse egymást.
Ha pedig egy mező tiltott a bástyák számára, akkor kezdjük ennek a sorában a bástyák elhelyezését. Ezt (n-1)-féleképpen tehetjük meg. A következő sorba ismét (n-1)-féleképpen helyezhetünk bástyát, mert itt csupán az első bástyával nem kerülhet egy oszlopba az újabb bástya. Tovább mindig eggyel csökken az újabb bástya számára szóba jövő mezők száma, így ha az n×n-es sakktáblán van egy tilos mező, akkor (n-1)!⋅(n-1)-féleképpen helyezhetünk el úgy bástyákat, hogy ne legyenek köztük ütő helyzetben levők. A színezési feltételt nem kielégítő elhelyezések száma most sem nagyobb, mint
(n-2)!⋅n2-12.
így a mindkét követelménynek megfelelő elhelyezések száma legalább
(n-1)!⋅(n-1)-(n-2)!⋅n2-12=(n-1)!⋅n-32.
Ha tehát n>3, akkor a második értelmezés mellett is van megfelelő bástyaelhelyezés. Az eddigiek azonban még nem zárják ki, hogy a 3×3-as sakktáblán is legyen, hiszen csak alsó becslést nyertünk a megfelelő elhelyezések számára.
3. Vizsgáljunk meg egy 3×3-as sakktáblát egy tilos mezővel. (Az 1. megjegyzés szerint feltehetjük, hogy ez a bal alsó sarok). Ezt úgy akarjuk kiszínezni, hogy ne lehessen rajta 3 bástyát a kívánt módon elhelyezni. Jelöljük a sorokat számokkal, az oszlopokat betűkkel, ahogyan a sakkban szokás, a színeket pedig kisbetűkkel. Legyen a C1 mező színe k. Ide csak akkor nem tehetünk bástyát, ha az A2, B3 és A3, B2 mezőpárok vagy egyező színűek, vagy az egyik pár egyező színű, a másikban pedig szerepel a k szín. Mindenképpen feltehetjük, hogy A2 és B3 egyező, mondjuk l színű, mert ha nem így volna, akkor a 2-es és 3-as sor felcserélésével ezt elérhetjük. Az A2, B1, C3 mezőkre akkor nem tehetjük a 3 bástyát, ha az utóbbi kettő egyező m színű. Az A3, B1, C2 ezután csak akkor nem megfelelő bástyaelhelyezés, ha az első és harmadik mező egyező n színű, végül a még lehetséges A3, B2, C1 elhelyezés sem megfelelő, mivel B2 eleve már csak k színű lehet.
 
4. ábra
 
5. ábra

Azt találtuk tehát, hogy ha páratlan n-re egy n×n-es sakktábla egy mezejét elhagyjuk, a többit kiszínezzük úgy, hogy minden színnel két mező legyen kiszínezve, akkor n>3-ra továbbra is elhelyezhető n bástya a kívánt módon, n=3-ra azonban nem feltétlenül. A fenti gondolatmenet azt is adta, hogy csak az 5a ábra színezése mellett nem lehetséges az elhelyezés, valamint az ebből a felső két sor megcserélésével keletkezőnél (5b ábra). Az utóbbi azonban nem lényegesen különböző, a jobbra emelkedő átlóra történő tükrözéssel és a színek alkalmas átkeresztelésével keletkezik az 5a ábra színezéséből.
Figyeljük meg a továbbiak érdekében azt is, hogy ennek a ,,rossz'' elhelyezésnek minden 2×2-es résztáblájában legalább az egyik átló mezői különböző színűek.
4. Tardos Gábor észrevette, hogy n növekedésével a tiltott mezők számát is növelhetjük. Pontosabban, ha n>3 és az n×n-es sakktáblából n/2-nél kevesebb mezőt elhagyunk, a többit pedig kiszínezzük úgy, hogy egy színnel legfeljebb két mező legyen színezve, akkor is elhelyezhető n bástya úgy, hogy semelyik kettő ne üthesse egymást és csupa különböző színű mezőn álljanak. Páros n esetén tehát (n-2)/2 mezőt hagyhatunk el, páratlan n esetén (n-1)/2-t.
Ennek belátására gondoljuk meg, hogy egy kizárt mező (n-1)! bástyaelhelyezést hiúsít meg, tehát ha t tilos mező van, ez legfeljebb t⋅(n-1)! elhelyezést zár ki. A megmaradó mezőkből1 [12(n2-t)] egyszínű pár alkotható és ezek legfeljebb ugyanennyiszer (n-2)! bástyaelhelyezést zárhatnak ki. A megfelelő bástyaelhelyezések száma tehát legalább
(n-2)!{(n-1)(n-t)-[12(n2-t)]}==(n-2)!{n2-nt-n+t-12(n2-n)-[12(n-t)]}==(n-2)!{12n(n-2t-1)+t-[12(n-t)]}.
A középső kifejezést úgy kaptuk, hogy alkalmaztuk a következő könnyen belátható összefüggést: ha u egész szám, akkor
[u+v]=u+[v],
éspedig u=12(n2-n)-re. (Ez a kifejezés nyilvánvalóan egész szám).
Ha az utolsó alakba t helyébe (n-2)/2-t teszünk páros n esetén, illetőleg (n-1)/2-t páratlan n esetén, akkor (n-2)! szorzójára a következők adódnak:
n-1-[n+24],ill.n-12-[n+14].
Ha n 3-nál nagyobb egész szám, akkor a megfelelő kifejezés pozitív. Ezzel az állítást bebizonyítottuk.
A nyert eredmény azt adja többek közt, hogy 4×4-es sakktáblára egy tiltott mező esetén is elhelyezhető 4 bástya a kívánt módon, 5×5-ös táblára pedig 2 tiltott mező esetén is 5 bástya. Megmutatható, hogy ennél több is igaz: 4×4-es sakktábla esetén tetszés szerinti 2 mezőre megtilthatjuk bástya helyezését, 5×5-ös tábla esetén pedig már 5 mezőre, amik nincsenek egy sorban vagy egy oszlopban, akkor is lehetséges a bástyák kívánt módon történő elhelyezése.
Az I. megoldás meggyőzött arról, hogy létezik a követelményeknek megfelelő bástyaelhelyezés, sok is, anélkül, hogy eljárást adott volna ilyen elhelyezés megkeresésére. A következő megoldásban egy ilyen eljárás megadásával bizonyítjuk az állítás igaz voltát.
 

II. megoldás. A következő, a feladaténál valamivel általánosabb állítást fogjuk bebizonyítani: Ha n egy 3-nál nagyobb egész szám, és egy n×n-es sakktáblán egy mezőt tiltottnak nyilvánítunk, a többit kiszínezzük úgy, hogy legfeljebb 2 mező lehet egyező színnel festve, akkor elhelyezhető a táblán a bástya úgy, hogy semelyik 2 ne üthesse egymást és csupa különböző színű mezőn álljanak.
Helyezzük az első bástyát a tiltott mező sorának bármelyik megengedett mezejére. Ekkor a többi bástya a többi sorokban helyezendő el úgy, hogy a már letett bástyáétól különböző oszlopban álljon, és amennyiben van még egy, a lehelyezett bástyáéval egyező színű mező a tábla még megengedett részén, arra sem kerülhet bástya. Az (n-1) bástya számára megengedett mezők tehát egy (n-1)×(n-1)-es résztáblát adnak, esetleg egy tiltott mezővel. Ha ilyen nem adódik, akkor önkényesen nyilvánítsunk tiltottnak egy mezőt, ezzel visszavezettük a feladatot az eredetire, csak n helyett (n-1)-gyel. Az eljárást ismételjük addig, amíg vissza nem jutunk egy 4×4-es táblához egy tiltott mezővel, legyen ez A1.
Ketté választjuk a lehetőségeket. Először azt az esetet vizsgáljuk, amikor az A oszlopban vagy az 1-es sorban van olyan mező, amelyikkel egyező színű található a jobb felső 3×3-as résztáblán. Legyen pl. B1 és D2 színe k. (L. 6. ábra). Ekkor A2 színe egy újabb l szín. A jobb felső 2×2-es résztáblának az egyik átlójában esetleg fellép a másik l színű mező, de az egyik átlónak egyszínűnek kell lennie. Mondjuk C4 és D3 m színű. A4 és C2 egyező n színű kell hogy legyen, mert csak így nem ad megfelelő bástyaelhelyezést B1, C3-mal, amelyekkel egyező színű mezőket már ismerjük. Hasonlóan, egyező p színűnek kell lennie B3-nak és C1-nek, mert különben A4, D2-vel ad egy megfelelő bástyaelhelyezést. A2, B3, C4 ezután D1-gyel már csak akkor nem megfelelő 4 bástya elhelyezésére, ha az utolsó mező l színű. Ekkor azonban B4 egy újabb színnel van színezve, és így A2, B4, C1, D3 alkalmas a 4 bástya elhelyezésére (6. ábra).

6. ábra

Azt az esetet kell még megvizsgálnunk, ha minden A oszlopbeli mezővel egyszínű ‐ ha van ilyen egyáltalán ‐ az 1-es sorban van és viszont. Ilyen párnak nyilvánvalóan kell lennie. Legyen A2 és B1 k színű. B3 és C4 egyező l színű, mert A2, D1-gyel csak így nem adnak megfelelő bástyaelhelyezést, miután egyikük sem lehet D1-gyel egyező színű. Hasonlóan C2, D3 egyező m színű kell hogy legyen. A4, B3, C2, D1 csak akkor nem megfelelő, ha az első és utolsó mező, egyező n színű, A4, B1, C3, D2 pedig csak akkor, ha az utolsó kettő egyező p színű. Ekkor azonban A2, B4, C3, D1 megfelelő bástyaelhelyezést ad, mert B4 színe különbözik az eddig említett mezők színétől. Ezzel beláttuk, hogy n=4-re megoldható feladtunk és ezzel a megoldást befejeztük (7. ábra).
 


7. ábra

Megjegyzés. A fenti gondolatmenet alkalmazásával lényegesen tovább lehet menni a kizárható mezők kérdésében, mint amennyi az I. megoldás gondolatmenetével elérhető volt. Bebizonyítjuk, hogy ha n legalább 5, akkor a II. megoldás állítása még akkor is érvényes marad, ha előre kijelölt n-3 mezőre nem szabad bástyát helyezni.
A II. megoldás második részében bebizonyítottuk az állítás igaz voltát n=4-re. Ha n>4, akkor egy bástya elhelyezésével legalább 2 tiltott mezőt zárhatunk ki a továbbiakból. Ha van legalább 2 tiltott mező egy sorban vagy egy oszlopban, akkor ezek sorába, ill. oszlopába helyezünk egy bástyát, ha pedig ilyen nem fordul elő, akkor egy tiltott mező sorának és egy másik oszlopának a közös mezejére. Az elhelyezett bástya mezejével egyszínű mező viszont a továbbiak szempontjából tiltott mezővé válik. Így egy bástya elhelyezésével a problémát egy 1-gyel rövidebb oldalú tábla esetére vezettük vissza, amelyen legalább 1-gyel kevesebb a tiltott mezők száma.
Az eljárást n-4-szer ismételve egy 4×4-es résztáblához jutunk, amelyen legfeljebb 1 tiltott mező van, tehát elhelyezhető rajta 4 bástya a kívánt módon. Ezzel beláttuk állításunkat.
A kizárható mezők száma ezen túl is növelhető. Erre más alkalommal szándékszom visszatérni.
1Ezt a számot ,,n faktoriálisnak'' nevezik, és ‐ mint azt használtuk is ‐ így jelölik: n! Lényegében azt láttuk be, hogy n különböző dolgot ennyiféleképpen lehet egymás után rakni.

1[t]-vel, mint szokásos, a legnagyobb egész számot jelöljük, amelyik még nem nagyobb t-nél, a t úgynevezett egész részét.