Feladat: 1963. évi Kürschák matematikaverseny 1. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Fazekas Patrik ,  Gerencsér László ,  Lukovics Edit ,  Máté Attila 
Füzet: 1964/április, 146 - 148. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Egyéb szinezési problémák, Mátrixjátékok, Számelrendezések, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1964/április: 1963. évi Kürschák matematikaverseny 1. 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.

Nevezzük egyszerűség kedvéért az a magasságú tanulót a-nak, a b magasságút b-nek, stb. Tekintsük a sorát és b oszlopát. E sor és oszlop kereszteződésében elhelyezkedő széken is ül egy tanuló. Ennek magasságát c-vel jelöljük.
Számolunk azzal a lehetőséggel, hogy a, b, c nem mind különbözők. Ha ugyanis a és b egy sorban ül, akkor c azonos b-vel. Ha a és b egy oszlopban ül, akkor c és a azonos. Ha pedig a azonos b-vel, akkor c is azonos velük.
Minthogy a és c egy sorban ül, és a a sorában a legkisebb, c-nél sem lehet nagyobb, azaz a≤c. Ugyanígy adódik, hogy c≤b, hiszen c és b egy oszlopban ül, és b az oszlopában a legnagyobb. Ezek szerint a≤c≤b, tehát a≤b, vagyis: az a>b eset nem következhetik be.
Az a=b eset bekövetkezik, ha pl. az utolsó sorba a legnagyobb tanulókat ültetjük. Ekkor az utolsó sorban ülők legkisebbike egyaránt betölti a és b szerepét, mert egyrészt a sorában nincs nála kisebb, de minden más sorban van, másrészt az oszlopában nincs nála nagyobb, de minden más oszlopban van.
Az a<b eset bekövetkezik, ha pl. az előző elrendezésből indulunk ki, de az utolsó sor legkisebb tanulója helyet cserél az oszlopában ülő valamelyik másik tanulóval. Az előreültetett tanuló a helycsere után is változatlanul betölti b szerepét, hiszen oszlopában nincs nála nagyobb, de minden más oszlopban van. Minthogy azonban az előreültetett tanuló új sorának minden más tanulója nála kisebb, a keresésekor ő még az egyes sorokból kiszemelt legkisebbek között sem szerepel, s így a szerepét nem ő tölti be.

 

Megjegyzés. 1. A feladat p>1, q>1 megszorítását kihasználtuk akkor, amikor ugyanabban az oszlopban ülő másik tanulóról, s amikor ugyanabban a sorban ülő minden más tanulóról szóltunk. A megszorításra szükség van, mert ha a székek egyetlen sorban vagy egyetlen oszlopban helyezkednek el, akkor nyilván a legkisebb, illetőleg a legnagyobb tölti be egyszerre a és b szerepét. Ilyenkor tehát csak az a=b eset valósulhat meg.
 

2. Felvetjük a kérdést, hogy minden tanuló számolhat-e azzal a lehetőséggel, hogy a szerepét majd ő tölti be. Ugyanezt kérdezzük a b szerepet illetően is. Azt állítjuk, hogy a legkisebb p-1 tanuló és a legnagyobb q-1 tanuló egyik szerep betöltésekor sem jöhet szóba.
a esetében ez abból következik, hogy a a saját sorának legkisebbike, tehát a sorában van q-1 nála nagyobb tanuló, viszont minden más sorban van a-nál kisebb, azaz van legalább p-1 nála kisebb tanuló. Hasonlóan okoskodhatunk b esetében is, mert a saját oszlopában p-1 nála kisebb tanuló ül, és minden más oszlopban van nála nagyobb, azaz legalább q-1 nála nagyobb tanuló van.
Ha tehát a tanulókat a legkisebbtől kezdve megszámozzuk, akkor csak a
p,p+1,p+2,...,pq-q+1
sorszámú tanulók tölthetik be az a, b szerepeket.
 

