Die Mathe-Redaktion - 24.09.2018 08:09 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 254 Gäste und 13 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » ** Welche Farbe hat meine Mütze?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule ** Welche Farbe hat meine Mütze?
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-08-30


Heute hat mir ein Kollege eine schnuckelige Variation des Welche-Farbe-hat-meine-Mütze-Rätsels erzählt, welches ich gerne an euch weitergebe.

Der böse Zauberer Gargamel hat alle Schlümpfe gefangen. Es sind abzählbar unendlich viele. (Im Folgenden mit <math>S_0,S_1,S_2,...</math> bezeichnet.) Eines Abends verkündet er:

"Morgen werde ich euch alle fressen. Es sei denn, ihr bewältigt folgende Aufgabe. Ihr werdet euch in einer langen Reihe aufstellen, und ich werde jedem von euch eine Mütze aufsetzen. Die Mütze ist entweder weiß oder rot. Ihr werdet so stehen, dass ein Schlumpf mit der Nummer <math>n</math> nur die Schlümpfe <math>S_{n+1},S_{n+2},S_{n+3},...</math> sehen kann. Insbesondere sieht kein Schlumpf die Farbe seiner eigenen Mütze. Schreibt dann alle die Farbe eurer eigenen Mütze verborgen vor den anderen auf einen Zettel. Nachdem ich euch die Mützen aufgesetzt habe, ist jegliche Kommunikation verboten. Wenn nur endlich viele von euch einen Fehler machen, seid ihr alle frei."

Die ganze Nacht beratschlagen die armen Schlümpfe, wie sie ihre Haut retten können ...

Lösungsvorschläge bitte per PM an mich.



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2017-08-30


Gold geht an BlakkCube! An der Lösung gibt es absolut nichts auszusetzen; ganz toll aufgeschrieben!

Kuestenkind kannte das Rätsel bereits, hat mir aber eine Zusatzaufgabe gestellt, an der ich noch knabbere eek

Viele Grüße
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
Bai
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2014
Mitteilungen: 1160
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2017-08-30


2017-08-30 22:23 - StrgAltEntf in Beitrag No. 1 schreibt:
Kuestenkind kannte das Rätsel bereits, hat mir aber eine Zusatzaufgabe gestellt, an der ich noch knabbere :-o

Darf man denn erfahren, welche das ist?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2017-08-30


Silber geht an Bai! Auch an Bais Lösung gibt es nullkommanix auszusetzen - outstanding!

Kuestenkinds Zusatzfrage:

Wenn die Schlümpfe nicht heimlich, sondern laut und für alle vernehmlich ihre Tipps abgeben dürfen, und zwar in der Reihenfolge <math>S_0,S_1,S_2,...</math>, wie können sie es dann erreichen, dass maximal ein Schlumpf falsch antwortet?

EDIT: Mittlerweile kenne ich die Lösung der Zusatzfrage (danke @Kuestenkind), nehme Vorschläge gerne entgegen und kommentiere sie auf Wunsch. Als Schwiergkeitsgrad hätte ich für die Zusatzfrage *** eingestellt; zumindest dann, wenn sie nicht als Zusatzaufgabe sondern als eigenständiges Rätsel gestellt worden wäre.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2017-08-31


Einige haben für das Zusatzrätsel vorgeschlagen, dass die Schlümpfe über einen verdeckten Kanal miteinander kommunizieren. Z. B. indem sie unterschiedlich lange Sprechpausen einlegen oder ihre Antwortsätze unterschiedlich formulieren (etwa "meine Mütze ist rot", falls seine und die des Nachfolgers rot sind, oder "meine Mütze ist nicht rot, also weiß", falls seine weiß und die des Nachfolgers rot ist). Möglicherweise lässt sich Gargamel dadurch überlisten - als Lösung für das Rätsel kann ich es aber leider nicht gelten lassen frown

Folgendes ist aber natürlich erlaubt (auch wenn es nicht viel bringt): Wenn <math>S_3</math> sagt, dass seine Mütze weiß ist, bedeutet das eigentlich, dass die Mützen von <math>S_7</math> und <math>S_9</math> rot sind.

