Eine Nacht in Hilbert´s Hotel

25.08.2006, 03:00

Lazarus

Auf diesen Beitrag antworten »

Eine Nacht in Hilbert´s Hotel

Ich habe folgende Aufgabe und bin mir mit der Lösung nicht sicher.

Zitat:

Spiel (Unendliches Hotel):
Betrachten Sie ein unendliches Hotel mit abzählbar unendlich vielen Zimmern. Ein neuer Gast kommt und fragt, ob Platz auch für ihn ist. Der Direktor des Hotels, ein Mathematiker, sagt: "Alle Zimmer sind besetzt; aber kein Problem, ich finde ein Zimmer auch für Sie."
Wie hat der Direktor das Problem gelöst?
Nach einem Tag kommen abzählbar unendlich viele neue Gäste, aber alle Zimmer sind noch besetzt. Trotzdem hat der Direktor kein Problem, um Zimmer für alle alten und neuen Gäaste zu finden.
Wie hat er das gemacht?

Nun Bedeutet ja abzählbar unendlich gleichmächtig zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ . Folglich gibts es genausoviele Zimmer wie Natürliche Zahlen

Darf ich jetzt einfach alle Gäste die schon da sind mit $\begin{eqnarray*} 1,...,n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ betiteln und sagen der Neuankömmling ist $\begin{eqnarray*} n+1 \end{eqnarray*}$ und da jede Natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ einen Nachfolger $\begin{eqnarray*} n+1 \end{eqnarray*}$ gibt es auch für den $\begin{eqnarray*} n+1 \end{eqnarray*}$ -ten Gast eine Übernachtungsmöglichkeit, eben gerade das $\begin{eqnarray*} n+1 \end{eqnarray*}$ -te Zimmer?

Dieses Spielchen kann man dann ja fortsetzten und verteilt jeweils schön portioniert die am darauffolgenden Tag abzählbar unendlich vielen Neuankömmlinge auf die Zimmer.

Ist das wirklich so simpel, oder hab ich da was übersehn/zuviel gesehn ?
Was mich ein bisschen stört ist die Formulierung "alle Zimmer seien besetzt."
Was meint der Direktor genau damit ?

25.08.2006, 03:13

Ben Sisko

Auf diesen Beitrag antworten »

RE: Eine Nacht in Hilbert´s Hotel

Zitat:

Original von Lazarus
Darf ich jetzt einfach alle Gäste die schon da sind mit $\begin{eqnarray*} 1,...,n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ betiteln

Nein, denn dann wären nur endlich viele Gäste da (auch wenn du n beliebig groß wählen kannst). Anders gesagt: in Zimmer n+1 liegt schon einer Big Laugh

Big Laugh

Da musst du schon einen etwas einfallsreicheren Ansatz finden... Augenzwinkern

Augenzwinkern

