Problem B. 4942. (March 2018)

B. 4942. The one hundred mathematicians participating in an international combinatorial conference were all housed in the same hotel. The receptionist was originally planning to place them in the order of their arrival in the rooms numbered 1 to 100. However, he forgot to give that instruction to the guest arriving first, who has thus chosen a room at random. So the receptionist instructed all the other guests to take the room with their number in the order of arrivals, or, if that room has already been taken, to select any other room they like. How many possible arrangements of the guests in the rooms are there?

Proposed by A. Faragó and T. Káspári, Paks

(4 pont)

Deadline expired on April 10, 2018.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

97 students sent a solution.
4 points:	52 students.
3 points:	30 students.
2 points:	10 students.
1 point:	5 students.

Problems in Mathematics of KöMaL, March 2018