Auch den Vorschlag für das Ausgangsrätsel, dass die Schlümpfe die Farbe des Nachfolgers aufschreiben und dann heimlich die Zettel tauschen, ist eine unerlaubte Schummelei frown

Der gemachte Einwand, dass Gargamel in endlicher Zeit nur endlich viele Zettel kontrollieren und deswegen nicht entscheiden kann, ob tatsächlich unendlich viele Schlümpfe falsch geantwortet haben, ist zwar berechtigt, aber für dieses Rätsel nicht zielführend. (Denn Gargamel kann ja bei diesem Rätsel auch unendlich viele Mützen in endlicher Zeit den Schlümfen aufsetzen, was ja dann auch nicht möglich wäre.)

Ich lasse euch noch ein wenig Zeit und appeliere insbesondere an die Mengenlehrespezialisten hier im Forum, noch ein wenig drüber nachzudenken smile



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2017-08-31


In Vertretung von Küstenkind kann ich Gold für das Zusatzrätsel an Bai vergeben. Herzlichen Glückwunsch!



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2017-09-01


Silber für das Zusatzrätsel geht an BlakkCube ... herzlichen Glückwunsch!



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2017-09-01





  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2017-09-01


Hallo zusammen!

Ich gebe das Rätsel frei zur öffentlichen Diskussion. smile



  Profil  Quote  Link auf diesen Beitrag Link
BerndLiefert
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2014
Mitteilungen: 390
Aus: Lehramtplanet
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2017-09-01


1. Äquivalenzklassen
2. Auswahlaxiom
3. ???
4. Profit



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2017-09-01


2017-09-01 21:31 - BerndLiefert in Beitrag No. 9 schreibt:
1. Äquivalenzklassen
2. Auswahlaxiom
3. ???
4. Profit

1. Ja
2. Ja
3. smile
4. ???



  Profil  Quote  Link auf diesen Beitrag Link
salomeMe
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.10.2015
Mitteilungen: 439
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2017-09-02


"Wenn nur endlich viele von euch einen Fehler machen, seid ihr alle frei."

Was ist, wenn alle Schlümpfe mehr als einen Fehler machen: z.B. "grün" und "blau" auf ihren Zettel schreiben? wink

Wie sehen eigentlich grün- und blaublinde Schlümpfe eine ansonsten weiß erscheinende Mütze? Falls diese die Mütze als rot erkennen und die Anzahl der Schlümpfe mit dieser Eigenschaft unendlich ist, wäre es unfair "rot" als Fehler zu werten, falls ein Schlumpf mit einer weißen Mütze so antwortet, denn er könnte ja von der genannten Sehschwäche betroffen sein und nur Schlümpfe mit roten Mützen sehen.

EDIT: ich wollte mit diesem Beitrag keineswegs die ursprüngliche Aufgabenstellung kritisieren (@Kuestenkind) - habe einfach keinen praktikablen mathematischen Lösungsansatz gefunden. In solchen Situationen fallen mir dann leider oft Spitzfindigkeiten ein, die ich besser nicht aufgeschrieben hätte.

beste Grüße
salomeMe



  Profil  Quote  Link auf diesen Beitrag Link
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 1001
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2017-09-02


Ich kann deinen Beitrag leider überhaupt nicht nachvollziehen, salomeMe. StrgAltEntf hätte die Aufgabe ja auch mathematisch formulieren können:

Gibt es unter Annahme des Auswahlaxioms für <math>n\in\mathbb N</math> Abbildungen <math>S_n: \{0,1\}^{\mathbb N_{>n}} \to \{0, 1\}</math>, so dass für jedes <math>(H_k)_{k\in\mathbb N} \in \{0,1\}^{\mathbb N}</math> gilt, dass <math>\{n\in\mathbb N\quad\vert\quad S_n ((H_k)_{k>n}) \neq H_n\} </math> endlich ist?

Hätte dir diese Aufgabenstellung nun mehr zugesagt?

