Lösung Aufgabe 18

[Anonymous]

Hi!
How do you know that {(x,x-y,x+y,y) | x,y = 0,1,2 mod (3)} will in fact give you the quadruples with the desired characteristics?

[Anonymous]

I honestly also do not see it immediately that they would for sure fulfill the criteria. It still is very easy to verify symbolically that equality of any two of the entries guarantees equality of all of them, which is sufficient here (while any pair of them shares one entry, that fact is not required for the construction to work, but can be derived). The x+y=a+b and x-y=a-b => x=a and y=b part, being the least straight forward one, is still easily shown by adding or subtracting the two equalities.

I still like the construction, but I would also be interested to know where it comes from and whether there is an easier certificate for why it would work.

I really don’t want to take away anything from this really neat trick to generate the required set since it works so beautifully, but I personally found the set to be constructible pretty easily in any case once I knew what I was looking for

[Anonymous]

Die 72er Lösung zu finden ist m.E. eine außergewöhnliche Leistung – Chapeau!
@Pierrot_: Ich denke, dass „im Gesamtsystem Farbkonstellation“ 60 nicht das Optimum darstellt – sondern 69!

Die Grund-Idee hierzu kam mir anhand der Lösung der „Vorgängeraufgabe“ vom 12.12.2019 (ähnliche, deutlich einfachere Konstellation mit nur 3 statt 4 Wichteln).
Bei folgender Strategie reagieren alle Wichtel nach den gleichen Regeln, und dies nur anhand der zu sehenden 3 Mützenfarben (unabhängig von der Reihenfolge – d.h. es gibt nur 10 Regeln) – und zwar wie folgt (E = Enthaltung = T7):

1,2,3 → E
1,1,2 → E
1,1,3 → „2 oder 3“
2,2,1 → „1 oder 3“
2,2,3 → E
3,3,1 → E
3,3,2 → „1 oder 2“
1,1,1 → „1 oder 2“
2,2,2 → „2 oder 3“
3,3,3 → „1 oder 3“

Für die 81 Konstellationen bedeutet dies:
– genau eine Farbe doppelt:
in allen 36 Fällen rät ein Wichtel richtig, 3 enthalten sich
– zwei Farben doppelt:
in allen 18 Fällen raten 2 Wichtel richtig und 2 enthalten sich
– eine Farbe dreifach:
in 12 der 24 Fälle (1,1,1,2 / 2,2,2,3 / 3,3,3,1) rät ein Wichtel richtig, 3 enthalten sich
in den übrigen 12 Fällen raten alle 4 Wichtel falsch
– eine Farbe vierfach:
in allen drei Fällen raten alle 4 Wichtel richtig

Insgesamt wird damit die erste Runde in 69 der 81 Fälle überstanden,
in der nachfolgenden 2. Runde kann dann mind. ein Wichtel (wohl sogar mind. 3 Wichtel) die richtige Mützenfarbe angeben.

Dankenswerterweise wurde vom Aufgabensteller diese zwar auch nicht ganz einfach zu findende, aber deutlich übersichtlichere 69er Lösung mit der noch wesentlich komplexeren 72er Lösung in einer Antwort zusammengefasst, so dass beides zur richtigen Lösungs-Nummer (9) führt.

[Anonymous]

@Eidus: Nice!!! und natürlich Glück gehabt, dass Du in die range 68-72 gerutscht bist 🙂

allerdings unterscheidest du ja doch noch eine Stufe tiefer, in dem du nicht nur die Anzahl der Farben (wie in meiner Lösung: da ist das Optimum 60), sondern innerhalb der Anzahl der Farben auch noch nach den verschiedenen Farben sortierst. Bei meinen ersten Überlegungen gab es einfach nur drei Unterscheidungen: ein Wichtel sieht eine, zwei oder drei verschiedene Farben (unabhängig davon welche Farben).

Toll, wie viele verschiedene Strategien man sich überlegen kann, aber eben nur eine, bei der man sich dann auch sicher sein kann, dass sie optimal ist 🙂

[Anonymous]

