Re: Ein Rätsel mit unendlich vielen Verdammten ...
Verfasst: 10. Mai 2020, 19:24
Problemstellung
Unendlich viele zum Sünder erhalten die Chance, der ewigen Verdammnis zu entgehen.
Jedem Sünder mit Nummer n wird ein Hut mit der Farbe fn - schwarz oder weiß - aufgesetzt. Jeder Sünder n sieht sämtliche Hutfarben f1, f2, ... fn-1, fn+1, ... mit Ausnahme der eigenen fn. Die Sünder können nicht untereinander kommunizieren. Sie müssen auf ein Zeichen hin gleichzeitig ihre eigene Hutfarben nennen. Wer richtig rät, wird gerettet, wer falsch rät, fällt der ewigen Verdammnis anheim.
Die Sünder hatten jedoch die Gelegenheit, sich vorher auf eine Strategie zu einigen. Blindes Raten würde im Mittel die Hälfte retten, die andere Hälfte ins ewige Verderben führen.
Existiert eine bessere Strategie als blindes Raten?
Wieviele Sünder können sich retten?
Lösung
Fast alle Sünder - d.h. alle bis auf endlich viele - können sich retten.
Beweis
Sei f = (fn) mit n ∈ N und fn = 0,1 eine Hutfolge.
Sei F = {f(r); r ∈ R} die (überabzählbare) Menge aller Hutfolgen
Nun definieren wir eine Äquivalenzrelation von Hutfolgen f ~ g: f sei äquivalent zu g, genau dann, wenn sich f und g nur in höchstens endlich vielen Stellen unterscheiden. Umgekehrt sind zwei Folgen nicht äquivalent, wenn sie sich in unendlich vielen Stellen unterscheiden.
Eine Äquivalenzklasse [f] wird dann definiert als Teilmenge von F mit
[f] = {f(r) ∈ F: f(r) ~ f} ⊂ F
d.h. in [f] sind alle f(r) enthalten, die untereinander und insbs. zu einem (beliebigen) Repräsentanten f äquivalent sind.
Eine Teilmenge S = {σ ∈ F} ⊆ F nennt man ein Repräsentantensystem von F bzgl. ~, wenn S genau ein σ ∈ [f] je [f] enthält.
Damit haben wir die Lösung.
Die Sünder legen ihre Strategie fest:
1a) Sie führen zunächst die o.g. Zerlegung aller möglichen Hutfolgen F in die genannten Äquivalenzklassen [f] durch.
1b) Sie einigen sich auf ein Repräsentantensystem S für F bzgl. ~.
Nun werden sie aufgefordert, ihre eigene Hutfarbe zu erraten:
2a) Da jeder Sünder alle Hutfarben bis auf die eigene kennt, ist dies gleichbedeutend damit, dass jeder die vollständige Folge zu erraten hat; nennen wir diese f°. Nun kann jeder Sünder aus den ihm bekannten Hutfarben bereits die Äquivalenzklasse [f°] ermitteln, zu der f° gehört: er sieht bzw. kennt z.B. (001…?...) wobei das ? für die eigene Hutfarbe steht. Damit weiß er jedoch, dass z.B. (001…?...) ~ (001…0...) ~ (001…1...) ~ f°. Damit kennt jeder Sünder nun auch den zuvor festgelegten Repräsentanten σ ~ f° aus [f°]. Somit ist [f°] und σ aus der Kenntnis der sichtbaren Hutfarben für jeden Sünder eindeutig ableitbar.
2b) Der Sünder mit Nummer n rät (≟) seine eigene Hutfarbe als n-te Stelle aus diesem σ, d.h. f°n ≟ σn, also z.B.: n rät (001… σn ...). Da in [f°] nur Folgen enthalten sind, die sich an endlich vielen Stellen von f° unterscheiden, unterscheidet sich auch der zuvor festgelegte Repräsentant σ ~ f° aus [f°] nur an endlich vielen Stellen von f°. Und damit raten auch nur endlich viele Sünder falsch, nämlich diejenigen, die das Pech haben, dass ihre Position n gerade den Stellen fn entspricht, an denen sich σ von f° unterscheidet, d.h. σn ≠ f°n.
◼
Wozu benötigt man das Auswahlaxiom?
Man benötigt eine injektive Funktion c, die für alle möglichen Folgen f ∈ F den jeweiligen Repräsentanten σ[f] ∈ [f] zuordnet, d.h.
c: F → S
c(f) = σ[f] ⟺ σ ~ f
mit
f ~ g ⟹ c(f) = c(g)
D.h. egal welches f man in die Funktion hineinsteckt, man erhält immer das eindeutig definierte σ[f] je [f].
Dies kann jeder Sünder durchführen, da er zwar nicht f° kennt, jedoch ein f ~ f°, das sich in höchstens einer (seiner) Stelle von f° unterscheidet, d.h. er ermittelt das σ ~ f° mittels σ = c(f ~ f°) und rät f°n ≟ σn = cn(f).
Die Menge der Verdammten entspricht dann
V = {n ∈ N: σn ≠ f°n}
|V| < ∞
Dies kann man auch wie folgt interpretieren:
Sei
F/~ = {[f]}
die Menge aller Äquivalenzklassen von F bzgl. ~.
Damit ist die Definition von c äquivalent zu einer Bijektion
c: F/~ → S
c[f] = σ[f]
D.h. die Funktion c wählt aus jeder Äquivalenzklassen [f] ∈ F/~ genau ein σ[f] aus. Die Existenz einer derartigen Auswahlfunktion c für eine unendliche Menge F/~, deren Elemente unendliche Mengen [f] sind, wird durch das Auswahlaxiom sichergestellt.
Für das vorliegende Problem – die Frage nach der Existenz einer Strategie, die alle außer endliche viele Sünder rettet – sind die Details von c irrelevant; die pure Existenz von c stellt die Lösung σ ~ f° sicher. Der eigentliche Kern der Lösung ist die Anwendung der speziellen Äquivalenzrelation f ~ g ⟺ fn ≠ gn für höchsten endlich viele n.
Unendlich viele zum Sünder erhalten die Chance, der ewigen Verdammnis zu entgehen.
Jedem Sünder mit Nummer n wird ein Hut mit der Farbe fn - schwarz oder weiß - aufgesetzt. Jeder Sünder n sieht sämtliche Hutfarben f1, f2, ... fn-1, fn+1, ... mit Ausnahme der eigenen fn. Die Sünder können nicht untereinander kommunizieren. Sie müssen auf ein Zeichen hin gleichzeitig ihre eigene Hutfarben nennen. Wer richtig rät, wird gerettet, wer falsch rät, fällt der ewigen Verdammnis anheim.
Die Sünder hatten jedoch die Gelegenheit, sich vorher auf eine Strategie zu einigen. Blindes Raten würde im Mittel die Hälfte retten, die andere Hälfte ins ewige Verderben führen.
Existiert eine bessere Strategie als blindes Raten?
Wieviele Sünder können sich retten?
Lösung
Fast alle Sünder - d.h. alle bis auf endlich viele - können sich retten.
Beweis
Sei f = (fn) mit n ∈ N und fn = 0,1 eine Hutfolge.
Sei F = {f(r); r ∈ R} die (überabzählbare) Menge aller Hutfolgen
Nun definieren wir eine Äquivalenzrelation von Hutfolgen f ~ g: f sei äquivalent zu g, genau dann, wenn sich f und g nur in höchstens endlich vielen Stellen unterscheiden. Umgekehrt sind zwei Folgen nicht äquivalent, wenn sie sich in unendlich vielen Stellen unterscheiden.
Eine Äquivalenzklasse [f] wird dann definiert als Teilmenge von F mit
[f] = {f(r) ∈ F: f(r) ~ f} ⊂ F
d.h. in [f] sind alle f(r) enthalten, die untereinander und insbs. zu einem (beliebigen) Repräsentanten f äquivalent sind.
Eine Teilmenge S = {σ ∈ F} ⊆ F nennt man ein Repräsentantensystem von F bzgl. ~, wenn S genau ein σ ∈ [f] je [f] enthält.
Damit haben wir die Lösung.
Die Sünder legen ihre Strategie fest:
1a) Sie führen zunächst die o.g. Zerlegung aller möglichen Hutfolgen F in die genannten Äquivalenzklassen [f] durch.
1b) Sie einigen sich auf ein Repräsentantensystem S für F bzgl. ~.
Nun werden sie aufgefordert, ihre eigene Hutfarbe zu erraten:
2a) Da jeder Sünder alle Hutfarben bis auf die eigene kennt, ist dies gleichbedeutend damit, dass jeder die vollständige Folge zu erraten hat; nennen wir diese f°. Nun kann jeder Sünder aus den ihm bekannten Hutfarben bereits die Äquivalenzklasse [f°] ermitteln, zu der f° gehört: er sieht bzw. kennt z.B. (001…?...) wobei das ? für die eigene Hutfarbe steht. Damit weiß er jedoch, dass z.B. (001…?...) ~ (001…0...) ~ (001…1...) ~ f°. Damit kennt jeder Sünder nun auch den zuvor festgelegten Repräsentanten σ ~ f° aus [f°]. Somit ist [f°] und σ aus der Kenntnis der sichtbaren Hutfarben für jeden Sünder eindeutig ableitbar.
2b) Der Sünder mit Nummer n rät (≟) seine eigene Hutfarbe als n-te Stelle aus diesem σ, d.h. f°n ≟ σn, also z.B.: n rät (001… σn ...). Da in [f°] nur Folgen enthalten sind, die sich an endlich vielen Stellen von f° unterscheiden, unterscheidet sich auch der zuvor festgelegte Repräsentant σ ~ f° aus [f°] nur an endlich vielen Stellen von f°. Und damit raten auch nur endlich viele Sünder falsch, nämlich diejenigen, die das Pech haben, dass ihre Position n gerade den Stellen fn entspricht, an denen sich σ von f° unterscheidet, d.h. σn ≠ f°n.
◼
Wozu benötigt man das Auswahlaxiom?
Man benötigt eine injektive Funktion c, die für alle möglichen Folgen f ∈ F den jeweiligen Repräsentanten σ[f] ∈ [f] zuordnet, d.h.
c: F → S
c(f) = σ[f] ⟺ σ ~ f
mit
f ~ g ⟹ c(f) = c(g)
D.h. egal welches f man in die Funktion hineinsteckt, man erhält immer das eindeutig definierte σ[f] je [f].
Dies kann jeder Sünder durchführen, da er zwar nicht f° kennt, jedoch ein f ~ f°, das sich in höchstens einer (seiner) Stelle von f° unterscheidet, d.h. er ermittelt das σ ~ f° mittels σ = c(f ~ f°) und rät f°n ≟ σn = cn(f).
Die Menge der Verdammten entspricht dann
V = {n ∈ N: σn ≠ f°n}
|V| < ∞
Dies kann man auch wie folgt interpretieren:
Sei
F/~ = {[f]}
die Menge aller Äquivalenzklassen von F bzgl. ~.
Damit ist die Definition von c äquivalent zu einer Bijektion
c: F/~ → S
c[f] = σ[f]
D.h. die Funktion c wählt aus jeder Äquivalenzklassen [f] ∈ F/~ genau ein σ[f] aus. Die Existenz einer derartigen Auswahlfunktion c für eine unendliche Menge F/~, deren Elemente unendliche Mengen [f] sind, wird durch das Auswahlaxiom sichergestellt.
Für das vorliegende Problem – die Frage nach der Existenz einer Strategie, die alle außer endliche viele Sünder rettet – sind die Details von c irrelevant; die pure Existenz von c stellt die Lösung σ ~ f° sicher. Der eigentliche Kern der Lösung ist die Anwendung der speziellen Äquivalenzrelation f ~ g ⟺ fn ≠ gn für höchsten endlich viele n.