Gruß,

Küstenkind



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1646
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2017-09-02


Frage zur Originalaufgabe:

Kennen die Schlümpfe ihre Position in der Reihe?
Laut Aufgabenstellung wohl nicht.
Der letzte Post liest sich jedoch so als ob.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2017-09-02


2017-09-02 14:25 - DerEinfaeltige in Beitrag No. 13 schreibt:
Kennen die Schlümpfe ihre Position in der Reihe?

Ja, kennen sie. Zumindest, nachdem sie sich in die Reihe gestellt haben.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2017-09-03


Eine sehr schöne Lösung für die Zusatzaufgabe hat mir Nuramon gesandt. Diese Lösung baut nicht auf der Lösung der Originalaufgabe auf (verwendet aber auch eine zum AC äquivalente Aussage).



  Profil  Quote  Link auf diesen Beitrag Link
stupidix
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 05.09.2017
Mitteilungen: 7
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2017-09-05


Sorry, welche "Lösung" auch immer hier ausgedacht wurde, sie ist falsch, wie schon hier bewiesen:

Link*** Ein Spiel mit dem Teufel

Es reicht nicht, mit Sätzen, Axiomen und Konstruktionsvorschriften um sich zu werfen, es ist auch nachzuweisen, daß diese anwendbar sind und das gewünschte Ergebnis liefern.  Ein Beweis läßt sich nicht dadurch entkräften, daß man etwas Falsches konstruiert und den Fehler darin nicht erkennt.  Es bleibt trotzdem falsch.



  Profil  Quote  Link auf diesen Beitrag Link
LeBtz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.04.2015
Mitteilungen: 1117
Aus: dem Meer
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2017-09-05


Vielleicht liegst du ja auch falsch und die anderen eher richtig?
Daran sollte man mal einen Gedanken verschwenden, wenn eine große Mehrheit ausgebildeter Mathematiker gegen einen steht.

Ich habe in dem anderen Thread etwas dazu geschrieben, warum deine Widerlegung der Lösung nichts zeigt (in kurz: du beweist im Grunde über mehrere Zeilen Trivialitäten, aber wenn es zum entscheidenden Punkt kommt, führst du den nicht aus, sondern postulierst ihn einfach. Es ist klar, warum das so ist, ein präzises Argument lässt sich für falsche Aussagen eben nicht finden).



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2017-09-05


Danke @stupidix für den Hinweis, dass das Rätsel hier schon vor geraumer Zeit gestellt wurde. Das wusste ich nicht. Was du dort schreibst, kann ich aber leider nicht nachvollziehen, auch weil ich die Hieroglyphen nicht richtig entziffern kann.



  Profil  Quote  Link auf diesen Beitrag Link
salomeMe
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.10.2015
Mitteilungen: 439
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2017-09-08


Hallo StrgAltEntf,

mir erscheint das frühere Rätsel etwas einfacher gestellt worden zu sein, da jeder Mathematiker (bei Dir Schlumpf) die Hüte aller anderen sehen kann. Das scheinen mir mehr Informationen zu sein, als in dem von Deinem Rätsel abgeleiteten Rätsel von @Kuestenkind gegeben sind, bei dem nur ein Fehler auftreten darf. Eventuell kommst Du um die Auflösungen Deines Rätsels und des abgeleiteten nicht herum?

Auf jeden Fall scheinen Deine Schlüpfe übermenschliche Eigenschaften zu besitzen, wenn sie wohl aus überabzählbaren möglichen Mützenverteilungen aus jeweils abzählbaren Farbfolgen alle genau ein und dieselbe Verteilung auswählen können.

beste Grüße
salomeMe



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 663
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2018-08-18

\(\begingroup\)
Das Rätsel ist jetzt schon etwas älter. Mich würden die Lösungswege für die Zusatzaufgabe interessieren.

