A B. 4942. feladat (2018. március)

B. 4942. A nemzetközi kombinatorikai konferenciára érkező száz matematikust egy szállodában helyezik el, ahol a szobák egytől százig vannak megszámozva. A recepciós azt tervezi, hogy a matematikusokat érkezésük sorrendjében az adott sorszámú szobába küldi. Az elsőnek érkező vendégnek viszont elfelejti a megfelelő utasítást megadni, így ő a szobák közül véletlenszerűen választ egyet. Végül a recepciós a többieknek azt az utasítást adja, hogy az érkezési sorszámuknak megfelelő szobát egyesével foglalják el; illetve ha az már foglalt, akkor válasszanak a szabad szobák közül egyet tetszés szerint. Hányféleképpen költözhettek be a szobákba a vendégek?

Javasolta: Faragó András és Káspári Tamás (Paks)

(4 pont)

A beküldési határidő 2018. április 10-én LEJÁRT.

Megoldás. Tekintsük azoknak a vendégeknek a sorszámait, akik a (sorszámuk szerinti) szobájukat foglaltan találták. Ezek a sorszámok a \(\displaystyle \{2,3,\dots,100\}\) egy részhalmazát alkotják. Megmutatjuk, hogy mind a \(\displaystyle 2^{99}\) darab részhalmaz pontosan egyféle beköltözésnél állhat elő. Tegyük fel, hogy a részhalmaz elemeire \(\displaystyle 2\leq a_1<a_2<\dots<a_n\leq 100\). Az \(\displaystyle a_1\) sorszámú szobát csak az 1-es sorszámú vendég foglalhatta el, hiszen az \(\displaystyle a_1\)-nél kisebb sorszámúak közül az elsőnek érkező vendéget leszámítva mindenki a saját szobájába került. Az \(\displaystyle a_2\) sorszámú szobát ehhez hasonlóan csak az \(\displaystyle a_1\)-ediknek érkező vendég foglalhatta el, hiszen a nála kisebb sorszámúak közül csak az elsőnek érkező és az \(\displaystyle a_1\)-edik vendég került másik szobába, de azt már tudjuk, hogy az első vendég az \(\displaystyle a_1\)-edik szobában van. és így tovább, az \(\displaystyle a_3\)-as szobába az \(\displaystyle a_2\)-edik vendég, az \(\displaystyle a_4\)-esbe az \(\displaystyle a_3\)-adik vendég, ..., végül az \(\displaystyle a_{n}\)-es szobába az \(\displaystyle a_{n-1}\)-es vendég került. Az \(\displaystyle a_{n}\)-edik vendég pedig ezek szerint az 1-es szobát választotta (hiszen a nála nagyobb sorszámúak mind a sajátjukba kerültek). Az \(\displaystyle 1,a_1,a_2,\dots,a_n\) számoktól különböző sorszámú vendégek pedig mind a sorszámuk szerinti szobába kerültek. Tehát valóban pontosan egyféleképpen kaphattuk az \(\displaystyle \{a_1,a_2,\dots,a_n\}\) részhalmazt. (Ez \(\displaystyle n=0\) esetén is igaz, vagyis, ha senki nem találta foglaltan a neki szánt szobát, ekkor ugyanis a \(\displaystyle 2,3,\dots,100\) sorszámú vendégek mind a sorszámuk szerinti szobában vannak, így az első vendég is.)

Tehát \(\displaystyle 2^{99}\)-féleképpen költözhettek be a matematikusok a szobákba.

Statisztika:

97 dolgozat érkezett.
4 pontot kapott:	52 versenyző.
3 pontot kapott:	30 versenyző.
2 pontot kapott:	10 versenyző.
1 pontot kapott:	5 versenyző.

A KöMaL 2018. márciusi matematika feladatai