Feladat:	B.4942	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Fraknói Ádám ,  Győrffy Ádám György ,  Schrettner Jakab ,  Vida Tamás ,  Weisz Máté (Szeged)
Füzet:	2019/február, 88 - 92. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Logikai feladatok, Kombinatorikai leszámolási problémák
Hivatkozás(ok):	Feladatok: 2018/március: B.4942

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. Azt állítjuk, hogy $k$ matematikus $2^{k-1}$-féleképpen tud beköltözni a szobákba. Ezt teljes indukcióval bizonyítjuk. $k=1$: Egy ember egy szobába csak $1=2^0=2^{1-1}$-féleképpen költözhet be. $k=2$: Az első ember beköltözik valamelyik szobába a kettő közül, a másodiknak már nincs választása, tehát $2=2^1=2^{2-1}$-féleképpen tudnak beköltözni. Most tegyük fel, hogy valamely $k$-ig ($k\ge 2$) minden pozitív egészre igaz az állításunk. Megmutatjuk, hogy ekkor $\left(k+1\right)$-re is igaz, vagyis $k+1$ matematikus $2^k$-féleképpen tud beköltözni a szobákba. Ha az első ember a saját szobájába (az első számúba) megy, akkor utána mindenki a neki kijelölt szobába fog menni, tehát ez egyféle beköltözés. Ha az első ember az $n$-edik szobába megy ($2\le n\le k+1$), akkor egészen az $\left(n-1\right)$-edik emberig mindenki más el tudja foglalni a saját szobáját. Foglalkozzunk a többi matematikussal, akiknek száma $\left(k+1\right)-\left(n-1\right)=k-n+2$. Az $n$-edikként érkezőnek az első foglalta el a szobáját, a többieké viszont még szabad. Vegyük észre, hogy éppen olyan helyzetben van ez a $k-n+2$ matematikus, mintha csak ők lennének a szállodában, és előttük senki sem érkezett volna. Mindenkinek megvan az előre kijelölt szobája: értelmezhető úgy, mintha az $n$-edik emberé lenne az 1. szoba, ő érkezne elsőnek, és neki felejtette volna el a recepciós megadni az utasítást. Vagyis ha az első ember az $n$-edik szobába megy ($2\le n\le k+1$), akkor a többiek $2^{\left(k-n+2\right)-1}$-féleképpen foglalhatják el a szobákat (az indukciós feltevés miatt). Mivel $n$ értéke $2$ és $k+1$ között bármi lehet, így ezeket összegezve kapjuk meg, hogy $k+1$ matematikus hányféleképpen választhat szobát: ${\displaystyle \begin{array}{c}\hfill {\displaystyle 1+{\sum }_{n=2}^{k+1}{2}^{\left(k-n+2\right)-1}=1+{\sum }_{n=2}^{k+1}{2}^{k-n+1}=}\hfill \\ \hfill {\displaystyle =1+\left(2^{k-1}+2^{k-2}+\text{...}+2^1+2^0\right)=1+\left(2^k-1\right)=2^k\mathrm{.}}\hfill \end{array}}$ Tehát $2^{99}$-féleképpen költözhetnek be a szobákba a vendégek.   Weisz Máté (Szegedi Radnóti Miklós Kís. Gimn., 10. évf.)     II. megoldás. Megvizsgálom a lehetőségek számát úgy csoportosítva, hogy hány ember nem került arra a helyre, ahova szánták: ‐ Ha minden ember oda került, akkor az első ember az első szobába ment, ez 1 lehetőség. ‐ Pontosan 1 ember nem kerülhetett rossz helyre. ‐ 2 ember került rossz helyre, ha az első vendég az $n$. szobát foglalta el ($2\le n\le 100$), majd az $n$. vendég az első szobát választotta. Ez $99=\left(\genfrac{}{}{0ex}{}{99}{1}\right)$ lehetőség. ‐ 3 ember nem került jó helyre, ha az első ember elfoglalta az $n$. szobát ($2\le n\le 99$), az $n$. ember elfoglal egy $m$. szobát ($n<m\le 100$), az $m$. ember pedig az elsőt. Ez annyi lehetőség, ahányféleképpen 2-től 100-ig 2 szobát ki tudunk választani, ahol a kisebb szám $n$-nek, a nagyobb $m$-nek felel meg, vagyis $\left(\genfrac{}{}{0ex}{}{99}{2}\right)$ lehetőség. ‐ Hasonlóan gondolkodva: ha $x$ ember került rossz helyre ($2\le x\le 100$), akkor a szobák közül 2-től 100-ig $x-1$ ember nincs jó helyen, hiszen $x>1$ esetén az első szobában nem az első vendég foglal helyet. A 99 szoba közül $\left(x-1\right)$-et $\left(\genfrac{}{}{0ex}{}{99}{x-1}\right)$-féleképpen lehet kiválasztani. Minden ilyen lehetőség egyféleképpen valósulhat meg, hiszen ha sorban vesszük a ,,rossz'' szobákat, akkor a bent lakó vendégek érkezésének sorszáma is növekvő sorrendbe kerül, mivel minden vendég csak a saját, vagy nála nagyobb sorszámú szobába mehetett, mert a többit addigra feltöltötték. Az összes lehetőség száma tehát: $1+\left(\genfrac{}{}{0ex}{}{99}{1}\right)+\left(\genfrac{}{}{0ex}{}{99}{2}\right)+\left(\genfrac{}{}{0ex}{}{99}{3}\right)+\text{...}+\left(\genfrac{}{}{0ex}{}{99}{99}\right)$. Mivel $1=\left(\genfrac{}{}{0ex}{}{99}{0}\right)$, így a lehetőségek száma $\left(\genfrac{}{}{0ex}{}{99}{0}\right)+\left(\genfrac{}{}{0ex}{}{99}{1}\right)+\left(\genfrac{}{}{0ex}{}{99}{2}\right)+\left(\genfrac{}{}{0ex}{}{99}{3}\right)+\text{...}+\left(\genfrac{}{}{0ex}{}{99}{99}\right)$, ami a Pascal-háromszög 100. sorában lévő számok összege. Az első sorban az összeg 1; és utána minden egyes szám az alatta lévő sorba két számhoz adódik hozzá, tehát a számok összege lefelé mindig megkétszereződik, a 100. sorban $2^{99}$. Tehát $2^{99}$-féleképpen költözhettek be.   Vida Tamás (Győr, Kazinczy F. Gimn., 10. évf.)     III. megoldás. Legyen a lehetséges beköltözések száma $n$ darab matematikus esetén $C_n$. Nyilvánvaló, hogy $C_1=1$. $n$ matematikus esetén, ha az első matematikus az első szobába költözik be, akkor mindenki egyértelműen beköltözik az érkezésének megfelelő szobába. Ha az első matematikus beköltözik a $k$-adik szobába ($2\le k\le n$), akkor az első utáni $k-2$ matematikus egyértelműen be tud költözni az érkezésének megfelelő szobába. A maradék $n-k+1$ matematikusnak adott az $1$., $\left(k+1\right)$-edik, $\left(k+2\right)$-edik, $\text{...}$, $n$-edik szoba a beköltözésre. Ekkor tekintsük a szobaszámokat $1$, $2$, $3$, $\text{...}$, $\left(n-k+1\right)$-nek. Ekkor az első matematikus tetszőleges szobába költözik be, a többi pedig a feladat szövegének megfelelően, tehát ekkor $C_{n+k-1}$-féleképpen tudnak beköltözni a matematikusok. Így ${\displaystyle \begin{array}{c}\hfill {\displaystyle C_n=1+C_{n-2+1}+C_{n-3+1}+\text{...}+C_{n-n+1}=}\hfill \\ \hfill {\displaystyle =1+C_{n-1}+C_{n-2}+\text{...}+C_1=1+{\sum }_{i=1}^{n-1}{C}_i\mathrm{.}}\hfill \end{array}}$ Ebből $\begin{array}{c}{\displaystyle C_{n-1}=1+\sum _{i=1}^{n-2}{C}_i\mathrm{,}}\end{array}$ és így $\begin{array}{c}{\displaystyle C_n=1+\sum _{i=1}^{n-1}{C}_i=1+\sum _{i=1}^{n-2}{C}_i+C_{n-1}=2\cdot C_{n-1}\mathrm{.}}\end{array}$ Tudjuk, hogy $C_1=1$, így $C_n=2^{n-1}$. Ebből pedig következik, hogy $100$ matematikus esetén a lehetséges beköltözések száma $2^{99}$.   Győrffi Ádám György (Miskolc, Földes Ferenc Gimn., 9. évf.)     IV. megoldás. Vegyünk egy tetszőleges 100 jegyű kettes számrendszerbeli számot. Minden számjegy azt jelöli, hogy az adott ember jó szobában van-e: a $0$ azt, hogy jó ember van a szobában, az $1$ pedig azt, hogy nem. Ha az első számjegy 0 (balról nézve), akkor minden számjegy 0, mert ha az első ember jó helyre ment, akkor már mindenki más is. Ha első számjegy 1 (balról nézve), akkor ez azt jelenti, hogy az első ember nem jó szobába ment. Ha az $x$-edik szobába ment, akkor $x$ és az $1$ számjegy között csupa 0 van. Ugyanígy, ha az $n$-edik ember az $i\mathrm{.}$ szobát választja (ahol $i\ne 1$ és $n>1$), akkor $i>n$ és az  $n$ és $i$ sorszámú számjegyek között minden szám 0 lesz. Ha az $n$-edik ember az 1-es szobát választja, akkor minden $n$ feletti számjegy 0 lesz. Olyan nem fordulhat elő, hogy az első számjegy 1 és a többi 0, mert az első ember elfoglalja valakinek a szobáját. Ilyen módon minden ilyen kettes számrendszerbeli számból egyértelműen kiszámolható, hogy ki melyik szobába ment és fordítva: abból, hogy ki melyik szobába ment, leírható pontosan egy kettes számrendszerbeli szám. (Pl. 100100100110100$\text{...}$0010: Az 1. ember a 4. szobába ment, a 4. ember a 7. szobába, a 7. ember a 10. szobába, a 10. ember a 11. szobába, a 11. ember a 13. szobába, $\text{...}$, a 99. ember az 1. szobába. Mindenki más a saját szobájába ment.) Összesen tehát $2^{99}-1+1=2^{99}$ eset van.   Fraknói Ádám (Budapest, Jedlik Ányos Gimn., 11. évf.)     V. megoldás. Tekintsük a feladatot általánosan: $n$ egy adott pozitív egész, és $n$ matematikus érkezik a szállodába, 1-től $n$-ig számozott szobákba a feladatban leírt módon. Teljes indukcióval belátjuk, hogy ekkor a vendégek $2^{n-1}$-féle sorrendben költözhettek be a szobákba. Ez $n=1$ esetén nyilvánvalóan igaz, hiszen 1 ember csak egyféleképp költözhet be az egyetlen szobába. Tegyük fel, hogy egy adott $n$ pozitív egészre beláttuk, hogy $n$ vendég $2^{n-1}$-féleképpen költözhet be a leírt módon. Ezt felhasználva számláljuk össze, hányféleképpen költözhet be $n+1$ matematikus. Megfigyelhető, hogy az $n+1$. matematikus vagy az egyes számú, vagy az $\left(n+1\right)$-es számú szobába költözhetett be, hiszen ha az $i$. számú szoba $2\le i\le n$-re még szabad az $i$. matematikus érkezésekor, akkor ő ide költözik, és elfoglalja azt, tehát az $\left(n+1\right)$-edik vendég már nem költözhet ide. Az olyan beköltözési sorrendek száma, melyekben az $n+1$. matematikus az $\left(n+1\right)$-es szobába kerül, éppen $2^{n-1}$, hiszen ekkor az első $n$ vendég beérkezési sorrendjére igaz, hogy az első vendég egy tetszőleges, 1-től $n$-ig számozott szobába költözött, a többi vendég pedig, ha tud, a saját sorszámával megegyező szobába, egyébként pedig egy tetszőleges, 1-től $n$-ig számozott szobába kerül, ami éppen az indukciós feltevésünk által megszámolt (azaz az $n$ vendégre vonatkozó) sorrendek száma. Most tekintsünk olyan sorrendeket, melyekben az $n+1$. matematikus az 1-es szobába kerül. Vegyünk egy ilyen sorrendet, és tegyük fel, hogy benne az $i$. vendég költözött az $\left(n+1\right)$-es sorszámú szobába (ahol $1\le i\le n$ a feltevés szerint). Tekintsük azt a sorrendet, melyben minden vendég ugyanabba a szobába kerül, kivéve az $i$. és az utolsó vendéget, mert ezek szobáit felcseréljük (tehát az $i$. vendég az 1-es szobába, az $n+1$. vendég pedig az $\left(n+1\right)$-es szobába kerül). Az így kapott sorrend továbbra is a feltételeknek megfelelő, hiszen $i\ne 1$ esetén az $i$. vendég az eredeti sorrendben sem az $i$. sorszámú szobába kerül, azaz tetszőlegesen választhat szobát, akár az elsőt is, $i=1$ esetén pedig az első vendég egyébként is tetszőlegesen választhat. Az $i$. vendég előtt érkezők továbbra is szabályosan költöznek be, és az utána következők is, hiszen $i<j<\left(n+1\right)$-re a $j$-edik vendég nem költözhet az $\left(n+1\right)$-es számú szobába, mert ekkor az $n+1$. vendégnek nem lenne helye (az 1-es és az $\left(n+1\right)$-es szoba is foglalt lenne már, ami nem lehet). Így tehát minden sorrendhez, melyben az $n+1$. matematikus az 1-es szobába kerül, rendelhető egy olyan, melyben az $\left(n+1\right)$-edikbe kerül. Ugyanez a hozzárendelés visszafelé is elvégezhető: ha az $\left(n+1\right)$-edik matematikus az $\left(n+1\right)$-edik szobába költözik, és az $i$-edik vendég az egyes szobába, akkor az ő szobáikat kicserélve ismét megfelelő sorrendhez jutunk. Könnyen látható, hogy ezek a hozzárendelések egymás inverzei, így azon sorrendek száma, melyekben az $n+1$. matematikus az egyes sorszámú szobába költözik, ugyanannyi, mint melyekben az $\left(n+1\right)$-es számúba, azaz $2^{n-1}$. A kettőt összevetve kapjuk, hogy $n+1$ matematikus éppen $2\cdot 2^{n-1}=2^n$-féleképp költözhet be. Ezzel az indukciós lépést beláttuk. Az eredményt $n=100$ esetén alkalmazva kapjuk, hogy 100 matematikus $2^{99}$-féleképp költözhet be.   Schrettner Jakab (Szegedi Radnóti Miklós Kís. Gimn., 11. évf.)