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 magasságú tanulót -nak, a magasságút -nek, stb. Tekintsük sorát és oszlopát. E sor és oszlop kereszteződésében elhelyezkedő széken is ül egy tanuló. Ennek magasságát -vel jelöljük. Számolunk azzal a lehetőséggel, hogy , , nem mind különbözők. Ha ugyanis és egy sorban ül, akkor azonos -vel. Ha és egy oszlopban ül, akkor és azonos. Ha pedig azonos -vel, akkor is azonos velük. Minthogy és egy sorban ül, és a sorában a legkisebb, -nél sem lehet nagyobb, azaz . Ugyanígy adódik, hogy , hiszen és egy oszlopban ül, és az oszlopában a legnagyobb. Ezek szerint , tehát , vagyis: az eset nem következhetik be. Az 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 és 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 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 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, keresésekor ő még az egyes sorokból kiszemelt legkisebbek között sem szerepel, s így szerepét nem ő tölti be.
Megjegyzés. 1. A feladat , 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 és szerepét. Ilyenkor tehát csak az eset valósulhat meg.
2. Felvetjük a kérdést, hogy minden tanuló számolhat-e azzal a lehetőséggel, hogy szerepét majd ő tölti be. Ugyanezt kérdezzük a szerepet illetően is. Azt állítjuk, hogy a legkisebb tanuló és a legnagyobb tanuló egyik szerep betöltésekor sem jöhet szóba. esetében ez abból következik, hogy a saját sorának legkisebbike, tehát a sorában van nála nagyobb tanuló, viszont minden más sorban van -nál kisebb, azaz van legalább nála kisebb tanuló. Hasonlóan okoskodhatunk esetében is, mert a saját oszlopában nála kisebb tanuló ül, és minden más oszlopban van nála nagyobb, azaz legalább nála nagyobb tanuló van. Ha tehát a tanulókat a legkisebbtől kezdve megszámozzuk, akkor csak a sorszámú tanulók tölthetik be az , 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 jelet, egy másikra vagy esetleg ugyanarra jelet tesz; ezután a folyosón gyülekező tanulókat nagyság szerint sorba állítja, és a , , , sorszámu tanulók közül kijelöl egyet vagy kettőt aszerint, hogy a teremben ugyanarra a székre tette-e az és a 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 jelű székre, s hogy és szerepét éppen az és 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 -nál nagyobb és -nél kisebb tanulónak, s ezért és a nagyság szerinti sorban nem állhattak egymás mellett. Ez az eset természetesen csak akkor valósítható meg, ha a , , , sorszámú tanulók száma -nél nagyobb, azaz
vagyis ilyenkor a , értékek között kell -nél nagyobbnak lennie. Eszerint bizonyos kivételt jelent a eset, mert ekkor a 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 , szerepeket. Ezért nem jelent megszorítást, ha csak azokkal az esetekkel foglalkozunk, amikor az jelű szék az utolsó sor bal szélén áll, a jelű szék pedig az első vagy az utolsó sor valamelyik szélső széke. Nevezzük a legkisebb tanulót ,,kicsinek'', a legnagyobb tanulót pedig ,,nagynak''. Ha a 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 , 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 , esetre készült, de módszere minden , 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 és átellenes sarkokban van, akkor olyan tanulót jelöl, akit a nagyság szerinti sorban és közrefog. Erre az esetre ábránk két elrendezést mutat be. Az első akkor alkalmazható, ha , a második pedig akkor, ha . Könnyű ellenőrizni, hogy a követelmények minden esetben teljesülnek.
|