Feladat: 2014. évi Nemzetközi Matematika Diákolimpia 12. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Maga Balázs 
Füzet: 2014/október, 387 - 389. oldal  PDF  |  MathML 
Témakör(ök): Nemzetközi Matematikai Diákolimpia, Indirekt bizonyítási mód, Logikai feladatok, Maradékosztályok
Hivatkozás(ok):Feladatok: 2014/szeptember: 2014. évi Nemzetközi Matematika Diákolimpia 12. 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.

Maga Balázs megoldása. Be fogjuk bizonyítani, hogy amennyiben i2<n(i+1)2, ahol i pozitív egész, akkor k=i.
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 i×i-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 n-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 s1, ekkor ezen bástya koordinátái (1,s1). Tekintsünk most úgy i darab szomszédos sort, hogy az s1 sor köztük van. Mivel n>i2i, ez lehetséges. Ezen i sorban még további i-1 bástya található (1,s1)-n kívül, mivel békés elrendezésben minden sorban pontosan egy bástya van. Indirekte tegyük fel, hogy ebben az i darab sorban nem marad szabadon i×i-s négyzet. Ez azt jelenti, hogy bármely szomszédos i oszlopba kerül bástya ezen az i darab soron. Azaz ha tekintjük ezen bástyák oszlopszámát növekvő sorrendben (ezeket jelölje 1=o1<o2<...<oi), akkor tetszőleges j1,2,...,i-1 esetén oj+1-oji. Ebből adódik, hogy oio1+i(i-1)=i2-i+1. Mivel viszont n>i2, ni2+1, ezen oi sorszámú oszlop után még legalább i darab oszlopban nincs bástya ezen az i darab soron. Ez viszont éppen azt jelenti, hogy szabadon marad egy i×i-s négyzet. Ez ellentmondás, tehát valóban mindig marad szabadon i×i-s négyzet.
II. Itt elegendő egy konstrukciót létrehoznunk, aminél nem marad szabadon (i+1)×(i+1)-s négyzet. Helyezzük el bástyáinkat a következő módon: az 1. sorban levő bástya legyen az (1,1) mezőn. A második sorban levő legyen az (i+2,1+1) mezőn. És így tovább, amint egy sorral feljebb lépünk, mindig i+1 oszloppal lépjünk jobbra, amíg ez lehetséges, azaz amíg az így kapott oszlopszám nem lépi túl az n-t. Ha viszont túllépi, válasszuk a legkisebb üres sor- és oszlopszámokkal rendelkező mezőt, azaz a (2,s2)-t. Innen indulva megint a fenti algoritmust követjük: 1 sorral feljebb, i+1 oszloppal jobbra, amíg ez lehetséges. Ha nem, a (3,s3) mezőt választjuk. Ezt az algoritmust folytatva pakoljuk fel a bástyákat, míg a sorszám el nem éri az n-t. Azt állítom, hogy az így kapott elrendezésben nem marad szabadon (i+1)×(i+1)-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 n 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 i+1-gyel 1 maradékot adó oszlopokon mentünk végig 1-től indulva n-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 n-ig. Ekkor világos, hogy ugyanabba a maradékosztályba nem kezdhettünk bele kétszer, hiszen akkor már n-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 (i+1)×(i+1)-s négyzet szabadon. Ez ekvivalens azzal, hogy tetszőleges módon választva i+1 szomszédos sort, nincs úgy i+1 szomszédos oszlop, hogy mindegyik üres lenne ezen i+1 soron belül. Ezt fogjuk tehát bizonyítani.
Először nézzük azt az esetet, amikor van olyan i+1-es maradékosztály, amit teljes egészében tartalmaz a kiválasztott i+1 darab sorunk, azaz a megjelenő oszlopszámok között ott van az összes 1 és n közötti szám, ami i+1-gyel osztva egy adott m maradékot ad. Ekkor nyilván nincs olyan i+1 szomszédos oszlop, ami üres lenne ezen az i+1 soron, mivel tetszőleges i+1 szomszédos oszlop között van olyan, melynek sorszáma m maradékot ad i+1-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 i+1 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 n 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 i+1 szomszédos sorból álló blokkunk pontosan 2 maradékosztályból tartalmaz oszlopszámot. Legyenek ezek m és m+1. Ekkor m0, mivel a maradékosztályokat 1-től indulva soroljuk fel, így ez a maradékosztály az utolsó.
m+1 viszont lehet 0, ekkor rendhagyó módon i+1-es maradéknak tekintjük mod i+1 az egyszerűség kedvéért. Ekkor az oszlopszámok a konstrukció megalkotási algoritmusa alapján lentről felfelé haladva: a(i+1)+m, (a+1)(i+1)+m, ..., (a+a1)(i+1)+m, m+1, (i+1)+m+1, ..., b(i+1)+m+1. Ekkor ba-1. Indirekte tegyük fel, hogy nincs így. Az imént i+1 sort vettünk fel, így a fent megjelenő i+1 együtthatók (a, a+1, ..., a+a1, 0, 1, ..., b) száma i+1. b<a-1 esetén ezek mind eltérőek, továbbá b+1 is eltér mindtől. Így a 0(i+1), 1(i+1), ..., b(i+1), (b+1)(i+1), a(i+1), (a+1)(i+1), ..., (a+a1)(i+1) számok mind eltérőek, valamint mindegyik legalább 0 és kisebb, mint n, mivel a legnagyobb közülük (a+a1)(i+1), s még (a+a1)(i+1)+mn is igaz.
Tehát a nemnegatív, n-nél kisebb i+1 többszörösök száma legalább i+2. Másrészt n(i+1)2 miatt a legnagyobb ilyen többszörös az i(i+1), a legkisebb pedig a 0(i+1), azaz az ilyen többszörösök száma valójában i+1. Ez ellentmondás, tehát valóban ba-1. Ugyanakkor b<a+a1. Ellenkező esetben ugyanis nb(i+1)+m+1>(a+a1)(i+1)+m. Ez utóbbi itt a legnagyobb n-nél nemnagyobb, i+1-gyel osztva m maradékot adó szám. Így nyilván b(i+1)+m+1 a legnagyobb n-nél nemnagyobb i+1-gyel osztva m+1 maradékot adó szám. Ez viszont azt jelenti, hogy az m+1-es maradékosztály összes n-nél nemnagyobb pozitív reprezentánsa megjelenik ebben az i+1 sorban, mint oszlopszám, ami ellentmond az esetünk kiinduló feltételével. Tehát a-1b<a+a1, azaz ab+1a+a1. Tehát (b+1)(i+1)+m az itt megjelenő oszlopszámok között van. Ebből viszont már rövid úton következik, hogy nem maradhat üresen i+1 szomszédos oszlop ebben az i+1 sorban.
Először is a legkisebb oszlopszám m+1i+1, így az első i+1 oszlop biztosan nem üres. Utána b(i+1)+m+1-ig végig legfeljebb i+1 a különbség a szomszédos sorszámok között, nincs gond, továbbra sem maradhat üresen i+1 szomszédos oszlop. Ezt követően nem maradhat üresen i+1 oszlop, hiszen (b+1)(i+1)+m-b(i+1)+(m+1)=i-1 két oszlopszám különbsége. Innen viszont (a+a1)(i+1)+m-ig ismét végig i+1 a különbség az oszlopszámok között, mint az imént, azaz most sem maradhat üresen i+1 szomszédos oszlop. Ezen iménti oszlop pedig nem lehet i+1-nél távolabb a tábla szélétől, mivel ez a legnagyobb n-nél nemnagyobb reprezentánsa egy i+1-es maradékosztálynak. Azaz akárhogy választunk ki i+1 szomszédos sort, nem lesz bennük i+1 szomszédos üres oszlop. Tehát a konstrukciónk valóban megfelel az elvárásainknak. Ezzel készen vagyunk, valóban minden n2 esetén, ha i2<n(i+1)2, akkor k=i.