Feladat: 1974. évi Kürschák matematikaverseny 1. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Hajdú István ,  Kecskés Csaba ,  Markó Péter ,  Neumann Attila ,  Prőhle Péter ,  Sparing László 
Füzet: 1975/február, 51 - 53. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Logikai feladatok, Kombinatorikai leszámolási problémák, Koordináta-geometria, Egyéb sokszögek geometriája, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1975/február: 1974. é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.

I. megoldás. Ha valaki bemegy a könyvtárba, akkor ezután két olyan dolog történhetik meg, amely a feladat szempontjából lényeges. Vagy eszébe jut, hogy otthon hagyta az olvasójegyét és távozik, mielőtt egy másik ember bejönne, ‐ ekkor nyilvánvaló, hogy ugyanannyi embert hagy ott, mint amennyit talált, ‐; vagy ottmarad, és ez esetben újak érkeznek utána, az olvasók száma nő a polcok között.
A második esetet vizsgáljuk meg közelebbről!
Miután könyvtárunk úgyis különleges tulajdonságokkal rendelkezik, olvasói bizonyára elfogadják a következő módosítást, amely a feladat szempontjából közömbös: miután az egyes személyek nincsenek kitüntetve, teljesen mindegy, hogy adott pillanatban ki lép be vagy ki hagyja el a termet, ezért tehát megállapodhatunk abban, hogy mindig az menjen el, aki utoljára bejött. Például: fessünk az egyik béketűrő olvasó hátára egy nagy vörös ,,A'' betűt. ,,A'' bejön, felírja, hogy n db embert talált az olvasóteremben. Ezután leül, közben jönnek-mennek a többiek. Tegyük fel, hogy k db olvasó érkezett még. Egyszercsak ,,A'' feláll és elindul az ajtó felé. Ekkor azonban elébe állunk és megkérjük, hogy maradjon még. Helyette elküldjük azt, aki legutóbb bejött, akinek a száma, (n+k), a belépő tábla legalján van. A feladat szempontjából teljesen közömbös, hogy ,,A'' barátunk egész nap ott rostokol, hiszen egy főt elzavartunk helyette. Tettük ezt pedig oly módon, hogy minden távozó ugyanazt a számot írta fel a távozási táblára, mint a másikra, amikor bejött. Ha egy idő múlva már senki sem jön többé olvasni, akkor kiengedjük a bennszorultakat érkezésük fordított sorrendjében. Így sor kerül szegény ,,A''-ra is, aki önkényünk áldozata lett, majd többi társára, míg végül senki sem marad benn. Így tehát minden olvasóhoz egy számpárt rendeltünk hozzá egy-egyértelműen. Miután a feladat szempontjából lényeges változtatást nem tettünk, ugyanazt az eredményt kell kapnunk, mint egyébként, vagyis a két táblán ugyanazok a számok szerepelnek (noha más-más sorrendben).

 
II. megoldás. Módosítsuk az előírást a következőképpen: aki eltávozik, a bejárati táblán áthúzza a könyvtárban maradó olvasók számát, ha az szerepel ott áthúzatlanul; ha nem szerepel, akkor felírja a kijárati táblára. Nem nehéz belátni, hogy az utóbbira sohasem kerül sor, ha ugyanis k olvasó tartózkodik a könyvtárban, akkor a táblán (áthúzatlanul) a 0,1,...,k-1 számok szerepelnek egyszer-egyszer. Speciálisan, ha nincs bent senki, akkor a tábla is üres. Megmutatjuk, hogy ez a helyzet minden létszámváltozásnál érvényben marad.
Nyitáskor az utoljára említett helyzet áll fenn.
Ha egy időpontban a leírt helyzet fennáll és valaki érkezik a könyvtárba, akkor a létszám (k+1)-re nő, és ugyanakkor a táblára a 0,1,...,k-1 számok mellé odakerül a k is.
Ha viszont valaki eltávozik, akkor (k-1) olvasót hagy a teremben és ennek megfelelően áthúzza a (k-1)-et, tehát a 0,1,...,(k-2) marad a táblán egy-egy példányban.
Záráskor senki sem marad a teremben, ennek megfelelően a bejárati táblán is minden szám át lesz húzva. Ez annak felel meg, hogy az eredeti előírás szerint a kijárati táblára ugyanazok a számok kerülnek, mint a bejáratira.
 
Megjegyzések. Sokféleképpen fogalmazták a versenyzők a megoldást, bár az alapgondolat hasonló a fentiekhez. Röviden említünk néhányat.
 

 
1. Többen egy embert állítottak egy létra elé, aki minden időben a létra annyiadik fokán áll, ahányan a könyvtárban vannak. Emberünk egyenként lép feljebb vagy lejjebb. Ahányadik fokról felfelé lép, az a szám kerül a bejárati táblára, ahányadikra lefelé lép, az a kijáratira. A feladat állításának helyessége abból következik, hogy minden fokról ugyanannyiszor lépett felfelé, ahányszor lefelé jövet rálépett, mert estére földet ér és hazamegy.
2. Egy koordinátarendszer x tengelyén egyenlő távolságban sorakozó pontok feleljenek meg az egymás utáni létszámváltozások időpontjának, és ábrázoljuk az y tengely irányában a létszámot. A kapott pontokat összekötő törtvonal és az x tengely egy vagy több zárt sokszöget alkot. Ezt k és (k+1) magasság közt az x tengellyel párhuzamosan átmetszve, a metsző egyenes ugyanannyiszor lép be a sokszögbe, mint ahányszor kilép belőle, azaz ugyanannyi emelkedő és süllyedő szakaszt metsz át. Az előbbiek alsó végpontja, azaz esetünkben k jelöli a bejárati táblára kerülő számot, a süllyedők alsó végpontja a kijárati táblára kerülőkét. Előbb tett megjegyzésünk szerint a kettő egyenlő.
3. Írjunk le (+1)-et, valahányszor érkezik valaki, és (-1)-et, valahányszor távozik. Ekkor bármelyik számig összeadva számainkat, az illető számnak megfelelő érkezés, ill. távozás után kialakult olvasólétszámot kapjuk. Ez az összeg nem lehet negatív, vagyis a sorozat bármelyik számáig legalább annyi (+1) van, mint (-1), az egész sorozatban pedig ugyanannyi van mindkettőből. A bejárati táblára az egyes (+1)-ek előtti számig terjedő összegek kerülnek, a kijárati táblára pedig a (-1)-ekig terjedő összegek [ezt a (-1)-et is még beleértve]. Most abból következik az állítás helyessége, hogy egy egymást követő (+1,-1) párnak megfelelően ugyanaz a szám kerül a két táblára, ha pedig ezt a párt kihagyjuk a sorozatból, akkor a sorozat leírt szerkezete nem változik meg.