3. Eddigi megállapításaink bizonyos korlátozásokat tartalmaztak. Azt kérdezzük most, hogy ezeket a korlátozásokat figyelembe véve minden eset megvalósulhat-e. Pontosabban szólva a következő kérdést vetjük fel: A tanár a teremben elhelyezkedő székek egyikére a jelet, egy másikra vagy esetleg ugyanarra b jelet tesz; ezután a folyosón gyülekező tanulókat nagyság szerint sorba állítja, és a p, p+1, ..., pq-q+1 sorszámu tanulók közül kijelöl egyet vagy kettőt aszerint, hogy a teremben ugyanarra a székre tette-e az a és a b jelet, vagy sem, mégpedig abban az esetben, amikor a megjelölt székek nincsenek sem egy sorban, sem egy oszlopban, akkor két olyan tanulót jelöl ki, akik a nagyság szerinti sorban nem állnak egymás mellett; kérdés, hogy elhelyezhetők-e a tanulók a teremben úgy, hogy a megjelölt székekre a kijelölt tanulók üljenek, mégpedig, ha ketten vannak, akkor a kisebbikük üljön az a jelű székre, s hogy a és b szerepét éppen az a és b jelű széken ülő tanuló töltse be.
Azt állítjuk, hogy ez mindig lehetséges. Meg kell említenünk, hogyha a megjelölt székek nincsenek sem egy sorban, sem egy oszlopban, akkor megoldásunk értelmében szerepelnie kell egy a-nál nagyobb és b-nél kisebb c tanulónak, s ezért a és b a nagyság szerinti sorban nem állhattak egymás mellett. Ez az eset természetesen csak akkor valósítható meg, ha a p, p+1, ..., pq-q+1 sorszámú tanulók száma 2-nél nagyobb, azaz
pq-p-q+2>2,(p-1)(q-1)>1,


vagyis ilyenkor a p, q értékek között kell 2-nél nagyobbnak lennie. Eszerint bizonyos kivételt jelent a p=q=2 eset, mert ekkor a 4 szék közül nem szabad két átlósan elhelyezkedőt megjelölni. Ha ugyanis a tanár így járna el, akkor nem tudna a folyosón az előírást betartva kijelölni két tanulót.
Állításunk bizonyítása érdekében először is azt említjük meg, hogy a teremben a sorokat is és az oszlopokat is szabadon felcserélhetjük a rajtuk ülőkkel együtt; ez nem változtat azon, hogy ki tölti be az a, b szerepeket. Ezért nem jelent megszorítást, ha csak azokkal az esetekkel foglalkozunk, amikor az a jelű szék az utolsó sor bal szélén áll, a b jelű szék pedig az első vagy az utolsó sor valamelyik szélső széke. Nevezzük a p-1 legkisebb tanulót ,,kicsinek'', a q-1 legnagyobb tanulót pedig ,,nagynak''.
Ha a b jel is az utolsó sor bal szélső székére került, akkor a kijelölt egyetlen tanulót erre a székre ültetjük, az utolsó sor többi székére a nagyokat, a bal szélső oszlop többi székére a kicsiket, a még el nem foglalt székekre pedig a többi tanulót ültetjük. Ilyenkor valóban az egyetlen kijelölt tanuló jut az a, b szerepek mindegyikéhez.
 
 
1. ábra
 

A többi esetben ábrán mutatunk be a követelményt kielégítő elrendezést (1. ábra). Az ábra a p=4, q=5 esetre készült, de módszere minden p>1, q>1 esetben alkalmazható. A kicsik helyét pont, a nagyok helyét kör jelöli. Az ábrán meg nem jelölt helyeken a többi tanuló tetszés szerint helyezkedhetik el. Ha a és b átellenes sarkokban van, akkor c olyan tanulót jelöl, akit a nagyság szerinti sorban a és b közrefog. Erre az esetre ábránk két elrendezést mutat be. Az első akkor alkalmazható, ha q>2, a második pedig akkor, ha p>2. Könnyű ellenőrizni, hogy a követelmények minden esetben teljesülnek.