Ich frage deshalb, weil mich folgende Variante des Rätsels interessiert:
Gargamel hat abzählbar unendlich viele Schlümpfe gefangen. Er bietet den Schlümpfen am Abend aber wieder einen Ausweg an: Am nächsten Morgen stellt Gargamel die Schlümpfe in einer Reihe $S_0,S_1,S_2,\ldots$ auf und gibt jedem eine Mütze, die eine von $n$ verschiedenen Farben hat (die Menge der Farben ist den Schlümpfen bekannt). Außerdem stellt er sicher, dass für alle $m\in\IN$ der Schlumpf $S_m$ die Mützenfarbe der Schlümpfe $S_{m+1},S_{m+2},\ldots $ sieht, aber keine andere. Die Schlümpfe müssen dann beginnend mit $S_0$ der Reihe nach ihre Mützenfarbe raten. Alle Schlümpfe können hören, was die Schlümpfe vor ihnen geraten haben. Wenn alle bis auf höchstens einen Schlumpf richtig raten, dann kommen alle Schlümpfe frei. Wenn mindestens zwei Schlümpfe falsch raten oder irgendein Schlumpf zu schummeln versucht, z.B. indem er etwas anderes sagt als eine der $n$ Farben, dann werden alle Schlümpfe gefressen.
Für welche Werte von $n$ gibt es eine Strategie, mit der die Schlümpfe frei kommen können?

Die ursprüngliche Zusatzaufgabe ist der Fall mit $n=2$. Ich kenne für unendlich viele $n$ eine Lösung, aber nicht für alle. Das kleinste $n$, für das ich die Antwort nicht weiß, ist $n=6$. Hat jemand dafür eine Lösung? Wenn StrgAltEntf damit einverstanden ist, kann ich meine Lösung hier in einem hide-Bereich aufschreiben. Wenn nicht, schicke ich sie gern auf Nachfrage per PN an Interessenten.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, vom Themenstarter, eingetragen 2018-08-18


2018-08-18 15:26 - Nuramon in Beitrag No. 20 schreibt:
Wenn StrgAltEntf damit einverstanden ist, kann ich meine Lösung hier in einem hide-Bereich aufschreiben.

Nur zu Nuramon,

das Rätsel ist ja auch schon längst freigegeben. (Ich hatte hier gar nicht aufgelöst, da das Rätsel ja bereits früher schon einmal gestellt wurde,)

Grüße
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 592
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2018-08-18


Ging das nicht so:

Ich glaube die drängeln sich alle in die Mitte und die anderen rücken rechts oder links ab. So wird wohl weiß und rot getrennt,oder ?
Praktisch der letzte , müsste es erfahren, wenn einer von links oder rechts sich nochmal reindrängelt,oder ?



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 663
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2018-08-18

\(\begingroup\)
2018-08-18 17:58 - pzktupel in Beitrag No. 22 schreibt:
Ging das nicht so:

Ich glaube die drängeln sich alle in die Mitte und die anderen rücken rechts oder links ab. So wird wohl weiß und rot getrennt,oder ?
Praktisch der letzte , müsste es erfahren, wenn einer von links oder rechts sich nochmal reindrängelt,oder ?
Die Reihenfolge der Schlümpfe steht fest, bevor sie die Mützen bekommen (zumindest in meiner Version). Sie dürfen sich dann nicht mehr umstellen.

Hier ist der Teil der Lösung zu der Version aus Beitrag 20, der mir bekannt ist:

 Die Schlümpfe können zumindest dann freikommen, wenn $n=1$ ist oder es einen Körper mit $n$ Elementen gibt (d.h. wenn $n$ eine Primzahlpotenz ist oder $n$ ist unendlich). $n=1$ ist trivial. Sei also $F$ ein Körper mit $n$ Elementen. Wir identifizieren die Farben mit den Elementen von $F$.
Sei $V=F^\IN$ der $F$-Vektorraum der unendlichen Folgen $\IN\to F$. Die Menge der Kroneckerdeltafolgen $\delta_m\in V$ (d.h. $\delta_m(m)=1$ und $\delta_m(i)=0$ für $i\not=m$) ist eine linear unabhängige Teilmenge von $V$. Also können wir sie zu einer Basis von $V$ ergänzen.
Wir wählen eine lineare Abbildung $f:V\to F$, indem wir $f(\delta_m)=1$ festlegen und linear fortsetzen.

