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 ,,'' betűt. ,,'' bejön, felírja, hogy db embert talált az olvasóteremben. Ezután leül, közben jönnek-mennek a többiek. Tegyük fel, hogy db olvasó érkezett még. Egyszercsak ,,'' 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, , a belépő tábla legalján van. A feladat szempontjából teljesen közömbös, hogy ,,'' 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 ,,''-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 olvasó tartózkodik a könyvtárban, akkor a táblán (áthúzatlanul) a 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 -re nő, és ugyanakkor a táblára a számok mellé odakerül a is. Ha viszont valaki eltávozik, akkor olvasót hagy a teremben és ennek megfelelően áthúzza a -et, tehát a 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 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 tengely irányában a létszámot. A kapott pontokat összekötő törtvonal és az tengely egy vagy több zárt sokszöget alkot. Ezt és magasság közt az 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 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 -et, valahányszor érkezik valaki, és -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 van, mint , az egész sorozatban pedig ugyanannyi van mindkettőből. A bejárati táblára az egyes -ek előtti számig terjedő összegek kerülnek, a kijárati táblára pedig a -ekig terjedő összegek [ezt a -et is még beleértve]. Most abból következik az állítás helyessége, hogy egy egymást követő 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. |