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. Maga Balázs megoldása. Be fogjuk bizonyítani, hogy amennyiben , ahol pozitív egész, akkor . Ennek igazolásához két dolgot kell tennünk. Egyrészt bizonyítanunk kell, hogy minden lehetséges békés elrendezés esetén marad szabadon -s négyzet. Másrészt meg kell mutatnunk, hogy létezik a bástyáknak olyan békés elrendezése, ami esetén nem marad szabadon ennél nagyobb négyzet. Ezen lépéseket ebben a sorrendben tesszük meg. I. Számozzuk meg az oszlopokat 1-től -ig balról jobbra, a sorokat szintén lentről felfelé. Ekkor lesz olyan bástya, ami az 1. oszlopban van. Legyen ennek sorszáma , ekkor ezen bástya koordinátái . Tekintsünk most úgy darab szomszédos sort, hogy az sor köztük van. Mivel , ez lehetséges. Ezen sorban még további bástya található -n kívül, mivel békés elrendezésben minden sorban pontosan egy bástya van. Indirekte tegyük fel, hogy ebben az darab sorban nem marad szabadon -s négyzet. Ez azt jelenti, hogy bármely szomszédos oszlopba kerül bástya ezen az darab soron. Azaz ha tekintjük ezen bástyák oszlopszámát növekvő sorrendben (ezeket jelölje ), akkor tetszőleges esetén . Ebből adódik, hogy . Mivel viszont , , ezen sorszámú oszlop után még legalább darab oszlopban nincs bástya ezen az darab soron. Ez viszont éppen azt jelenti, hogy szabadon marad egy -s négyzet. Ez ellentmondás, tehát valóban mindig marad szabadon -s négyzet. II. Itt elegendő egy konstrukciót létrehoznunk, aminél nem marad szabadon -s négyzet. Helyezzük el bástyáinkat a következő módon: az 1. sorban levő bástya legyen az mezőn. A második sorban levő legyen az mezőn. És így tovább, amint egy sorral feljebb lépünk, mindig oszloppal lépjünk jobbra, amíg ez lehetséges, azaz amíg az így kapott oszlopszám nem lépi túl az -t. Ha viszont túllépi, válasszuk a legkisebb üres sor- és oszlopszámokkal rendelkező mezőt, azaz a -t. Innen indulva megint a fenti algoritmust követjük: 1 sorral feljebb, oszloppal jobbra, amíg ez lehetséges. Ha nem, a mezőt választjuk. Ezt az algoritmust folytatva pakoljuk fel a bástyákat, míg a sorszám el nem éri az -t. Azt állítom, hogy az így kapott elrendezésben nem marad szabadon -s négyzet, azaz ez az elrendezés megfelel számunkra. Először azt kell meggondolnunk, hogy egyáltalán békés elrendezéshez jutottunk-e, azaz igaz-e, hogy minden sorban és oszlopban pontosan 1 bástya van. Mivel bástyát helyeztünk el, ez ekvivalens azzal, hogy egyik sorban vagy oszlopban sincs 1-nél több bástya. A sorokra ez nyilvánvaló, mivel a bástyák elhelyezése során egyesével lépdeltünk fel rajtuk. Egy oszlopban pedig azért nem lehet két bábu, mert először az -gyel 1 maradékot adó oszlopokon mentünk végig 1-től indulva -ig, aztán a 2 maradékot adókon stb. Így a bástyák elhelyezése során maradékosztályonként soroltuk fel a számokat 1-től -ig. Ekkor világos, hogy ugyanabba a maradékosztályba nem kezdhettünk bele kétszer, hiszen akkor már -nél több bástyát kellett volna elhelyeznünk. Tehát valóban békés az elrendezésünk. Tehát már csak azzal kell foglalkoznunk, hogy nem maradhatott -s négyzet szabadon. Ez ekvivalens azzal, hogy tetszőleges módon választva szomszédos sort, nincs úgy szomszédos oszlop, hogy mindegyik üres lenne ezen soron belül. Ezt fogjuk tehát bizonyítani. Először nézzük azt az esetet, amikor van olyan -es maradékosztály, amit teljes egészében tartalmaz a kiválasztott darab sorunk, azaz a megjelenő oszlopszámok között ott van az összes 1 és közötti szám, ami -gyel osztva egy adott maradékot ad. Ekkor nyilván nincs olyan szomszédos oszlop, ami üres lenne ezen az soron, mivel tetszőleges szomszédos oszlop között van olyan, melynek sorszáma maradékot ad -gyel osztva. Ezzel az esettel tehát készen vagyunk. Tehát már csak azzal az esettel kell foglalkoznunk, amikor nincs olyan maradékosztály, ami teljes egészében fel lenne sorolva ebben az sorban. Ekkor tehát legalább 2 maradékosztály elemei jelennek meg, mint oszlopszámok. Másrészt mivel csak akkor váltunk maradékosztályt, ha az aktuálisat már teljes egészében felsoroltuk, nem lehetséges, hogy legalább 3 maradékosztály elemei jelenjenek meg, mint oszlopszámok, hiszen ekkor a nem szélsők összes 1 és közötti reprezentánsa megjelenik az oszlopszámok között, márpedig azt ebben az esetben kizártuk. Tehát valójában most már csak azzal foglalkozunk, amikor az szomszédos sorból álló blokkunk pontosan 2 maradékosztályból tartalmaz oszlopszámot. Legyenek ezek és . Ekkor , mivel a maradékosztályokat 1-től indulva soroljuk fel, így ez a maradékosztály az utolsó. viszont lehet 0, ekkor rendhagyó módon -es maradéknak tekintjük mod az egyszerűség kedvéért. Ekkor az oszlopszámok a konstrukció megalkotási algoritmusa alapján lentről felfelé haladva: , , , , , , , . Ekkor . Indirekte tegyük fel, hogy nincs így. Az imént sort vettünk fel, így a fent megjelenő együtthatók (, , , , 0, 1, , ) száma . esetén ezek mind eltérőek, továbbá is eltér mindtől. Így a , , , , , , , , számok mind eltérőek, valamint mindegyik legalább 0 és kisebb, mint , mivel a legnagyobb közülük , s még is igaz. Tehát a nemnegatív, -nél kisebb többszörösök száma legalább . Másrészt miatt a legnagyobb ilyen többszörös az , a legkisebb pedig a , azaz az ilyen többszörösök száma valójában . Ez ellentmondás, tehát valóban . Ugyanakkor . Ellenkező esetben ugyanis . Ez utóbbi itt a legnagyobb -nél nemnagyobb, -gyel osztva maradékot adó szám. Így nyilván a legnagyobb -nél nemnagyobb -gyel osztva maradékot adó szám. Ez viszont azt jelenti, hogy az -es maradékosztály összes -nél nemnagyobb pozitív reprezentánsa megjelenik ebben az sorban, mint oszlopszám, ami ellentmond az esetünk kiinduló feltételével. Tehát , azaz . Tehát az itt megjelenő oszlopszámok között van. Ebből viszont már rövid úton következik, hogy nem maradhat üresen szomszédos oszlop ebben az sorban. Először is a legkisebb oszlopszám , így az első oszlop biztosan nem üres. Utána -ig végig legfeljebb a különbség a szomszédos sorszámok között, nincs gond, továbbra sem maradhat üresen szomszédos oszlop. Ezt követően nem maradhat üresen oszlop, hiszen két oszlopszám különbsége. Innen viszont -ig ismét végig a különbség az oszlopszámok között, mint az imént, azaz most sem maradhat üresen szomszédos oszlop. Ezen iménti oszlop pedig nem lehet -nél távolabb a tábla szélétől, mivel ez a legnagyobb -nél nemnagyobb reprezentánsa egy -es maradékosztálynak. Azaz akárhogy választunk ki szomszédos sort, nem lesz bennük szomszédos üres oszlop. Tehát a konstrukciónk valóban megfelel az elvárásainknak. Ezzel készen vagyunk, valóban minden esetén, ha , akkor . |