Die Schlümpfe können nun folgende Strategie verwenden: Der Schlumpf $S_0$ sieht, dass die restlichen Schlümpfe $S_1,S_2,\ldots$ die Mützenfarben $s_1,s_2,\ldots$ haben.
Auf Gargamels Frage, welche Farbe seine Mütze hat, antwortet $S_0$ mit $a:=f(s_1,s_2,\ldots)$.
Dann weiß $S_1$ seine Mützenfarbe $s_1$, denn wegen der Linearität von $f$ gilt $a=s_1f(\delta_0)+f(0,s_2,s_3,\ldots)=s_1+f(0,s_2,s_3,\ldots)$ und da $S_1$ die Farben $s_2,s_3,\ldots$ kennt, kann er $s_1=a-f(0,s_2,s_3,\ldots)$ berechnen.
Wenn Schlumpf $S_m$ an der Reihe ist, können wir nun induktiv annehmen, dass $S_1,S_2,\ldots, S_{m-1}$ richtig geraten haben und $S_m$ daher die Farben $s_1,s_2,\ldots, s_{m-1}$ kennt. Dann kann $S_m$ auch seine eigene Farbe $s_m$ berechnen, denn $a=s_mf(\delta_{m-1})+f(s_1,s_2,\ldots, s_{m-1},0,s_{m+1},s_{m+2},\ldots)$, also $s_m=a-f(s_1,s_2,\ldots, s_{m-1},0,s_{m+1},s_{m+2},\ldots)$.
Somit können alle Schlümpfe bis auf eventuell $S_0$ auf die Frage nach ihrer Mützenfarbe richtig antworten.

Anmerkungen:
1. Wenn man $F$ durch $\IZ/n\IZ$ ersetzt, dann weiß ich nicht, ob es eine lineare Abbildung $f: (\IZ/n\IZ)^\IN\to \IZ/n\IZ$ gibt mit $f(\delta_m)=1$ für alle $m$. Daher ist mir nicht klar, ob man die Schlümpfe retten kann, wenn z.B. $n=6$ ist.
2. Die Lösung funktioniert auch für die Variante der Aufgabe, in der Gargamel nur endlich viele Schlümpfe (sagen wir $k$ Schlümpfe) fängt, und zwar auch dann, wenn $n$ keine Primzahlpotenz ist. $f:(\IZ/n\IZ)^{(k-1)}\to \IZ/n\IZ$ ist dann einfach gegeben durch die Summe aller Mützenfarben.

Wie gesagt, bin ich sehr interessiert an anderen Lösungsansätzen, auch wenn die vielleicht nur für $n=2$ funktionieren.


EDIT: Ich kenne jetzt für alle $n$ die Antwort. Wer will, kann diese Variante jetzt also als weitere Zusatzknobelaufgabe ansehen und gegebenenfalls eine Lösung hier posten.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, vom Themenstarter, eingetragen 2018-08-19

\(\begingroup\)
2018-08-18 18:46 - Nuramon in Beitrag No. 23 schreibt:
Hier ist der Teil der Lösung zu der Version aus Beitrag 20, der mir bekannt ist:

Eine schöne Lösung! Ob man sie für n, die keine Primzahlpotenzen erweitern kann, kann ich leider nicht sagen. Dazu stecke ich nicht (mehr?) tief genug in der Theorie.

Hier die mir bekannte Lösung.

Die Lösung des ursprünglichen Problems habe ich von BlakkCube auf n Mützenfarben (0,1,...,n-1) adaptiert:


Die Menge aller möglichen Mützenverteilungen wird durch die Menge <math>\displaystyle V:=\{0,...,n-1\}^\mathbb{N}</math> gegeben. Wir nennen zwei Verteilungen <math>\displaystyle a,b\in V</math> äquivalent, falls sich a und b an höchstens endlich vielen Stellen unterscheiden. Wir schreiben dann <math>\displaystyle a\cong b</math>. Die Äquivalenz von Verteilungen ist offensichtlich reflexiv und symmetrisch.

