Beiträge von Cord

    Gibt es einen Grund zur Annahme, dass diese Dinge irgend etwas miteinander zu tun haben könnten?

    Nein! Wenn doch, warum bekommt man nicht eine etwas weiterführende Erklärung? Immer nur " ... nächsten Tagen hochgeladen werden" ist doch etwas armselig.

    Das reichlich gespendete Lob für die Aufgabensteller und -bearbeiter ist sicher sehr berechtigt, aber, was jetzt passiert, ist nicht besonders nett!

    Ich glaube für n = 3 lässt sich das noch am einfachsten aufdröseln. Die 48 Möglichkeiten sind keine Strategien. Es gibt 48 Möglichkeiten, wie sich die 3 Wichtel der Reihe nach in verscheidenen Hutvariationen aufstellen können. Aber beim 3. Wichtel haben sie gar keine Wahl mehr, das wird vom Weihnachtsmann bestimmt und dafür können sie keine Strategie wählen.


    Und der zweite Wichtel, der vom Weihnachtsmann ausgewählt wird, hat nicht nur 2 sondern 4 mögliche Strategien (nicht Wahlmöglichkeiten!). Er kann seine Farbwahl von seinem Vorgänger (A1 oder B1) und der Wahl seines Vorgängers abhängig machen, also für f(A1=0) muss er eine Strategie haben, genau so für f(A1=1), f(B1=0) und f(B1=1). Es gibt also 2 x 2 x 2 x 4 x 4 x 4 verschiedene Strategien.


    Ergänzung: sorry, ihr schreibt viel schneller als ich. Ich bin immer noch bei n=3, wollte aber euren Gedankenfluss mit n=4 nicht durcheinander bringen.

    Ja, so in etwa. Kleine Ergänzung resp. Korrektur: die Farbe, die Wichtel m aufgrund der vereinbarten Strategie wählt, hängt von m und allen vorher gewählten Wichteln ab, wobei die Reihenfolge der Auswahl wichtig ist. Sie hängt nicht ab von den vorher gewählten Farben.


    In anschaulichen Beschreibungen einer Strategie kann das natürlich sein, z.B. "falls die Anzahl der bisher rot gewählten ungerade ist ...".

    Das ändert aber nichts an den oben gemachten Feststellungen, da man jede, auch anschaulich definierte, Strategie immer in der oben beschriebenen Form angeben kann.

    D

    Das ist einfach: 4 * 2 = 8


    Male von jedem Wichtel je einen Pfeil auf 0 und 1: Das ergibt insgesamt 8 Pfeile.

    8 Pfeile, richtig. Nur: jeder einzelne Pfeil ergibt noch keine Strategie, denn er verbindet ja nur einen Wichtel mit einer Farbe, was ist mit den drei anderen?

    Eine Strategie - nur für diesen ersten "Zug" - bestünde darin, jeden Wichtel mit genau einer Farbe zu verbinden. Und die Anzahl solcher Zuordnungen ist 24.

    Ok, jetzt ich ...


    Eine Strategie besteht doch darin, für jeden denkbaren Verlauf des "Spiels" (das der W._Mann spielt) festzulegen, wie reagiert wird, in diesem Falle, welche Farbe (hier 0 oder 1) gewählt werden soll.


    Gehen wir von 4 Wichteln A,B,C und D aus.


    Wenn ich nur die allererste Wahl des W.-Manns betrachte: er kann A,B,C oder D wählen, 4 Möglichkeiten. Eine Strategie legt nun fest, welche Farbe A nehmen soll, wenn er gewählt wird, entsprechend für die drei anderen. D.h., die Strategie bildet die Menge {A,B,C,D} auf {0,1} ab. Und wie viele solcher Abbildungen gibt es?

    Phase 2 lass ich mal außen vor, denn die Anzahl der Strategien ist unabhängig von Phase 2. Quibo kennt natürlich die gewählte Strategie und muss nun entscheiden, welche Permutationen in Frage kommen, damit die Farbverteilung, die er sieht, so ist wie sie ist. Und das jeweils letzte Element solcher Permutationen ist dann ein Kandidat für Wichtel X.


    Zur Anzahl der Strategien (ohne jede Reduktion aufgrund von Symmetrien):


    Nehmen wir n = 4. Schon für die erste Wahl des W.-Manns gibt es 24 Möglichkeiten, zu reagieren und nicht nur 2*4. Für die zweite Wahl des W.-Manns sind 12 = 4*3 Paare zu berücksichtigen. Denn: die Farbe, die die Strategie für die Folge 2,1 für 1 vorsieht, kann ja anders sein, als die Farbe, die die Strategie für 1 beim Paar 3,1 vorsieht, und auch verschieden von der Farbe für die 1, wenn sie (also der entspr. Wichtel) als erste genannt wird oder als dritte in z.B. 2,4,1.


    Kurz und gut: eine Strategie ist eine Abbildung aller max. 15-stelligen Folgen aus dem Bereich 1 bis 16, paarweise verschieden, in die 2- elementige Menge {rot, blau}. (Bzw. für n = 4 eine Abbildung aller max. 3 stelligen Folgen aus dem Bereich 1,2,3,4 in die Menge {rot, blau}.)


    Nicht einleuchtend?


    Das sehe ich anders. Eine Strategie der Wichtel muss für jede Situation, die sich aufgrund der nicht vorherzusehenden Wahl des Weihnachtsmannes ergeben könnte, eine Reaktion vorsehen.

    Also: im folgenden mögen die Zahlen 1 bis 16 für die 16 Wichtel stehen.


    Das Spiel läuft in der ersten Phase dann so: der W.-Mann wählt eine Zahl zwischen 1 und 16, der entsprechende Wichtel muss dann bereits eine Wahl treffen, er kann nicht warten, bis die gesamte Wahl des W.-Manns feststeht. Eine Strategie zu haben bedeutet dann also, dass festgelegt sein muss, welche Wahl welcher Wichtel treffen soll, wenn er als erster gewählt wird. Dann geht's weiter mit der nächsten Auswahl des W.-Manns und der entsprechende Wichtel, der jetzt weiß, was vor ihm gewählt wurde, muss eine Wahl treffen. Das heißt, die gewählte Strategie muss für alle Paare von Wichteln für den zweiten Wichtel in diesem Paar eine Farbe vorsehen. In dieser Weise geht es weiter. Insgesamt: eine Strategie wählt für jede max. 15-stellige Folge von paarweise verschiedenen Zahlen zwischen 1 und 16 eine Farbe. Die Anzahl solcher Folgen ist, wie leicht zu sehen: 16 + 16*15 + 16*15*14 + ... + 16*15*14*...*2.


    Für den Fall der 4 Wichtel haben wir: Anzahl der Folgen ist 4 + 4*3 + *4*3*2 = 40.


    So ergeben sich die oben genannten Werte.


    Da die Anzahl der Farben 2 ist, könnte man auch sagen: eine Strategie besteht darin, eine Teilmenge der Menge aller oben erklärten Folgen festzulegen, nämlich die Menge aller Folgen, bei der der letzte in der Folge ROT wählt.


    Für den Fall von 3 Wichteln, der oben von RüdiJ erwähnt wurde, ergibt meine Rechnung auch 29 Strategien, da die Anzahl der Folgen ja 3 + 3*2 = 9 ist.

    Ja das wäre interessant einen Beweis zu sehen. Oder wenn es keine Quadratzahl ist. Ich habe lange nach einer Strategie für 8 Wichtel gesucht, konnte aber immer nur 4 davon "retten". Schon bei 8 Wichtel gibt es extrem viele Möglichkeiten für eine Strategie und ich habe keine Ahnung, wie man das allgemein angehen kann.

    Für den Fall n =8 statt 16: da müsste es doch mit einer 3,3,2 - Gruppierung (statt einer 4,4,4,4 - Gruppierung wie in der hier veröffentlichten "Musterlösung") möglich sein, immer mindestens 5 zu "retten", oder?


    Was die Anzahl der Strategien angeht: für den Fall der 16 Wichtel gibt es 235.951.249.665.216 Strategien, für den Fall von 8 Wichteln immerhin

    noch 269280, zu viel zum Durchlauf in einer Schleife. Selbst bei 4 Wichteln gibt es bereits 240 Strategien. Die Anzahl der Strategien lässt sich sicher durch "intelligente" Reduktionen verkleinern (z.B. wird man Strategien, die durch Permutation der Wichtel auseinander hervorgehen, als äquivalent ansehen können). Aber ihre Anzahl wird "groß" bleiben, um es vorsichtig auszudrücken.

    Einen Beweis dafür, dass es zu jeder Strategie der Wichtel mindestens eine Wahl des Weihnachtsmannes gibt, also eine 15 stellige Folge von (verschiedenen) Wichteln und eine Farbe für den 16. Wichtel (Mr.X), so dass Quibo nicht weniger als 4 Wichtel als Kandidaten für Mr.X bestimmen kann, ist nicht bekannt, oder habe ich was überlesen?

    Ich suche seit Tagen danach, bin aber wohl zu blöd, es sei denn, der Beweis ist tatsächlich schwierig bzw. die ganze Vermutung ist falsch.


    Naheliegende Verallgemeinerung: statt 16 bzw. 17 Wichtel seien es n2 bzw. n2 + 1 Wichtel und die beste Strategie liefert n Wichtel als Kandidaten für Mr.X.

    Herrlich, ich liebe diese Mützenrätsel, einmal mehr: dickes Dankeschön an Aart Blokhuis und Gerhard Woeginger.

    Wenn man die Lösung hat (14 Wichtel dürfen Kaffee und Kuchen essen), ist sie in der Rückschau gar nicht so kompliziert wie zunächst vermutet.


    Hier eine Lösungsvorschlag zur knackigen Mützenaufgabe 2020 mit Erklärungsansatz, wie man auf die Strategie kommen kann:

    https://www.dropbox.com/s/gwh4…Knackige_Muetzen.JPG?dl=0

    Sehr schöne Lösung resp. Strategie. Und erstaunlich einfach. (Warum nur bin ich nicht darauf gekommen? :().

    Die Vermutung liegt nahe, dass eine bessere Strategie nicht existiert. Aber wie beweisen? Vielleicht gibt's ja im Lösungsheft einen Hinweis.

    (Ist natürlich für die Lösung hier im Kalender ohne Belang.)

    Sehr schöne Aufgabe, wie auch die Aufgabe davor. Beide wirken erst harmlos, fast langweilig, enthüllen dann aber einen sehr interessanten Kern, insbesondere die gestrige Aufgabe.

    Es geht ja nicht einfach um die Lösung - die konnte man gestern schnell mit einfacher Programmierung erhalten - sondern um Zusammenhänge, Beweise, Verallgemeinerungen usw.

    Erstmal schnell mit dem grossen Rechenknecht die Richtung bestimmt. Aber dann die wahre Schönheit der zu-fuss Lösung entdeckt. Und dabei längst vergessene Fähigkeiten wiederentdeckt. Das einzige, was mich stört ist, [...]


    Und dann sind das viiieeel zu wenige Pakete. Das reicht ja noch nicht mal für alle die beim Kalender mitspielen :-(

    Genau so ging es mir.

    Diese "wahre Schönheit" - und ich nehme an, wir meinen die gleiche - habe ich heute morgen, kurz nach 6, direkt nach dem Aufwachen, entdeckt. Ist tatsächlich so.

    Gestern hatte ich aus lauter Faulheit die Aufgabe noch auf die billige Weise gelöst. (Und dabei, wie ich gerade merke, noch einen blöden Fehler gemacht !)

    Ein Wolf im Schafspelz, diese Aufgabe. :thumbsup:

    Zur Klärung:


    1) Beide, Ralph und Steffan, werden kein Amt (ungleich NP) zweimal ansteuern

    2) Ralph wird nach 204 Minuten zurück sein, Steffan früher

    3) Es ist aber prinzipiell nicht verboten, dass beide das gleiche Amt ansteuern

    4) Beide dürften prinzipiell auch gleichzeitig den gleichen Weg in die gleiche Richtung oder in verschiedene Richtungen nehmen

    5) Zu optimieren ist die Zeit des Langsameren (die Zeiten werden nicht addiert z.B.)


    Ist das alles so korrekt?

    Ich denke das ist eine Aufgabe nach dem Motto: entweder man kommt auf die Lösung, oder man kommt nicht (sofort) drauf.

    Wenn man nicht drauf kommt, ist es knifflig sich durchzubeißen.

    Wenn man die Lösung hat, erscheint die Aufgabe sehr simpel. Ist sie aber nicht für alle.


    Sich selbst in die Lage der Wichtel zu versetzen und um die Ecke zu denken hilft.

    Genau. Man muss drauf kommen, dann fällt die Aufgabe geradezu in sich zusammen. Aber so ist es ja häufig. Ich hatte auch erst verspätet die entscheidende "Erleuchtung".

    Wie sähe die Strategie und Antwort wohl bei 21 Wichteln aus?

    Und ändert sich was, wenn man 3 Mützenfarben hätte?

    Die gleiche Idee, die diese Aufgabe löst, lässt sich, in nahe liegender Weise verallgemeinert, auf den Fall beliebig vieler Wichtel (die dann höchstens ein Verständigungsproblem bekommen (2 mtr Abstand!)) und beliebig vieler Farben anwenden. Nur muss die Menge der möglichen Farben natürlich allen bekannt sein.

    Irgendwie verblüffend, aber irgendwie auch etwas enttäuschend.

    Die eine oder andere Mützenaufgabe der letzten Kalender konnte einen ja schon in die Nähe des Irrsinns treiben. Das ist dieses Mal nicht der Fall, gut so.

    Alles in allem: schöne Aufgabe.

    Vollkommen verunsichert von den posts hier hab ich heute (im Gegensatz zu den vergangenen Jahren) auch noch den optimalitätsbeweis in Angriff genommen. So, jetzt ist meine Antwort sogar bewiesen. Jetzt muss sie nur noch stimmen ;-)

    Darin, für die Lösungen einen Beweis zu suchen und hoffentlich zu finden, besteht ja der eigentliche Reiz des Kalenders (und ist, wenn es nicht gelingt, Quelle für Frustgefühle). In diesem Falle allerdings ist, wenn man die Lösungsidee einmal hat [...] Ich gebe aber zu, diese Idee (leider) nicht sofort gehabt zuhaben.

    Da es hier ja einige Verwirrung bzgl der Möglichkeit/Unmöglichkeit von "Verschiebungen" zum realen Kalender gab, hier nun auch mein Versuch das zu klären. Grundsätzlich sollen die Aufgaben des Mathekalenders (also auch diese konkret) ohne auf nicht im Text enthaltene Fakten angewiesen zu sein lösbar sein.

    Das Wissen auf welchen Wochentag ein bestimmtes historisches Datum nun tatsächlich fiel, wäre aber ein solcher nicht im Text enthaltener Fakt.

    Ich hoffe dieser Beitrag erklärt mehr als er verwirrt und ist auch kein unzulässiger Hinweis. Falls eins von Beidem doch der Fall sein sollte, natürlich bitte löschen.

    Also, ich werd noch irre. Dass es Wochentage mit den im Deutschen üblichen Bezeichnungen gibt, dass es eine ganz bestimmte periodische Reihenfolge gibt, also Sonntag, Montag, Dienstag usw...., dass sich also die Wochentage alle 7 Tage wiederholen, dass heute, der 11.12.2020, ein Freitag ist ..., dass der achte Hochzeitstag (ist das ein "historisches Datum") ein Montag ist (ist das ein "Fakt", der nicht im "Text" steht?), ist das alles nicht selbstverständlich?

    Was soll die ganze Eierei?

    Entschuldigung, wenn das unfreundlich klingt, ist nicht so gemeint. Ich liebe den Kalender. Es wundert mich nur, dass wir so gar nicht zusammen kommen. Ich frage mich, was ich da nicht verstanden habe.