Hat eigentlich jemand mal den „Brute-Force-Ansatz“ für die erste Runde probiert? Also alle 81 Mützenverteilungen gegen die 256 Strategien (Wichtel 1-4 zeigt jeweils eine Tafel aus 4-7; die Tafeln 1-3 werden zunächst vernachlässigt; wenn der Computer rechnet, dann kann man sie schon reinnehmen, sind dann aber direkt 2401 Tafel-Kombis) gehalten? Damit sollte doch die Struktur einer Lösung erkennbar sein, wenn es unter den 256 Tafel-Kombis aus Symmetrie mehrere mit 72 Erfolgen geben würde? Oder habt Ihr das zuerst gemacht und dann nach einer mathematischen Beschreibung / Erklärung gesucht?

[Anonymous]

Anonymous wrote:

Hat eigentlich jemand mal den „Brute-Force-Ansatz“ für die erste Runde probiert? Also alle 81 Mützenverteilungen gegen die 256 Strategien (Wichtel 1-4 zeigt jeweils eine Tafel aus 4-7; die Tafeln 1-3 werden zunächst vernachlässigt; wenn der Computer rechnet, dann kann man sie schon reinnehmen, sind dann aber direkt 2401 Tafel-Kombis) gehalten? Damit sollte doch die Struktur einer Lösung erkennbar sein, wenn es unter den 256 Tafel-Kombis aus Symmetrie mehrere mit 72 Erfolgen geben würde? Oder habt Ihr das zuerst gemacht und dann nach einer mathematischen Beschreibung / Erklärung gesucht?

Ich verstehe die Frage nicht. Es gibt keine Strategie im von dir genannten Sinne (festgelegte Schilderauswahl in Runde 1, unabhängig von den gesehenen Mützen), die in 72 von 81 Mützenverteilungen gut ist.
Oder habe ich dich falsch verstanden?

Die 72er-Strategien legen die gehobenen Schilder in Abhängigkeit von den gesehen Mützen fest.

[Anonymous]

Sorry, vielleicht etwas missverständlich formuliert…

Aus den 81 möglichen Mützenkombinationen ergibt sich, dass jeder der 4 Wichtel 27 Mützen-Kombis der jeweils drei anderen Wichtel zu sehen bekommt, auf die er dann jeweils in der ersten Runde mit den Tafeln 4-7 “antworten” kann, also hat jeder Wichtel insges. 108 Möglichkeiten. (“sehe Mützen-Kombi 1 von 27, zeige Tafel 4” bis “sehe Mützen-Kombi 27 von 27, zeige Tafel 7”; dies führt in einer optimalen Lösung zu maximal 27 “Tafel-Regeln” pro Wichtel je nach beobachteter Mützen-Kombi, die ein Wichtel lernen müsste; ggfls. hat auch nicht jeder Wichtel die gleichen “Tafel-Regeln”, aber mehr als 27 können es pro Wichtel nicht werden).

108 ^ 4 = 136.048.896 Kombinationen der jeweils 108 Möglichkeiten, dies sind doch dann alle möglichen Strategien (für das Zeigen der Tafeln 4-7 durch die 4 Wichtel in Abhängigkeit der jeweils beobachteten Mützen-Kombinationen), also insbes. darunter auch das Maximum mit den 72 Treffern?

[Anonymous]

Du hast da einen kleinen Rechenfehler – statt 27*4 musst du alle möglichen Kombinationen betrachten, 4^27 (über 10^16). Für alle vier kommst du also auf über 10^64, wenn mich nicht alles täuscht. Kurz gesagt – ich glaube nicht, dass irgendjemand bei der Aufgabe Unterstützung durch den Computer genutzt hat.

[Anonymous]

Hmmm, da hatte ich eher einen Verständnisfehler… Eine 6stellige Zahl aus je 10 Ziffern hat schließlich auch ein paar mehr Möglichkeiten als 6*10=60… Mehr als 10^64 sind dann wirklich schon ziemlich viele Möglichkeiten…

[Anonymous]

So abwegig ist es gar nicht, auf die Lösung zu kommen – wurde ja bereits schön in Beitrag 1 und 3 von murks und linsen_mit_spätzle erläutert! Lässt man sich nicht von einer Nebelkerze einlullen und gibt sich mit einem Ergebnis oberhalb von 54 zufrieden, sondern schaut wirklich auf die 81 verschiedenen Kombinationen einzeln!!
Hier ein Versuch an mancher Stelle einzelne Schritte der Taktikfindung noch genauer zu erläutern:

Eine optimale Strategie bedeutet, dass jeder Wichtel für jede der aus seiner Sicht 27 sichtbaren Kombination wissen muss, welches Schild T4-T7 er in die Höhe streckt.

Es muss also auf alle Fälle auch das 2 Farbenschild benutzt werden (sonst fallen ja alle raus).

Jetzt beginnt man einfach mit einem Wichtel der bei einer speziellen ihm sichtbaren (erst einmal völlig beliebigen) Kombi ein 2-Farbenschild hochhält etwa Atto, wenn er “bbb” erblickt.
Auch jetzt hat man bei der Konstruktion der optimalen Taktik noch alle Freiheitsgrade, welches 2-Farbenschild Atto hochhält, der Einfachheit halber nehmen wir die “inversen Farben”: Atto hält das Schild-“rg” hoch.

Damit haben wir aber eine 4er-Kombination, die auf alle Fälle verliert: nämlich wenn Atto eine blaue Mütze trägt: Also verliert die Kombi “bbbb”, aber man hat schon mal 2 Gewinnpositionen: rbbb und gbbb

Jetzt kommt die entscheidende Idee: die eh schon verlorene Kombi “bbbb” vierfach als verloren zu nutzen: nämlich auch für die anderen drei Wichtel: Sie verfahren in diesem speziellen Fall genau gleich: falls sie bbb sehen zeigen sie das “2-Farben-Schild rg”
Damit hat man pro Wichtel 2 gute, also kuchenbringende Kombinationen, die offensichlich alle verschieden sind: alle acht Nachbarkombinationen von bbbb. Bei nur einer schlechten Kombination bbbb.

Bei allen acht Nachbarkombinationen von bbbb hebt folglich nur genau ein Wichtel das Schild “rg” hoch und es gibt Kaffee und Kuchen, bei der schlechten Kombi bbbb heben alle 4 Wichtel “rg” hoch und sie verlieren quasi vierfach (ob ein oder vier Wichtel falsch liegen spielt aber keine Rolle!! so oder so schlecht): Jeder Wichtel hebt also nur in einem Drittel der Fälle ein 2Farben-Schild hoch (verliert davon wieder 1/3), sonst T7 (das ist der Clou) – ingesamt gehen so aber nur 1/9 der Fälle flöten: 1/3 * 1/3.

Besser geht nicht für diese 9 Kombinationen!! Man hat nun das Verähltnis: 8 Gute – 1 Schlechte: 8/9 zu 1/9:
Sprich im Otpimalfall verliert man bei allen 81 Kombination 1/9 (das aber mit Sicherheit)!!:

Der nächste Schritt liegt nun nahe: Man versucht, die verbleibenden 72 in 8 weitere solche 9er-Gruppen einzuteilen, gelingt dies – hat man mit Sicherheit die optimale Taktik: pro 9er-Gruppe eine schlechte Kombination, acht Gute – insgesamt also 9 schlechte Kombis und 72 Gute.

Letzter Schritt: Wie findet man diese 9 schlechten Kombis, dass das auch so aufgeht?

Damit man wirklich maximal ausbeutet: also bei allen 9 schlechten Kombinationen wirklich 8 gute Nachbarn erhält, folgt im Rückschluss, dass JEDE gute Kombi nur genau eine schlechte Kombi als Nachbar haben darf (Nachbar: nur eine Stelle der vier verschieden) – hieraus folgt, dass die schlechten Kombis mindestens 3 verschiedene Stellen haben MÜSSEN, da es bei nur zwei verschiedenen Stellen, ja eine gute Kombi “dazwischen” geben müsste, die just diese beiden schlechten Kombis als Nachbarn hat – und das darf nicht sein: Jede gute Kombi darf nur einen schlechten Nachbarn haben.
Zwei schlechte Kombis können aber paarweise auch nicht an allen vier Stellen verschieden sein, da man sonst die Bedingung: alle paarweise mindestens drei Stellen auseinander, nicht einhalten kann (an einer Stelle weiter auseinander bedeutet an einer anderen Stelle näher beisammen):

Folglich suchen wir nach 9 Kombinationen, die paarweise an genau einer Stelle übereinstimmen (sprich an genau drei Stellen verschieden sind) – “also gleichmäßig auseinander liegen”.

Diesen Sachverhalt kann man sich alternativ auch direkt aus oben begonnener Konstruktion herleiten:

Schauen wir uns eine der bisher acht guten Kombination an: eine Nachbarkombination von bbbb: etwa “brbb” (Bilbo hat rot).
Bisher kennt unsere Konstruktion nur “bbbb” als schlecht – für die drei anderen Wichtel kann sich bbbb aber nicht mehr ergeben, daher halten sie T7 hoch, nur Bilbo wird “rg” hochhalten und es gibt Kaffee und Kuchen.
Damit aber brbb eine gute Kombination bleibt, muss bbbb der einzig “schlechte” Nachbar von brbb sein – diese Überlegung gilt für alle Nachbarn von bbbb, damit ist aber direkt klar, dass alle Kombinationen, die sich an genau zwei Stellen von bbbb unterscheiden auch gut sein müssen, da dies ja gerade die Nachbarn der Nachbarn sind.
Da aber jede gute Kombination auch eine schlechte haben muss (wenn ein Wichtel ein 2-Farben-Schild hochhält, kann er grundsätzlich auch daneben liegen), folgt wiederum dass gewisse Nachbarn der Nachbarn der Nachbarn (an drei Stellen verschieden) schlecht sein müssen…

Es gibt viele verschiedene Möglichkeiten, diese 9 schlechten Kombis festzulegen – hier noch ein systematischer Ansatz, wie man schnell zum Ziel kommt. Interessant ist noch folgende Fragestellungen: Wie viele Möglichkeiten gibt es denn? 🙂

Die 9 Kombinationen müssen “gleichmäßig” auseinander liegen, paarweise an genau einer Stelle übereinstimmen.
Daraus folgt, dass unter den 4×9=36 Farben, jede Farbe gleich oft vorkommen muss: nämlich 12 mal – übertragen auf die Spalten: exakt 3 mal pro Spalte. Nun erreichen wir dies sehr schnell durch systematische Gruppierung (man beachte die Spalten):

b b b b
b r r g
b g g r

r b r r
r r g b
r g b g

g b g g
g r b r
g g r b

für b=0, r=1 und g=2: entpricht dies übrigens gerade {(x,y,x+y,x-y) | x,y = 0,1,2 mod (3)}

[Anonymous]

Anonymous wrote:

Es gibt sehr viele verschiedene Möglichkeiten diese 9 schlechten Kombis festzulegen – es wurde oben auch erläutert, wie man sie finden kann. Interessant ist noch folgende Fragestellungen: Wie viele Möglichkeiten gibt es denn?

Ich komme auf 72 (mit Programm).

[Anonymous]

Ohne Programm, aber mit meiner Konstruktionsvorschrift:
Es kann nur höchstens eine der Konfigurationen (0,0,0,0), (1,1,1,1), (2,2,2,2) beinhaltet sein, wir gehen einfach mal von (0,0,0,0) aus.
Danach müssen drei Einsen und eine Null, sowie komplementär drei Zweien und eine Null da sein, da gibt es vier Möglichkeiten, hier nehmen wir (0,1,1,1)
Wenn die Null an zweiter Stelle ist, muss es sowohl eine Eins, als auch eine Zwei an erster Stelle geben, bei beiden müssen die letzten beiden Konfigurationen noch eine Eins und eine Zwei haben, hier gibt es also noch zwei Möglichkeiten, also Faktor 2. Das sind also 24 Konfigurationen.

Jetzt also noch die Fälle ohne die drei obigen, wenn die alle nicht drin sind, dann müssen alle Zahlen in genau einer Kombination an drei Stellen voranden sein (sonst ist die jeweilige Viererkombination nicht überdeckt). Diese drei gleichen können paarweise nicht an der gleichen Stelle sein (mit (0,0,0,1) und (2,2,2,1) dürfte bei (x,x,x,1) keins der x eine Null oder Zwei sein, und bei (1,1,1,x) müsste x auch eine Eins sein).
Also haben wir für die drei-Nullen Kombination vier Stellen für die nicht-Null und zwei Möglichkeiten für die nicht-Null, o.b.d.A. (0,0,0,1). Damit muss die drei-Zweien Kombination eine Null an einer der ersten drei Stellen haben, und dann gibt es für die drei-Einsen Kombination noch zwei Mögliche Stellen, an der auch eine Zwei stehen muss, insgesamt 4*2*3*2 = 48.

Mit diesen Drei gesetzt ergibt sich der Rest von selbst, mit dem Wissen, dass jede Zahl an jeder Stelle genau dreimal vorkommen muss, mit einer Zahl an einer Stelle, die schon zweimal so vorkommt, alle anderen Stellen mit der da noch nicht vorkommenden Zahl besetzt sein muss (*):
z.B. (0,0,0,1); (2,2,0,2); (1,2,1,1) – ist der letzte Eintrag 1, so muss die Kombination (2,1,2,1) sein, ist der dritte Eintrag 0, so muss (1,1,0,0) herauskommen, ist der zweite eine 2, so muss es (0,2,2,0) sein. Mit diesen neuen dazu ergeben sich die restlichen Kombinationen aus 2 als erster Eintrag – (2,0,1,0), 0 als erster Eintrag – (0,1,1,2) und 1 an erster Stelle – (1,0,2,2)

zusammen: (0,0,0,1); (2,2,0,2); (1,2,1,1); (2,1,2,1); (1,1,0,0); (0,2,2,0); (2,0,1,0); (0,1,1,2); (1,0,2,2)
(*): eine Zahl kann an keiner Stelle mehr als dreimal vorkommen, da für jede andere Position nur drei Möglichkeiten existieren, und diese nicht doppelt vorkommen dürfen, wenn die eine andere Stelle gleich ist. Da wir neun Kombinationen suchen, muss also an jeder Stelle jede Zahl genau dreimal vorkommen.

Insgesamt gibt es also 24 Möglichkeiten mit einer Zahl, die viermal vorkommt, und 48 Möglichkeiten ohne solche, also 72.

[Anonymous]

Unter den Voraussetzungen dass
1. alle Wichtel gleich handeln,
2. in der ersten Runde nur die vier Tafeln “BG” “BR” “GR” “BGR” benutzt werden,
3. nur die Zusammensetzung der Mützefarben, die ein Wichtel sieht betrachtet wird
(also BBB BBG BBR BGG BGR BRR GGG GGR GRR RRR)
ergibt die brute-force-Lösung zwei Strategien, mit denen man in 69 Fällen (eine Runde) weiterkommt.

Die eine von “eidus”:

BBB -> BG; BBG -> BGR; BBR -> GR; BGG -> BR; BGR -> BGR; BRR -> BGR; GGG -> GR; GGR -> BGR; GRR -> BG; RRR -> BR;

und eine ähnliche (identische):

BBB -> BR; BBG -> GR; BBR -> BGR; BGG -> BGR; BGR -> BGR; BRR -> BG; GGG -> BG; GGR -> BR; GRR -> BGR; RRR -> GR;

Ich konnte aus Zeitgründen nur die og. 4^10 Strategien für die 81 “Kombi”-s testen.

[Anonymous]

Hübsch… Wenn es also 72 verschiedene 9er-Pakete gibt (9 schlechte Kombinationen, die paarweise an genau einer Stelle übereinstimmen), folgt direkt, dass eine feste Kombination (der 81 verschiedenen, etwa bbbb) in genau acht der 72 9er-Paketen vorkommt, da ja jede feste Kombintaion in gleich vielen 9er-Paketen vorkommen muss: 72*9/81=8

Umkehrung:
Wenn man also direkt zeigen kann (geht eventuell schneller Murks?!), dass eine feste Kombination in genau acht verschiedenen 9er-Paketen vorkommt, folgt auch direkt, dass es 72 9er-Pakete gibt: 81*8/9=72
aber vlt ist das eben doch nicht ganz so trivial – habe es noch nicht durchdacht :-)…

[Anonymous]

Super Idee, das macht den Beweis deutlich netter. Sowas wollte ich ursprünglich auch machen, habe aber den silbernen Faden nicht gefunden:
Für eine beliebige Kombination können wir wie für die (0,0,0,0) in meinem Beispiel vorgehen, da die Mützenfarben der verschiedenen Wichtel keine wirkliche Interaktion miteinander haben – am Ende ist der Graph (C3*C3*C3*C3) so symmetrisch, dass jeder Knoten identisch ist. (Gibt für jedes Paar Knoten eine Isomorphie, die den einen auf den anderen mappt – diese Isomorphie benennt im Prinzip einfach die Mützenfarben pro Wichtel um)
Also geht meine obige Argumentation für die Menge an 9-Knoten sets, die die (0,0,0,0) beinhalten für jeden Knoten, jeder ist in 8 Sets beinhaltet, also muss es 3^4*8/9=72 verschiedene Sets geben. Hübsch!

[Author]

Posts