Seien <math>\displaystyle a=(a_m),b=(b_m),c=(c_m)\in V</math> mit <math>\displaystyle a\cong b</math> und <math>\displaystyle b\cong c</math>. Dann gibt es Indizes <math>\displaystyle i_1,\ldots, i_k</math> mit <math>\displaystyle a_m\neq b_m</math> für <math>\displaystyle m=i_1,\ldots, i_k</math> und <math>\displaystyle a_m=b_m</math> sonst; sowie <math>\displaystyle j_1,\ldots, j_\ell</math> mit <math>\displaystyle b_m\neq c_m</math> für <math>\displaystyle m=j_1,\ldots, j_\ell</math> und <math>\displaystyle b_m=c_m</math> sonst. Aus der Transitivität der Gleichheitsrelation (=) folgt, dass <math>\displaystyle a_m=c_m</math> (zumindest)für alle Indizes <math>\displaystyle m\notin\{i_1,\ldots, i_k,j_1,\ldots, j_\ell\}</math> gilt. Folglich unterscheiden sich die Verteilungen a und c in höchstens endlich vielen Stellen. Die Äquivalenz von Verteilungen ist daher auch transitiv.

Damit ist gezeigt, dass es sich bei der Äquivalenz von Verteilungen um eine Äquivalenzrelation handelt.

Auf der Menge der Äquivalenzklassen <math>\displaystyle V/\cong</math> garantiert uns das Auswahlaxion die Existenz einer Auswahlfunktion, d.h. <math>\displaystyle f:V/\cong\longrightarrow V</math> mit <math>\displaystyle f(X)\in X</math> für alle Äquivalenzklassen <math>\displaystyle X\in V/\cong</math>.

Da die Schlümpfe nun sehr schlau sind, wählen sie sich eine solche Auswahlfunktion und einigen sich darauf, nur diese zu verwenden.

Am nächsten Tag erhalten sie ihre Mützen. Jeder Schlumpf sieht nun nur endlich(!) viele Mützen nicht(!). Jeder Schlumpf füllt nun gedanklich die nicht sichtbaren Mützen mit der Farbe 0 auf. Diese Verteilungen, die sich die Schlümpfe nun ausgedacht haben, unterscheiden sich nur jeweils um höchstens endlich viele - sie sind also alle in der gleichen Äquivalenzklasse, in der sich auch die tatsächliche Verteilung befindet! Nun wendet jeder Schlumpf auf die Äquivalenzklasse seiner "gedanklichen" Verteilung die Auswahlfunktion, auf die man sich geeinigt hat, an. Auf die Frage, welche Farbe seine Mütze habe, antwortet er nun, welche Farbe an seiner Position der gewählte Repräsentant der Äquivalenzklasse (also das Bild der Auswahlfunktion) hat. Nach Konstruktion unterscheidet sich dieser Repräsentant in höchstens endlich vielen Stellen von der tatsächlichen Verteilung und die Schlümpfe sind frei.


Jetzt kommt die Variante.


\(S_0\) sieht die Mützenfarben \(b_1,b_2,b_3,...\) und vergleicht sie mit dem Repräsentanten \(a_1,a_2,a_3,...\) der Auswahlfunktion. Er berechnet sodann \(x=\sum_{m=1}^\infty(a_m-b_m)\mod n\) (beachte, dass hier nur endlich viele von 0 verschiedene Summanden stehen) und nennt x als seine eigene Mützenfarbe.

Nun ist \(S_1\) an der Reihe. Er kennt \(a_1,a_2,a_3...\) sowie x und \(b_2,b_3,...\). Er kann also \(b_1\) berechnen.

Und so geht es jetzt weiter. \(S_m\) kennt \(a_1,a_2,a_3...\), x und \(b_1,b_2,...,b_{m-1},b_{m+1},b_{m+2},...\) und kann daraus \(b_m\) berechnen.