(ein sinnvoller Tipp fällt mir nicht ein, ohne es schon zu verraten; wenn du's verraten haben willst, sag Bescheid).

25.08.2006, 03:15

JochenX

Auf diesen Beitrag antworten »

Was heißt denn alle Zimmer sind besetzt?
Bei unendlich vielen Zimmern auf jeden Fall nicht, dass da nur n Gäste sind, sonst wäre ja einiges frei.

Es sind abzählbar unendlich viele Zimmer (also immerhin ganz schön viele), aber auch "genauso viele" Gäste da; also einfach sagen "der bekommt das n+1-te" Zimmer ist nicht möglich, denn die sind ja alle belegt.

Aber die Unendlichkeit macht es möglich, dass hier doch das geschieht, was im endlichen nicht möglich wäre. Eigentlich ist das Hotel voll, aber trotzdem passt noch jede Menge rein.

Tipp:
Setze doch den neuen Gast einfach mal in Zimmer 1.
Wie wäre es, wenn wir dem Gast, den wir gerade aus Zimmer 1 geworfen haben, in Zimmer 2 setzen würden?
Aber wo geht dann der Gast aus Zimmer 2 hin?

Nu haste aber eine Idee für's erste und wenn dann am nächsten Tage noch mehr ankommen, dann denkste dir halt was neues dazu aus.

[damit du dir das ganze besser vorstellen kannst, hier eine kleine Geschichte dazu, die mir in meinem Geiste schwebt: die natürlichen Zahlen machen einen Ausflug und übernachten in diesem Hotel; die Zimmerzuordnung funktioniert einwandfrei, denn die Zimmer sind ja abzählbar unendlich viele; die Zahl i geht einfach ins i-te Zimmer, genau das sagt das ja aus.
Jetzt kommt aber einen Tag später die 0 zu Besuch, die möchte jetzt ein Zimmer haben; zählen wir nicht mehr 1,2,3..., sondern 0,1,2,... können wir die Menge der natürlichen Zahlen mit der Null dazu genauso "abzählen", die Einteilung in die Zimmer geht also wie oben überlegt vonstatten.

Weil es da so schön ist und die natürlichen Zahlen am Telefon so schwärmen, kommen dann am vorletzten Urlaubstag noch die ganzen negativen Zahlen dazu und wollen Zimmer.
Das ist jetzt deine letzte Aufgabe, dass da wieder "unendlich vielen Neuankömmlinge"n ein Zimmer gegeben werden soll.

Unendlich vielen ist in dem Zusammenhang übrigens ungenau; würden alle reellen Zahlen (auch unendlich viele, sogar noch mehr als abzählbar undendlich viele] da rein wollen, müsste selbst der mathematisch hochbewanderte Portier aufstecken.]

So, die Gute-Nacht-Geschichte hat mich müde gemacht.
Ist für mich da noch ein Zimmer in deinem Hotel frei oder muss ich unter der Brücke schlafen?

25.08.2006, 03:31

Lazarus

Auf diesen Beitrag antworten »

Ok, aber wenigstens hatte ich den Knackpunkt erkannt Big Laugh

Big Laugh

also wenn man das Pferd von vorne aufzäumt (wie langweilig) dann seh ich den Punkt, weil hinten raus wirds unendlich, d.h. die können immer weiter schieben.

Kennst du eigentlich die Geschichte "Als die 0 ins Zahlenreich kam" ?
In der Geschichte gings im endeffet darum das die Natürlichen Zahlen ziemlich faul sind und nicht in´s $\begin{eqnarray*} i+1 \end{eqnarray*}$ -te Zimmer Tauschen wollten. Am Ende klapps aber dann doch, naja...

Zurück zum Thema:
Seien die Zimmer durchnummeriert mit $\begin{eqnarray*} i \end{eqnarray*}$ , die Positiven ganzen Zahlen und die $\begin{eqnarray*} 0 \end{eqnarray*}$ mit $\begin{eqnarray*} n \end{eqnarray*}$ sowie die negativen ganzen Zahlen mit $\begin{eqnarray*} k \end{eqnarray*}$ .
Wenn jetzt alle Negativen Zahlen zu Besuch kommen, darf ich dann jeder Zahl die in Zimmer $\begin{eqnarray*} i \end{eqnarray*}$ ist einfach das Zimmer $\begin{eqnarray*} 2i \end{eqnarray*}$ zuordnen (somit jeder Zahl $\begin{eqnarray*} n \end{eqnarray*}$ die Zimmernummer $\begin{eqnarray*} i=2n+2 \end{eqnarray*}$ und jeder negativen Zahl $\begin{eqnarray*} k \end{eqnarray*}$ das Zimmer $\begin{eqnarray*} i=2\sqrt{k^2}-1 \end{eqnarray*}$ gesetzten Falles $\begin{eqnarray*} i\geq 1 \end{eqnarray*}$

(Vom Gedanken isses ja klar, die Formulierung ist jetzt weng kompliziert geworden weil du ja unbedingt die Null mit dabei haben wolltest, sonst wäre mir was leichteres eingefallen)

Aber insgesamt isses schon ziemlich spät, vermutlich is deswegen auch kein wirkliches nachdenken mehr möglich.
Daher verschieb ich das einfach mal auf morgen und biete dir gerne ein Zimmer deiner Wahl an, allerdings musst du die Zuordnungsvorschrift für die übrigen zimmer der nachfolgenden zahlen selbst definieren, da ich etz schlafen geh.

mit nächtlichen dankesgrüßen
uli

25.08.2006, 03:47

Ben Sisko

Auf diesen Beitrag antworten »

Grundsätzliche Idee ist richtig. Bisherige Gäste von i nach 2i. Für die anderen würd ich keine Vorschrift formulieren, sondern sagen, sie sollen sich ein freies Zimmer nehmen, sind ja genug da Big Laugh

Big Laugh

25.08.2006, 13:09

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Ben Sisko
Bisherige Gäste von i nach 2i.

Genau so geht's. Danach sind alle Zimmer mit ungeraden Nummern frei. Das sind abzählbar unendlich viele Zimmer und damit paßt der Bus mit den abzählbar unendlich vielen Gästen rein.

Die Geschichte geht aber noch weiter:
In derselben Nacht fahren abzählbar unendlich viele Busse mit jeweils abzählbar unendlich vielen Gästen vor das Hotel und jeder will natürlich auch noch ein Zimmer. Es wird berichtet, daß der Portier laut schreiend "Das halt ich nicht aus!" davon lief. Aber zum Glück wußte ein findiger Mathematiker auch hierfür einen Lösungsweg. Augenzwinkern

Augenzwinkern

Anzeige

25.08.2006, 13:58

Lazarus

Auf diesen Beitrag antworten »

Also ich vermute ja, dass der Grund für dieses Vollkommend Überlaufene Hotel darin liegt, dass die Zimmer so billig sind, sagen wir 1 € pro Nacht.
Wenn nun schon zwei Nächte lang unendlich viele Gäste die Miete gezahlt haben dann sollte der Hoteldirektor einfach sagen "wir sind voll, ich hab schon unendlich viel Geld" (ungefähr so wie Dagobert Duck, Klaas Klever und McMoneysack zusammen Big Laugh

Big Laugh

)

Oder eine (zugegeben bisschen fiese) Methode die alle loszuwerden (beginnend bei der 0):
Die 0 kommt an, man sagt ihr "ganz hinten" sei noch eines frei.
die 0 wird loslaufen aber niemals ankommen und vorallem niemals zurückkommen um sich zu beschweren, somit Problem gelöst.
Mit den ganzen anderen sollte man ähnlich verfahren allerdings sollte man ein Schild aufstellen damit mans nicht abzählbar abzählbar-unendlich oft sagen muss.

(Dadurch dass ich das etz geschrieben hab hatte ich zeit zum Nachdenken Augenzwinkern

Augenzwinkern

)

Darum mal ein versuch der Lösung.

Ich nummerier die ankommenen Busse mit $\begin{eqnarray*} q \in \mathbb N \end{eqnarray*}$ durch.
Die Leute in den Busen mit $\begin{eqnarray*} m\in \mathbb N \end{eqnarray*}$ .
Ferner seien die Zimmer weiterhin $\begin{eqnarray*} i\in \mathbb N \end{eqnarray*}$ .
Nun gilt wieder für alle Leute auf den Zimmer die Zuordnungsvorschrift $\begin{eqnarray*} i\mapsto 2i \end{eqnarray*}$ sodass alle ungeraden Zahlen wieder frei werden.

[Das ist übrigends einer der Gründe warum das Hotel so billig ist: dass man annähernd jede Nacht umziehen muss! Ein anderer ist die unendlich-lange Schlange am Frühstücksbuffet]

Sei nun $\begin{eqnarray*} \mathbb P \end{eqnarray*}$ die Menge aller Primzahlen und $\begin{eqnarray*} p_n\in \mathbb P \end{eqnarray*}$ bezeichne die $\begin{eqnarray*} n \end{eqnarray*}$ -te Primzahl. Beispielsweise $\begin{eqnarray*} p_5=11 \end{eqnarray*}$
Die dann frei werdenten Zimmer (alle ungeraden Zahlen) besetzt man folgendermaßen:
Ins Zimmer $\begin{eqnarray*} 1 \end{eqnarray*}$ kommt LOED. in die Zimmer $\begin{eqnarray*} 3 \end{eqnarray*}$ bis $\begin{eqnarray*} 3^m \end{eqnarray*}$ kommen alle Leute aus dem Bus $\begin{eqnarray*} 1 \end{eqnarray*}$ , Aus dem Bus $\begin{eqnarray*} 2 \end{eqnarray*}$ kommen alle in die Zimmer $\begin{eqnarray*} 5 \end{eqnarray*}$ bis $\begin{eqnarray*} 5^m \end{eqnarray*}$ , und so weiter.

Sei nun $\begin{eqnarray*} q_m \end{eqnarray*}$ der $\begin{eqnarray*} m-te \end{eqnarray*}$ Gast aus dem $\begin{eqnarray*} q \end{eqnarray*}$ -ten Bus dann ergibt sich die Zuordnungsvorschrift $\begin{eqnarray*} q_m \mapsto p_{q+1}^m \end{eqnarray*}$

Ich kann da keinen Denkfehler mehr drinn finden .. bedeutet dass, dass es stimmt ?
Servus

25.08.2006, 14:10

JochenX

Auf diesen Beitrag antworten »

Erstmal noch ein paar meiner Buchstaben zum Vorherigen:

Zitat:

Kennst du eigentlich die Geschichte "Als die 0 ins Zahlenreich kam" ?

nein, klingt ganz ähnlich; sollte ich etwa nur eine abgekupferte Geschichte erfunden haben?

Warum schreibst du für negative Zahlen k $\begin{eqnarray*} \sqrt{k^2} \end{eqnarray*}$ statt einfach $\begin{eqnarray*} -k \end{eqnarray*}$ ? Wäre das nicht etwas einfacher?

Zitat:

(Vom Gedanken isses ja klar, die Formulierung ist jetzt weng kompliziert geworden weil du ja unbedingt die Null mit dabei haben wolltest, sonst wäre mir was leichteres eingefallen)

Dann formuliere wie du das leichter kannst OHNE die Null.
Nach der ersten Formulierung steckste die 0 dann einfach wieder mit dem selben Trick wie oben in Zimmer 1.
Was ich dir hier übrigens auch empfehle ist, die Zuordnungsvorschrift gar nicht unbedingt immer anzugeben, sondern einfach aufzuzählen: (0,1,-1,2,-2,3,-3,....) und jeder sieht die Abzählbarkeit und weiß auch, wie es weiter geht.
Bei komplexeren Beispielen kann das nämlich sehr schwer werden die Bijektion Menge -> natürliche Zahlen zu finden.

Deine Zuordnung der vielen Busse von Klarsoweit ist MÖGLICH, um alle Gäste unterzubringen.
Interessanterweise findest du damit keine Bijektion, sondern eine ECHTE Injektion deiner Menge (Vereinigung aller Mengen) in die natürlichen Zahlen, d.h. es bleiben Zimmer FREI.
Eine weitere Möglichkeit, die Leute unterzubringen, und dabei alle Zimmer zu belegen, siehe hier: http://de.wikipedia.org/wiki/Cantor-Diagonalisierung.
Ein wenig umdenken musst du aber noch.

Übrigens danke für das Zimmer 1, vermutlich ist der Weg zum Klo für mich damit auch am kürzesten.
Guter Service hier.

25.08.2006, 14:25

Lazarus

Auf diesen Beitrag antworten »

Mich hat diese "diese Zahl die in Zimmer i ist wird ..." gestört.

Aber es geht ja eigentlich auch direkt:
die natürlichen Zahlen und die 0 seine $\begin{eqnarray*} n \end{eqnarray*}$
die Negativen ganzen Zahlen $\begin{eqnarray*} z \end{eqnarray*}$ .

$\begin{eqnarray*} n&\mapsto& 2n+2\\z&\mapsto& -2z-1 \end{eqnarray*}$

Kurz nach 3 mit ein bisschen was im Tee fällt denken eben etwas schwerer Augenzwinkern

Augenzwinkern

Zur Injektion: es bleibt nur das Zimmer 1 frei oder hab ich mich verzählt ? Dann behaupt ich jetzt ich hab das extra gemacht, damit du eines bekommst!

Zur direkten Aufzählung: Hammer

Hammer

Aber euch vielen Dank für die nette und kurzweilige Unterhaltung sowie Hilfe.

servus

25.08.2006, 14:42

JochenX

Auf diesen Beitrag antworten »

Zitat:

Zur Injektion: es bleibt nur das Zimmer 1 frei

du belegst Zimmer 1 mit mir und sämtliche Zimmer, die Primzahlpotenzen sind.
Zimmer 6, 8, 10.... bleiben alle frei.

smile

smile

25.08.2006, 14:44

Lazarus

Auf diesen Beitrag antworten »

Ne da sind ja Gäste von vorher drinn.

Zitat:

Nun gilt wieder für alle Leute auf den Zimmer die Zuordnungsvorschrift $\begin{eqnarray*} i\mapsto 2i \end{eqnarray*}$ sodass alle ungeraden Zahlen wieder frei werden.

\\edit: wobei man sagen muss ich fang erst an mit primzahlpotenzen von 3, da 2 (und alle potenzen von 2) als gerade Zahlen belegt werden.

Deshalb dieses $\begin{eqnarray*} q_{m}\mapsto p_{q+1}^m \end{eqnarray*}$ damit auch für den ersten bus erst die zweite Primzahl (also die 3) benutzt wird.

25.08.2006, 15:11

JochenX

Auf diesen Beitrag antworten »

Und wer sitzt in Zimmer 15?
das ist ungerade, aber keine Primzahlpotenz; oder habe ich dein kompliziertes Verteilungsverfahren imme noch nicht verstanden?

schau dir mal die Anordnung der positiven rationalen Zahlen im Link oben an.
Eine Zahl a/b dann als (a,b) aufzufassen und damit das b-te Element aus der a-ten Menge zu meinen ist dann der letzte kleine Schritt.
Ich glaube, damit fährst du einfacher als mit deinem komplizierten Zuordnungsverfahren.

25.08.2006, 16:41

Lazarus

Auf diesen Beitrag antworten »

ne stimmt, das hatte ich nicht bedacht.

Ich hatte den Link mir schon durchgelesen, bin dann auch auf eine ähnliche Methode gekommen:

den Bruch $\begin{eqnarray*} \frac{a}{b} \end{eqnarray*}$ so zu interpretieren:
$\begin{eqnarray*} a \end{eqnarray*}$ sei der Bus aus dem jemand kommt, bei a=1 ist es das Hotel.
$\begin{eqnarray*} b \end{eqnarray*}$ ist der Sitzplatz bzw das Zimmer in dem jemand saß/wohnte.

Jetzt dann einfach der Reihe nach durchgehen mit dem Diagonalisierungsverfahren und fertig.

Ich hatte mir gleich wo du den Link gezeigt hast diese Methode gedacht, aber wollte erst meine eigenen retten .. aber ich glaub das geht nicht wirklich, wenn alle Zimmer belegt sein sollen, bzw wird noch aufwendiger.
Beheben liese sich dass dadurch dass man bestimmten Bussen dann zusammengesetzte ungerade Zahlen zuteilt. Muss man halt nur ne systematik finden mit der sich das in eine ordentliche Zuordnungsvorschrift packen lässt, und da hast du natürlich wieder recht:
Das artet in gaaanz viel Arbeit aus und ist zugegebenermaßen ziemlich umständlich.

ok... dank dir Augenzwinkern

Augenzwinkern

servus

25.08.2006, 17:09

JochenX

Auf diesen Beitrag antworten »

Doch, du kannst deine Methode natürlich retten, allerdings wird es dann schwer, dazu eine Funktionsvorschrift wirklich anzugeben.

Du hast nachher abzählbar viele Gäste, die die Zimmer belegen, allerdings sind einige Zimmer frei.
Lass also einfach jeden soweit wie möglich "aufrutschen" (dabei entstehen tollerweise keine freien Zimmer "am Ende") und schon hast du dein Problem gelöst.

25.08.2006, 23:26

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von Lazarus
Sei nun $\begin{eqnarray*} \mathbb P \end{eqnarray*}$ die Menge aller Primzahlen und $\begin{eqnarray*} p_n\in \mathbb P \end{eqnarray*}$ bezeichne die $\begin{eqnarray*} n \end{eqnarray*}$ -te Primzahl. Beispielsweise $\begin{eqnarray*} p_5=11 \end{eqnarray*}$
Die dann frei werdenten Zimmer (alle ungeraden Zahlen) besetzt man folgendermaßen:
Ins Zimmer $\begin{eqnarray*} 1 \end{eqnarray*}$ kommt LOED. in die Zimmer $\begin{eqnarray*} 3 \end{eqnarray*}$ bis $\begin{eqnarray*} 3^m \end{eqnarray*}$ kommen alle Leute aus dem Bus $\begin{eqnarray*} 1 \end{eqnarray*}$ , Aus dem Bus $\begin{eqnarray*} 2 \end{eqnarray*}$ kommen alle in die Zimmer $\begin{eqnarray*} 5 \end{eqnarray*}$ bis $\begin{eqnarray*} 5^m \end{eqnarray*}$ , und so weiter.

Sei nun $\begin{eqnarray*} q_m \end{eqnarray*}$ der $\begin{eqnarray*} m-te \end{eqnarray*}$ Gast aus dem $\begin{eqnarray*} q \end{eqnarray*}$ -ten Bus dann ergibt sich die Zuordnungsvorschrift $\begin{eqnarray*} q_m \mapsto p_{q+1}^m \end{eqnarray*}$

Die Funktionsvorschrift am Ende ist in Ordnung, siehe Jochens Kommentare dazu. Aber die Aufzählung

Zitat:

in die Zimmer $\begin{eqnarray*} 3 \end{eqnarray*}$ bis $\begin{eqnarray*} 3^m \end{eqnarray*}$ kommen alle Leute aus dem Bus $\begin{eqnarray*} 1 \end{eqnarray*}$ , Aus dem Bus $\begin{eqnarray*} 2 \end{eqnarray*}$ kommen alle in die Zimmer $\begin{eqnarray*} 5 \end{eqnarray*}$ bis $\begin{eqnarray*} 5^m \end{eqnarray*}$ , und so weiter.

kannst du so nicht machen, da du ja m nur als Zählindex verwendest, du kannst mit m nicht die Anzahl der Passagiere in einem Bus angeben (sind ja abzählbar unendlich viele) und deswegen auch nicht die Zimmer 5 bis 5^m für Bus 2 reservieren. Was wäre 5^m.

Wie gesagt, das darunter ist i.O., aber wollte den Teil nicht so stehen lassen.

Gruß vom Ben

26.08.2006, 13:33

Lazarus

Auf diesen Beitrag antworten »

Da hast du recht, aber das liegt an der Formulierung. Danke dass du mich darauf hinweist, ist echt schlampig formuliert!

Es ist so gemeint das alle $\begin{eqnarray*} 5^m \end{eqnarray*}$ für beliebige $\begin{eqnarray*} m \in \mathbb N \end{eqnarray*}$ für Bus 2 reserviert sind.

@Jochen:
Ja, aber du weisst doch ich bin Fan von expliziten Zuordnungsvorschriften Augenzwinkern

Augenzwinkern

Also dank euch beiden !
Servus
uli

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »