Hilberts Hotel und die Handtücher

          Die Lösung steht im unteren Teil der Seite.

Hilberts Hotel ist ein unter Mathematikern gut bekanntes Haus. Es hat abzählbar unendlich viele Zimmer, nummeriert mit den natürlichen Zahlen  1, 2, 3, ...

David Hilbert hat dieses Hotel konstruiert, um besondere Eigenschaften nicht-endlicher Mengen zu demonstrieren. Ist beispielsweise das Hotel voll belegt, so kann ein neuer Gast dennoch aufgenommen werden, indem alle anderen Gäste ein Zimmer aufrücken, also von Zimmer  n  nach Zimmer  n+1  umziehen, und so Zimmer  1  für den neuen Gast freimachen. Ganz ähnlich verfährt man, wenn mehrere, aber endlich viele neue Gäste erscheinen. Aber auch die Ankunft eines Reisebusses mit abzählbar unendlich vielen neuen Gästen bringt die Rezeption des voll belegten Hotels nicht in Verlegenheit. Die bereits eingecheckten Gäste ziehen jeweils von ihrem Zimmer mit der Nummer  n  ins Zimmer  2n  um und machen alle Zimmer mit ungeraden Nummern frei, also unendlich viele.

Hier kommt eine neue Episode über Hilberts Hotel.

Im Winter hatte das Hotel wegen Renovierung geschlossen und öffnet wieder zu Ostern. Die Nachfrage ist sehr groß; das Hotel ist für lange Zeit ausgebucht. Die Zimmer mit den Nummern  1  bis  1000  sind für Langzeitgäste reserviert (dort gibt es die beste Aussicht). Das sind Gäste, die mindestens ein Jahr bleiben. Die Beliebtheit von Hilberts Hotel zeigt sich auch darin, dass diese Zimmer nie leer stehen. Im Gegenteil: Viele Langzeitgäste müssen mit höheren Zimmernummern vorliebnehmen.

Nun muss erklärt werden, wie das Hotel mit dem Handtuchwechsel verfährt. Es gibt nur blaue und gelbe Handtücher. Jedes Zimmer behält seine Handtuchfarbe vom Einzug der Zimmergäste bis zu deren Auszug. Dann aber wird die Handtuchfarbe für die nächsten Gäste in diesem Zimmer getauscht, um zu verhindern, dass irrtümlich alte Handtücher weiterverwendet werden. Bei der Neueröffnung zu Ostern erhalten alle Zimmer blaue Handtücher.

Hilberts Hotel erweist sich als so beliebt wie seit eh und je. Schon am nächsten Abend nach der Neueröffnung steht wieder ein Bus mit abzählbar unendlich vielen Gästen vor der Tür. Kein Problem: Man wendet Hilberts Vorgehensweise an; alle schon eingecheckten Gäste ziehen von Zimmer  n  nach Zimmer  2n  um und machen die Zimmer mit ungeraden Nummern frei. In die Zimmer  1, 3, 5, ... ,997, 999  ziehen natürlich wieder neue Langzeitgäste ein.

Am nächsten Tag spricht der Junior-Manager den Manager an. "Heute Abend kommen schon wieder neue Gäste. Wir mussten gestern in allen Zimmern die Handtuchfarbe wechseln. Auf Dauer ist das ziemlich viel Aufwand."  -  "Klar, aber was können wir tun?"  -  "Ich hätte da eine Idee: Wir lassen nur die Gäste mit den geraden Zimmernummern aufrücken, also  2 → 4, 4 → 8  usw. Dann kommen alle neuen Gäste unter, auch wenn wieder abzählbar unendlich viele kommen. Und wir müssen nur in der Hälfte der Zimmer die Handtuchfarbe wechseln."  -  "Gute Idee, so machen wir's."

Da sich abzeichnet, dass jeden Abend ein Bus mit abzählbar unendlich vielen Gästen ankommt, denkt der Junior-Manager auch am folgenden Tag, also nach der dritten Nacht, weiter nach. Er sorgt dafür, dass am Abend nur noch die Gäste in den Zimmern mit den durch  3  teilbaren Nummern umziehen müssen, also  3 → 6, 6 → 12  usw. Es werden die Zimmer  3, 9, 15  usw. für die neuen Gäste frei, und der Handtuch-Farbwechsel hat sich auf ein Drittel reduziert (glaubt zumindest das Management - man kann das vielleicht anzweifeln, da ja immer noch unendlich viele Farbwechsel nötig sind).

Da die Idee des Junior-Managers Anklang findet und für mehr Ruhe im Hotel sorgt, weitet das Management von Abend zu Abend das Verfahren aus: Am Abend nach der  m-ten Nacht werden wieder abzählbar unendlich viele neue Gäste erwartet; man lässt die Gäste in den Zimmern mit durch  m  teilbaren Nummern schon nachmittags zur doppelten Zimmernummer aufrücken, tauscht die Handtuchfarben in diesen Zimmern und kann abends alle neuen Gäste aufnehmen.

Nach  100  Nächten inspiziert der Hoteldirektor C. Antor sein Hotel, und zwar gegen Abend, kurz bevor die neuen (natürlich wieder abzählbar unendlich vielen) Gäste eintreffen. In welchen Zimmern mit den Nummern  1  bis  100  findet er blaue Handtücher?

Die Lösung lässt sich durch Ausprobieren herausfinden. Aber wie kann man das Problem verallgemeinern (also unabhängig machen von der Zahl  100) ?  Wie lässt sich die allgemeine Lösung beweisen?