\(S_0\) ist der einzige Schlumpf, der möglicherweise eine falsche Antwort gibt.


Grüße
StrgAltEntf
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, vom Themenstarter, eingetragen 2018-08-21

\(\begingroup\)
2018-08-18 18:46 - Nuramon in Beitrag No. 23 schreibt:
EDIT: Ich kenne jetzt für alle $n$ die Antwort. Wer will, kann diese Variante jetzt also als weitere Zusatzknobelaufgabe ansehen und gegebenenfalls eine Lösung hier posten.

@Nuramon:
Dein Edit sehe ich erst jetzt. Ich habe ebenfalls noch einmal drüber nachgedacht und meine, nun eine lineare Funktion  \(f:\IZ_n^\IN\rightarrow\IZ_n\) mit \(f(\delta_m)=1\) für alle m gefunden zu haben.

Sei n=6 (der allgemeine Fall geht analog wink )

Definiere \(\phi:\IZ_6\rightarrow\IZ_2\times\IZ_3\) durch \(\phi(d)=(\phi_2(d),\phi_3(d))=(d\mod2,d\mod3)\).

Für eine Folge \(a=(a_m)_{m\in\IN}\in\IZ_6^\IN\) sei dann \(\phi_2(a)=(\phi_2(a_m))_{m\in\IN}\in\IZ_2^\IN\) und analog \(\phi_3(a)\).

Seien dann \(f_2:\IZ_2^\IN\rightarrow\IZ_2\) und \(f_3:\IZ_3^\IN\rightarrow\IZ_3\) lineare Funktionen mit \(f_2(\delta_m)=f_3(\delta_m)=1\) für alle m.

Definiere \(f:\IZ_6^\IN\rightarrow\IZ_6\) durch \(f(a)=\phi^{-1}(\phi_2(a),\phi_3(a))\).

Dieses f müsste es tun. Meine ich. Wenn ich keinen Bock geschossen habe.  smile
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 663
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2018-08-21

\(\begingroup\)
Das sieht für $n=6$ richtig aus und so ähnlich habe ich das auch gelöst. Aber wenn in der Primfaktorzerlegung von $n$ echte Potenzen vorkommen, dann geht das glaube ich nicht ganz so einfach. Die Lösung die ich gefunden habe besteht im Wesentlichen daraus statt $\IZ/n\IZ$ die Menge $\IF_{q_1}\times \ldots \times\IF_{q_r}$ zu betrachten, wobei $n=q_1\cdots q_r$ die Zerlegung von $n$ in verschiedene Primzahlpotenzen ist, und dann in jeder Komponente die schon bekannte Lösung anzuwenden.

Damit kann man die Aufgabe lösen, aber das algebraische Problem, ob es für jedes $n$ einen Homomorphismus von abelschen Gruppen $f:(\IZ/n\IZ)^\IN\to \IZ/n\IZ$ mit $f(\delta_m)=1$ für alle $m\in \IN$ gibt, ist noch nicht ganz beantwortet (und ich kenne die Antwort auch nicht). Mit deiner Idee (also dem chinesischen Restsatz) kann man das Problem immerhin auf den Fall reduzieren, dass $n$ eine Primzahlpotenz ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4280
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, vom Themenstarter, eingetragen 2018-08-21

\(\begingroup\)
2018-08-21 20:05 - Nuramon in Beitrag No. 26 schreibt:
Damit kann man die Aufgabe lösen, aber das algebraische Problem, ob es für jedes $n$ einen Homomorphismus von abelschen Gruppen $f:(\IZ/n\IZ)^\IN\to \IZ/n\IZ$ mit $f(\delta_m)=1$ für alle $m\in \IN$ gibt, ist noch nicht ganz beantwortet (und ich kenne die Antwort auch nicht).

Hm, ja ... irrigerweise ging ich davon aus, dass man oBdA n=6 setzen kann  wink Aber nein, wenn in der Primzahlzerlegung von n einige Primzahlen mehrfach auftreten, klappt es noch nicht.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]