Lösung

Zur Zählung der Tage: Der Tag  1  sei der Tag mit dem ersten Handtuchfarbwechsel, also nach der ersten Nacht nach Ankunft der ersten Gäste. Die Inspektion von C. Antor findet am Tag  100  statt, und zwar nach dem  100. Farbwechsel.

Wir betrachten als einführendes Beispiel den "Zwischenstand" für Zimmer #14  am  21. Tag. Ausgehend von der Anfangsausstattung mit blauen Handtüchern, wurde in diesem Zimmer die Handtuchfarbe getauscht an den Nachmittagen der Tage  1, 2, 7  und  14 ,  denn das sind die Teiler von  14 .  Also ist die Handtuchfarbe wieder blau.

Man kann nun leicht eine Excel-Tabelle mit  0 = blau  und  1 = gelb  anlegen, die berechnet, wie die Handtuchwechsel ablaufen. Wenn der Direktor am Abend des  9. Tages die ersten  9  Zimmer inspizieren würde, sähe die Tabelle so aus:

  Tag 1 2 3 4 5 6 7 8 9
Zi.#
  1   1 1 1 1 1 1 1 1 1
  2   1 0 0 0 0 0 0 0 0
  3   1 1 0 0 0 0 0 0 0
  4   1 0 0 1 1 1 1 1 1
  5   1 1 1 1 0 0 0 0 0
  6   1 0 1 1 1 0 0 0 0
  7   1 1 1 1 1 1 0 0 0
  8   1 0 0 1 1 1 1 0 0
  9   1 1 0 0 0 0 0 0 1

Wenn man größere Tabellen anlegt, stellt sich sofort eine Vermutung ein: Alle Handtücher sind blau, außer in den Zimmern mit quadratischer Nummer. Für  100  Tage und  100  Zimmer findet man auf diese (empirische) Weise tatsächlich heraus, dass nur in den Zimmern  1, 4, 9, 16, 25, 36, 49, 64, 81  und  100  gelbe Handtücher hängen.

Verallgemeinerung der Problemstellung:
Welche Handtuchfarben findet man am Abend des  n-ten Tages in den Zimmern mit den Nummern  1  bis  n  vor?
Hier bekommen die Langzeitgäste eine besondere Bedeutung. Denn wir müssen uns sowohl auf  n ≤ 1000  beschränken, weil in den übrigen Zimmern zusätzliche Farbwechsel durch Auszug von Gästen vorkommen können, als auch auf  n ≤ 365 ,  weil manche Langzeitgäste nur genau ein Jahr bleiben könnten. Also modifizieren wir die allgemeine Problemstellung etwas:

Das Hotel beherbergt in den Zimmern  1  bis  N  nur Langzeitgäste; das sind Gäste, die mindestens  T  Tage im Hotel bleiben. Sei  n ≤ min{N,T} .
Welche Handtuchfarben findet man am Abend des  n-ten Tages in den Zimmern mit den Nummern  1  bis  n  vor?

Wie oft wurde in diesen Zimmern die Handtuchfarbe gewechselt? Offenbar so oft wie die Anzahl der Teiler der Zimmernummer. Das wurde bereits für das Zimmer #14  beispielhaft gezeigt. Zur Bestimmung der Anzahl der Teiler einer natürlichen Zahl  k  ist es hilfreich, sich die Primfaktorzerlegung von  k  anzusehen.  k  möge  s  Primfaktoren  p₁ ... p_s  haben;  p_r  komme  h_r-mal als Faktor vor  (r = 1 ... s).

k = Π_r = 1..s p_r^h_r

Die Teiler von  k  weisen die einzelnen Primfaktoren jeweils  0-  bis  h_r-mal auf. Kommt jeder Primfaktor  0-mal vor, so handelt es sich um den Teiler  1 ;  kommt jeder Primfaktor  h_r-mal vor, so handelt es sich um den Teiler  k .  Für jedes  p_r  gibt es also  1 + h_r  Möglichkeiten des Auftretens in einem Teiler. Die Anzahl aller Teiler wollen wir mit  τ(k)  bezeichnen. Wir erhalten:

τ(k)= Π_r = 1..s(1+h_r)

Von  τ(k) ist für uns nur interessant, ob es sich um eine gerade oder eine ungerade Zahl handelt. Im ersten Fall hat es im Zimmer #k  eine gerade Anzahl von Farbwechseln gegeben, und nach  n  Tagen findet man dort blaue Handtücher vor. Im zweiten Fall findet man gelbe Handtücher vor.

Nun ist  τ(k) ein Produkt natürlicher Zahlen und somit genau dann ungerade, wenn alle Faktoren ungerade sind. Dies bedeutet, dass die  h_r  alle gerade sind. In der Produktdarstellung von  k  sind dann alle  p_r^h_r  Quadratzahlen, also auch  k  selbst.

Wir formulieren zuerst das zahlentheoretische Ergebnis:

Nur Quadratzahlen haben eine ungerade Anzahl von Teilern; alle anderen natürlichen Zahlen haben eine gerade Anzahl von Teilern.

Die Antwort auf die allgemeine Problemstellung mit  n ≤ min{N,T} lautet also genau so, wie wir zu Beginn durch die iterative Berechnung für  n = 100  vermutet hatten:

Am Abend des  n-ten Tages sind die Handtücher in den Zimmern bis  #n  blau, mit Ausnahme der quadratischen Zimmernummern, dort hängen gelbe Handtücher.

Publiziert 2015-12-28          Stand 2014-07-20

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem