Smalltalk

#matherätsel

a) Gegeben ist ein Zahlenschloss mit 3 Feldern, wobei jedes Feld nur die Ziffern 1, 2 oder 3 darstellen kann. Das Schloss öffnet sich, sobald man mindestens zwei der drei Ziffern richtig eingestellt hat und zu öffnen versucht. Wieviele Kombinationen muss man ausprobieren, damit man das Schloss sicher öffnen kann?

b) Wie lässt sich das beweisen?

Ich bin schon gespannt, welche Beweise euch einfallen.

Ach ja: lösungen wie immer bitte nur per PN an mich

es gibt bereits drei chessmailer, die sich an dieser aufgabe versucht und mir lösungsideen geschickt haben. ich gehe davon aus, dass noch mehr daran knobeln, ohne sich bisher gemeldet zu haben.

ich werde jedem teilnehmer zwei versuche für aufgabe a gewähren. aufgabe b kann beliebig oft probiert werden.

Ich glaube, ich sehe hier einfach den Haken nicht, denn das erscheint mir allzu einfach, jedenfalls zu einfach, als dass du das hier als Aufgabe stellen würdest. Aber Aufgaben zur Kombinatorik haben meist einen solchen versteckten Haken. Wir haben seinerzeit Aufgaben zur Kombinatorik im Lehrerzimmer diskutiert und 3 Mathelehrer (einer davon ich) waren verschiedener Ansicht über die richtige Lösung bzw. den korrekten Beweis!

Auch ich bin der Meinung, dass die Lösung sehr simpel ist...und damit vermutlich falsch...

Die verschiedenen Lösungen der 3 Mathelehrer kamen übrigens dadurch zustande, dass wir alle drei die Aufgabenstellung jeweils etwas anders aufgefasst hatten (ein Phänomen, das ich übrigens auch nur bei Aufgaben zur Kombinatorik erlebt habe!).
Hier ist jedenfalls nicht gefragt, wie viele 'gültige' Kombinationen es gibt (welche das Schloss öffnen), sondern wie viele man ausprobieren muss. Und da geht es schon los: gehört die anfangs eingestellte Ziffernkombination dazu, gilt sie als 'ausprobiert'? Oder kann man davon ausgehen, dass die Ausgangs-Kombination das Schloss nicht öffnet?

>Wieviele Kombinationen muss man ausprobieren<

ich lese es so, dass man aktiv probieren muss. Also nur weil das Schloss mit der Einstellung 1-2-1  vorliegt heißt es nicht, dass ist die Einstellung als ausprobiert gilt.

NOLF sieht das ganz richtig. Nur weil das schloss auf eine zahlenkombination eingestellt ist, hast du sie damit noch nicht ausprobiert.

Und da dieser vorschlag jetzt schon häufiger kam, will ich das noch offen besprechen:

Eine simple methode wäre, einfach die dritte ziffer zu ignorieren und alle anderen kombinationen auszuprobieren. So kommt man auf 3x3=9 versuche im worst case. Es geht aber besser!

Ja, das war auch meine erste Idee gewesen, aber dann habe ich schon gemerkt, dass man dann zu viel ausprobiert.

ok das scheint ein harter brocken zu sein. inzwischen sind schon fünf knobler in meinem postfach zusammengekommen, aber lösen konnte bisher noch keiner.

dass die lösung schwerer ist, als sie zuerst aussieht, ist mir damals selbst aufgefallen. mein erster gedanke war, dass hier so lächerlich wenige möglichkeiten existieren, dass es doch eigentlich nicht so schwer sein kann, das zu lösen. die aufgabe hat mich dann aber doch mehr gehirnschmalz gekostet als erwartet.

ich habe übrigens meine meinung über aufgabe a geändert: wer mir eine menge an tripeln anbietet, die eine korrekte lösung darstellen, darf vorher so oft falsch liegen, wie er oder sie will. denn das ist auf jeden fall eine leistung.

Die erste korrekte lösung ist da 👏


Geissbock löst aufgabe A mit einer korrekten menge an tripeln.

Geissbock hat einen beweis gefunden, der im prinzip identisch zu meinem ist.

Damit hat er als erster das rätsel vollständig gelöst 👏

>> wer mir eine menge an tripeln anbietet, die eine korrekte lösung darstellen<<

Mit Zahlen (also z.B. (1,2,3) für die Ausgangsposition) oder allgemein mit Variablen (z.B. (a,b,c))?

Wenn du mir lieber variablen schicken willst, ist mir das auch recht. Hier ist ja sowieso alles beliebig austauschbar.

(1,2,3) berücksichtigt halt z.B. nicht, dass auch Ziffern gleich sein können. Aber auch bei (a,b,c) meint man nicht unbedingt, dass z.B. a=b sein kann. Ich frage mich gerade noch, ob das einen Unterschied für die Lösung macht. Wahrscheinlich nicht.

Nein, die variablen müssen dann schon für unterschiedliche ziffern stehen. Ich sehe zumindest nicht, was das sonst für eine aussagekraft haben sollte.

Dann muss man verschiedene Fälle unterscheiden, und es wird sehr kompliziert aufzuschreiben.

Dann rate ich dringend davon ab 😄

@Vabanque
"... und es wird sehr kompliziert aufzuschreiben."
Du möchtest da nicht meine Tabellen sehen 😁

ein kleiner zwischenstand:

stand jetzt ist die zahl der einsender von lösungsvorschlägen auf 8 angewachsen. und manche davon bleiben mit bemerkenswerter hartnäckigkeit dran 👍

ich freue mich, dass diese doch nicht ganz einfache aufgabe so viel interesse findet.

falls jemand gewillt ist, die lösung ganz alleine und ganz sicher zu finden, ist das folgende das notwendige vorgehen:
- es muss eine lösung mit n tupeln gefunden werden
- es muss bewiesen werden, dass eine lösung mit n-1 tupeln nicht möglich ist

nur so könnt ihr euch ganz sicher sein, dass eure lösung richtig ist. tatsächlich war mein vorgehen umgdreht: ich habe erst bewiesen, dass es für eine bestimmte anzahl tupel unmöglich funktionieren kann, und dann eine lösung für ein tupel mehr gefunden. letzeres war nach ersterem gar nicht mehr schwer, weil damit klar war, welche voraussetzungen für die lösung gelten müssen.

es gibt tatsächlich im prinzip nur eine einzige lösung (oder ggf. zwei, wenn eine bestimmte umstellung in meiner lösung keine gültige permutation darstellt, da bin ich mir gerade nicht ganz sicher), die aber zahlreiche permutationen aufweist. soll heißen: es gibt viele lösungen, die aber im grunde identisch sind, weil sie alle eine notwendige voraussetzung erfüllen und ansonsten nur gleichwertige umstellungen der tripel darstellen. beispiel: wäre die tripel-menge (1,2,1), (2,3,2) eine lösung, wäre zwangsläufig auch (3,2,3), (2,1,2) eine lösung, weil hier einfach nur ziffern vertauscht wurden. und es gibt viele solche gültigen vertauschungen.

Hmm…. Mich verwirrt dein Beispiel: verstehe ich dich richtig, wenn (2,3,2) eine Lösung ist, dann auch (3,2,3)? Das heißt es ist egal an welcher Stelle die vermeintlich richtige Ziffer steht??

eine lösung für die aufgabe besteht niemals nur aus einem tripel! sie besteht immer aus einer menge von tripeln, und die müssen korrekt zueinander angeordnet sein. ein einzelnes tripel ist für die lösung gänzlich nutzlos.

"wenn (2,3,2) eine Lösung ist, dann auch (3,2,3)?"

<-- das kann also niemals der fall sein.

"wäre die tripel-menge (1,2,1), (2,3,2) eine lösung, wäre zwangsläufig auch (3,2,3), (2,1,2) eine lösung"

<-- das könnte der fall sein. es ist hier aber natürlich nur ein beispiel. eine tatsächliche lösung besteht aus mehr als zwei tripeln.

@toby84

Bin auch verwirrt:
Du schreibst oben
"- es muss eine lösung mit n tupeln gefunden werden"
zuletzt aber
"eine tatsächliche lösung besteht aus mehr als zwei tripeln."

Ein Tupel oder mehr als zwei Tripel?

Ich dachte, eine natürlich Zahl ist gefragt, die Anzahl der Versuche zum sicheren Öffnen?

Tripel, nicht tupel. ich habe mich oben verschrieben 🙂 Es geht ja immer um 3 ziffern, die ausprobiert werden, also tripel.

Und da steht "n tripel", also eine zu findende natürliche zahl an tripeln. Stellt euch doch einfach vor, was das bedeutet. 10 tripel entsprechen 10 versuchen, das schloss zu öffnen. Jeder versuch besteht aus drei ziffern, deshalb tripel. Diese 10 ist natürlich viel zu hoch, die möchte man so klein wie möglich machen. In obigem beispiel wäre die menge aus 2 tripeln also eine lösungsmenge [wenn sie a) alle möglichkeiten abdecken würde, was sie natürlich nicht tut und b) es keine menge aus einem tupel gäbe, das ebenfalls alle möglichkeiten abdeckt]

ist letzteres beispiel verständlich oder irritiert es noch mehr? gesucht ist wie gesagt die kleinste menge an tripeln, mit der man sämtliche existierenden tripel abdecken kann. auf diese weise kann man sich sicher sein: wenn man alle diese tripel ausprobiert hat, ist das schloss garantiert offen! und das geht, wenn ich beispielsweise a) 2 tripel finde, mit denen ich sämltiche möglichkeiten abdecke, und b) beweise, dass es mit einem tripel nicht geht. es ist offensichtlich, dass es mit einem tripel nicht geht. ähnlich offensichtlich ist es, dass es mit zwei tripeln nicht geht, aber ich will nur das prinzip verdeutlichen. a) und b) in diesen beispielen beziehen sich übrigens exakt auf die teilaufgaben a und b in der anfänglichen aufgabenstellung.

macmoldis hat erfolgreich zur lösung der aufgabe a hingearbeitet 👏

macmoldis hat aufgabe b gelöst.

ich bin übrigens kulant bei der lösung von aufgabe b. ich erwarte keinen echt mathematischen beweis. es reicht mir, wenn klar wird, wie ihr das begründet. von mir wird es am ende einen mathematisch eindeutig nachvollziehbaren beweis geben.

braucht jemand mehr bedenkzeit? sonst löse ich morgen auf

es wird mehr bedenkzeit geben. ich löse also frühestens am sonntag.

so, nun ist die wartezeit vorbei. diese aufgabe war schwerer, als ich erwartet hatte. insgesamt 12 chessmailer haben mir ideen und/oder lösungsvorschläge geschickt. wer weiß, ob nicht noch mehr dabei waren, die zwar gegrübelt, aber keine mails geschickt haben. und doch haben nur zwei chessmailer aufgabe a lösen können, und das mit fleiß und ausprobieren und heranarbeiten. dass die aufgabe nicht einfach ist, war mir bewusst. dass sie so schwer ist, war mir nicht bewusst.

aufgabe b war zugegebenermaßen tatsächlich schwierig. trotzdem hätte ich gedacht, dass es für manche machbar wäre. allerdings ist man als aufgabensteller immer vorurteilsbehaftet. man stellt ganz automatisch eher aufgaben, die man selbst gelöst hat, denn diese bereiten einem naturgemäß mehr freude.

beide mir geschickten lösungen für aufgabe b waren natürlich mathematisch nicht sauber, aber wer würde das schon erwarten. ich selbst bin mathematisch nicht so versiert, dass ich mir sicher bin, dass mein beweis kritiklos durchgehen würde.

bei geissbock habe ich die strukturierung der daten erkannt, die ich selbst für meinen beweis verwendet habe, auch wenn seine visualisierung ganz anders ist. bei macmoldis bin ich mir nicht ganz so sicher, aber sein fleiß bei dieser aufgabe gehört m.e. auf jeden fall honoriert.

mein beweis folgt in kürze.

Es folgt die Lösung. Ich beginne mit dem Beweis, dass es mit 4 Tripeln nicht gehen kann. Daraus ergibt sich direkt die Lösung mit 5 Tripeln. Zuerst ein paar Definitionen:

Definition 1: Knoten
Gegeben ist ein Würfel der kantenlänge 2, eingebettet in ein Koordinatensystem. Der kleinste Wert in allen Dimensionen ist 1, der größte 3. Auf diese Weise lassen sich über die drei Raumdimensionen Punkte auf und in dem Würfel definieren. Dabei werden sämtliche Punkte auf und in dem Würfel markiert, bei denen alle drei Raumdimensionen ganzzahlig sind. Das sind alle Tripel (x,y,z), für die gilt:
1<= x,y,z <=3 und
x,y,z sind natürliche Zahlen.
Diese Punkte werden im Folgenden als Knoten bezeichnet. Die Knoten sind äquivalent zu den Tripeln, mit denen man das Schloss zu öffnen versuchen kann.

Damit haben wir genau 27 Punkte im Würfel definiert, die sämtlichen Zahlentripeln entsprechen, die man als Lösungskombinationen im Schloss ausprobieren kann.

Knoten lassen sich aktivieren: das bedeutet, dass das zugehörige Zahlentripel am Schloss ausprobiert wird.

Knoten lassen sich markieren: wird ein Knoten aktiviert, werden einige der anderen Knoten markiert. Das bedeutet, dass man sie ausschließen kann, weil ein Knoten aktiviert wurde, der hinreichend nah am zu markierenden Knoten ist.

Um die Aufgabe zu lösen, müssen mit möglichst wenigen aktiven Knoten sämtliche Knoten im Würfel entweder aktiv oder markiert sein.

Definition 2: Kanten
Alle zuvor definirten Punkte werden mit allen solchen anderen Punkten durch eine Kante verbunden, deren Abstand zu ihnen genau 1 ist [das verbindet beispielsweise die Punkte (1,1,1) und (1,1,2), aber nicht (1,1,1) und (1,2,2)].

Auf diese Weise haben wir ein Gitternetz zwischen die Punkte gelegt.


Was passiert, wenn man einen beliebigen Knoten aktiviert (d.h. eine beliebige Ziffernkombination ausprobiert)?

Laut Voraussetzung öffnet sich das Schloss, wenn mindestens zwei der drei Felder, die das Zahlenschloss beinhaltet, korrekte Ziffern enthält und man dann das Schloss aktiv zu öffnen versucht. Nehmen wir also an, dass die richtige Lösungskombination das Tipel (1,1,1) wäre, so würde auch beispielsweise das Ausprobieren der Tripel (1,1,2) und (1,1,3) dazu führen, dass das Schloss sich öffnet. Für das korrekte Zahlentripel gilt: für jede Ziffer gilt, dass man an ihrer Stelle eine andere Ziffern einsetzen könnte, und das Schloss würde sich trotzdem öffnen. Es stehen für jede Ziffer zwei alternative Ziffern zur Verfügung. Das lässt sich auf jedem der drei Felder ausführen. So kommt man neben dem tatsächlich ausprobierten Tripel auf 2x3 = 6 weitere Tripel, die man ausschließen kann. Man kann also insgesamt genau 7 Tripel als Lösungstripel ausschließen, falls das Schloss sich nicht öffnet. Beispielsweise: falls (1,1,1) das Schloss nicht öffnet, schließt das zusätzlich aus:
(1,1,2), (1,1,3)
(1,2,1), (1,3,1)
(1,1,2), (1,1,3)

In unserem Würfel entspricht das exakt allen anderen Knoten, denen wir begegnen, wenn wir allen Kanten auf geradem Weg folgen, die von unserem Startknoten wegführen.

Ich habe eine hässliche Skizze davon gemacht, wie das Gitter aussieht, aber die ist es einfach nicht wert, hier eingefügt zu werden. Und online ein geeignetes Bild zu finden ist gar nicht so einfach. In folgendem Link sind 5 Würfel zu sehen, die aus kleineren Würfeln bestehen. Der zweite von links ist derjenige, der unser Gitter gut darstellt. Hier wäre beispielsweise links unten der Knoten (1,1,1), darüber kommen (1,1,2) und (1,1,3). Nach rechts unten kommen (1,2,1) und (1,3,1). Ganz rechts oben wäre (3,3,3). Ich hoffe, das ist anschaulich genug.

img.freepik.com/darmowe-wektory/model-szkieletowy-szescianu-o-..


Definition 3: Ebene

Wir legen eine der drei Ziffern des Zahlenschlosses auf eine bestimmte Ziffer fest, z.b. 1. Eine Ebene ist dann definiert als die Menge aller Punkte, die an der bestimmten Stelle die zur Ebene gehörende Ziffer aufweisen. Nehmen wir beispielsweise die Ebene z=3, so erhalten wir die 9 Punkte der Ebene:

(1,1,3), (1,2,3), (1,3,3), (2,1,3), (2,2,3), (2,3,3), (3,1,3), (3,2,3), (3,3,3)

Im Würfel aus dem Link wären das die 9 Punkte, die das Dach bilden.


Beweisführung:

Im folgenden betrachten wir, was innerhalb einer Ebene passiert, wenn wir Knoten aktivieren. Es gilt zwei Fälle zu unterscheiden:

Fall 1: der aktivierte Knoten befindet sich auf der Ebene: in diesem Fall können 4 weitere Punkte auf der Ebene markiert werden. Beispiel: der Knoten (1,2,3) wird aktiviert. Auf der Ebene z=3 können wir somit zusätzlich ausschließen: (2,2,3), (3,2,3), (1,1,3), (1,3,3). Das ist immer der Fall, weil es immer zwei variable Ziffern gibt, für die 2 alternative Werte eingesetzt werden können. Somit kommen wir auf 2x2 = 4 zusätzliche Knoten.

Fall 2: der aktivierte Knoten befindet sich nicht auf der Ebene. In diesem Fall kann genau ein Knoten auf der Ebene markiert werden, nämlich genau der, der aus der Vogelperspektive betrachtet auf derselben Linie liegt wie der aktivierte Knoten. Beispiel: der Knoten (1,2,2) wird aktiviert. Auf Ebene z=3 können wir ausschließlich den Knoten (1,2,3) markieren.


Beweis durch Widerspruch: angenommen, es ist mit 4 aktiven Knoten möglich, den gesamten Würfel zu markieren.

Nehmen wir an, dass wir den Würfel in die drei Ebenen z=1, z=2 und z=3 aufteilen (für die Beweisführung ist es egal, welche Ebenen wir genau verwenden. Wichtig ist nur, dass sie zusammen den Würfel vollständig abbilden). Für jeden aktiven Knoten gilt: er befindet sich auf exakt einer dieser Ebenen. Das ist trivial richtig, weil die dritte Ziffer in einer einzigen Zahlenkombination immer nur einen einzigen Wert annehmen kann.

Da es vier aktive Knoten und drei Ebenen gibt, ist Folgendes zwangsläufig wahr: es gibt mindestens eine Ebene, auf der sich kein oder nur ein Knoten befindet. Nennen wir diese Ebene e_min. Wir unterscheiden:

Fall 1: auf e_min befindet sich kein aktiver Knoten: durch die Knoten auf anderen Ebenen lässt sich jeweils höchstens ein Knoten auf e_min markieren. Bei 4 aktiven Knoten macht das 4 markierte Knoten. e_min hat aber 9 Knoten. Damit ist bewiesen, dass in Fall 1 in e_min unmöglich alle Knoten markiert sein können.

Fall 2: auf e_min befindet sich genau ein aktiver Knoten: Dieser Knoten markiert 4 weitere Knoten auf e_min. Jeder der anderen drei Knoten, die auf anderen Ebenen aktiviert sind, markieren höchstens einen bisher unmarkierten Knoten auf e_min. 5+3= 8. e_min hat aber 9 Knoten. Damit ist bewiesen, dass in Fall 2 in e_min unmöglich alle Knoten markiert sein können.

Damit ist der Widerspruchsbeweis vollständig.

Es fehlt noch der Beweis, dass es eine Lösung mit 5 Knoten gibt. Der ergibt sich aus den vorherigen Überlegungen praktisch von selbst. Wir wissen auch bei 5 Knoten, dass es mindestens eine Ebene e_min mit höchstens einem aktiven Knoten gibt (dass es dabei keine Ebene mit keinem aktiven Knoten geben darf, ist offensichtlich, den Fall ignoriere ich also). Egal wo der aktive Knoten ist, müssen die anderen vier Knoten von den anderen Ebenen aus die übrigen 4 Felder von e_min markieren. Und da gibt es kaum Möglichkeiten. Die Knoten dürfen nicht auf einer Linie liegen, sonst werden nicht genug Knoten markiert. Das kann jeder für sich selbst ausprobieren (ansonsten ergibt sich das auch aus einem anderen Beweis, den man führen kann. Falls Interesse besteht, kann ich den auch noch verschriftlichen). Somit hat man schon alles. Ein Beispiel:

wir legen einfach mal fest, dass unser aktiver Knoten auf e_min (1,1,1) ist. Also brauchen wir auf den anderen Ebenen Knoten, die (2,2,x), (2,3,x), (3,2,x), (3,3,x) abdecken. Damit sie nicht auf einer Linie liegen, kombinieren wir (2,3,x) mit (3,2,x) und (2,2,x) mit (3,3,x). Als Lösung ergibt sich:

(1,1,1), (2,3,2), (3,2,2), (2,2,3), (3,3,3).

Das ist nur eine von vielen Möglichkeiten. Immerhin kann jeder der 27 Knoten der aktive e_min-Knoten sein, alle anderen werden dann an diesen ersten Knoten angepasst.

Wie zeichnet sich der e_min-Knoten aus? Für jedes seiner Felder gilt: Auf demselben Feld hat keiner der anderen Knoten dieselbe Ziffer stehen. Es ist quasi der einsame Knoten in unserem Würfel. In oberem Beispiel sieht man das sehr gut: (1,1,1) ist der einsame Knoten, deshalb darf die 1 nirgendwo anders mehr vorkommen. Sobald ich auf diesen Trichter gekommen war, war das prüfen von mir engesandten Lösungen deutlich einfacher. Damit hatte ich zwar nicht alles abgedeckt, aber der einsame Knoten macht es doch sehr wahrscheinlich, dass hier tatsächlich eine Lösung gefunden wurde.

Ich hoffe, dass diese Lösung hinreichend verständlich war. Es ist gar nicht so einfach, eine Aufgabe rein schriftlich darzulegen, für die man meiner Ansicht nach eigentlich eine eigene Zeichnung braucht, um alles nachzuvollziehen. Und es ist auch nicht so einfach, den Spagat zwischen möglichst mathematisch korrekter Formulierung und verständlicher Sprache zu schaffen.

Falls Fehler in der Beweisführung sind, könnt ihr mich gerne darauf aufmerksam machen. Dann werde ich diese korrigieren. Der Text ist lang und der Tag war lang, ich habe nicht alles penibel überprüft.

Ein guter Freund, dem ich die Lösung gezeigt habe, hat mich gefragt, ob es einen simplen Algorithmus gibt, mit dem man in jeder beliebigen Konstellation die Lösung konstruieren kann. Den gibt es tatsächlich. Fall hier Interesse besteht, veröffentliche ich den auch gerne.

Unabhängig davon, ob hier noch weitere Posts folgen, will ich mich an dieser Stelle schon mal für die unerwartet rege Beteiligung bedanken. Ich hoffe, die Aufgabe hat Spaß gemacht, auch wenn nicht jeder eine optimale Tripel-Menge gefunden hat 🙂

Obwohl ich glaube, in Mathe nicht ganz untalentiert zu sein, kann ich das nicht nachvollziehen oder zumindest lässt meine Konzentration beim Lesen der Lösung stark nach. Das ist ähnlich wie Mathematikstudium, vor dem ja immer gewarnt wird.

Ich nehme jetzt mal eine eingestellte Zahlenkombi an, (z.B. 3;3;3).
Ich gebe jetzt mal eine erste Zahlenkombi vor, die eingestellt wird (1;1;1), die erste Einstellung dürfte ja beliebig sein.
Jetzt möchte ich Schritt für Schritt die weitere schlüssige Verfahrensweise hören. Nach der 5. Einstellung muss die eingestellte spätestens dabei sein.

Ich habe das mal mit einem sogenannten Baumdiagramm das Problem nachvollzogen und immer nicht mehr mögliche Pfade gestrichen, sieben Versuche war jedoch das Minimum.

na der beweis scheint nicht verstanden worden zu sein. eine positiv formulierte pn bekommen, die aber doch zugibt, nicht alles verstanden zu haben. eine andere, die bezweifelt, dass der "zeichnerische beweis" von mathematikern wirklich akzeptiert wird. oh je, oh je 🙈 also um das klarzustellen: in diesem beweis dient die graphische darstellung über den würfel einzig und allein der veranschaulichung. so bin ich selbst auf die lösung gekommen. das mit der veranschaulichung ist offensichtlich gründlich nach hinten losgegangen. ich umreiße den beweis ohne würfel:

wir teilen die 27 möglichen tripel in drei gruppen. willkürlich verwenden wir dafür die dritte ziffer. alle mit dritter ziffer 1 kommen in gruppe 1, mit ziffer 2 in gruppe 2, mit ziffer 3 in gruppe 3. schauen wir uns gruppe 3 an:

(1,1,3), (1,2,3), (1,3,3), (2,1,3), (2,2,3), (2,3,3), (3,1,3), (3,2,3), (3,3,3)

was passiert, wenn wir ein tripel aktivieren (ausprobieren), das nicht in gruppe 3 ist? zum beispiel (1,1,2)? dann können wir in gruppe drei nur ein einziges tripel als getestet markieren, nämlich (1,1,3). was passiert, wenn wir ein tripel in gruppe 3 aktivieren? wir können 4 weitere tripel markieren, insgesamt also 5 tripel in der gruppe.

wir haben 3 gruppen. wenn wir nur 4 tripel ausprobieren würden, hätten wir also auf jeden fall eine gruppe mit höchstens 1 ausprobierten knoten, die anderen drei knoten wären in anderen gruppen. damit können wir eine gruppe schlicht nicht vollständig markieren, denn 5 + 3 = 8, aber die gruppe hat 9 tripel. so einfach ist das.

oben versuche ich nur, diese argumentation a) zu formalisieren und b) zu veranschaulichen. das klappt wohl nicht.

und ein beweis dafür, dass 5 tripel tatsächlich ausreichen, geht mit systematischem austesten einer der lösungen, die von selbst aus meinem beweis herauspurzeln. zum beispiel:

A (1,1,1), B (2,2,2), C (3,3,2) und D (3,2,3), E (2,3,3)

hinter jedem tripel stehen die aktiven tripel, durch die es abgedeckt ist.

1,1,1 A → aktiv
1,1,2 A
1,1,3 A
1,2,1 A
1,2,2 B
1,2,3, D
1,3,1 A
1,3,2 C
1,3,3 E

2,1,1 A
2,1,2 B
2,1,3 E
2,2,1 B
2,2,2 B → aktiv
2,2,3 B,D,E
2,3,1 E
2,3,2 B,C,E
2,3,3 E → aktiv

3,1,1 A
3,1,2 C
3,1,3 D
3,2,1 D
3,2,2 B,C,D
3,2,3 D → aktiv
3,3,1 C
3,3,2 C → aktiv
3,3,3 C,D,E

und @gammapappa: was die herangehensweise über baumdiagramm angeht: hier müsstest du dein vorgehen genauer erläutern.

und während ich das folgende hier so schrieb, hat's toby64 eins weiter obe nochmal anders erklärt ...

na ok, mit den Würfelnkoordinaten könnt ich mir das im ersten Moment noch räumlich vorstellen, aber irgendwann war's dann doch mit dem lesen aus

Dachte jetzt kommt eine Mathe-Formel, die das klärt

Zur Erklärung, ich hab's am Ende nicht mit Mathe sondern über probieren in einem Diagramm gemacht, markiert was öffnet und geschaut, daß ich mit fünfen alle Öffnung abdecke ...

Jede Zahlenkombination ermöglicht 7 Öffnungen
bspw. 1;2;3 öffnet abgesehen von 1,2,3 auch
1,1,3 / 1,2,1 / 1,2,2 / 1,3,3 / 2,2,3 und 3,2,3
beim Versuch mit insgesamt 5 solcher Triple dann alle 27 Öffnungen abgedeckt

macmoldis.de/nobs/tabschloss.png

Mit Vier klappte nicht, da 3 Triple überschneidungsfrei 21 Öffnungen abdeckten und für die verbliebenen 6 Öffnungen aufgrund der Konstellationen weitere 3 Triple nötig waren
und bei vier hätte es da insgesamt nur eine Überschneidung gegeben, das war nicht

korrektur: ok, das ist m.e. doch auch noch kein beweis, aber vll verstehe ich ihn noch falsch.

ich hatte aber noch einen zweiten beweis, den ich jetzt trotzdem hier anbringe: wenn zwei tripel auf einer ebene sind, füllen sie in der ebene nicht 5+5, sondern nur 5+3 tripel (sich selbst eingeschlossen), 2 "abdeckungen" gehen also zwangsläufig verloren. den grund spare ich mir an dieser stelle, das kann auch jeder für sich ausprobieren. wir haben 3 gruppen und 4 tripel. jedes tripel deckt maximal 7 tripel ab (es selbst eingeschlossen), insgesamt wären das 7*4 = 28 tripel. aber da auf jeden fall zwei tripel auf derselben ebene liegen müssen (4 tripel, aber nur 3 ebenen), gehen zwangsläufig 2 abdeckungen verloren, so kommt man nur auf 26. das reicht nicht, um 27 tripel abzudecken.


"und während ich das folgende hier so schrieb, hat's toby64 eins weiter obe nochmal anders erklärt"

die erklärung war dieselbe, ich ließ einfach den würfel weg.

Dass es in 5 Versuchen geht, hatte ich toby ja geschrieben ... nur hat er dies nicht als Lösung akzeptiert. Ich hatte es an einem konkreten Beispiel ausprobiert, konnte aber keinen allgemeinen Beweis führen bzw. habe mich damit dann nicht weiter beschäftigt.

also ich will jetzt deine mail nicht öffentlich zitieren, aber eine erklärung hast du da nicht wirklich geliefert, eher eine vermutung. und eine lösung mit 5 tripeln gab es auch nicht. das kann ich ja nicht als lösung gelten lassen. ich hatte extra früh echte lösungsmengen gefordert statt eine einzelne lösungszahl, um zu verhindern, dass jemand einfach immer weiter runter geht, bis er bei der richtigen zahl angekommen ist. deshalb lasse ich keine einzelne zahl mehr gelten. ich habe bei deiner mail ja auch explizit nochmal nachgehakt, wie genau du auf die 5 kommst, aber weitere erklärungen kamen nicht mehr.

>>und eine lösung mit 5 tripeln gab es auch nicht<<

Die hatte ich nur für mich aufgeschrieben. Ich wollte das nochmal prüfen, aber das war mir dann wirklich zu aufwändig. Es gibt ja schließlich noch andere Dinge im Leben😁

Alles ok, meine Lösung war ja keine echte, lege also keinen Wert darauf, als 'Löser' genannt zu werden, und alle Achtung, wer sich hier so reinvertieft hat, einen Beweis zu liefern👍

schade, ich hätte sie auch für dich geprüft 🙂 ich muss ja nur schauen, ob ein einsamer knoten darin vorkommt, dann hätte ich dir die lösung geglaubt.

macmoldis Lösung kann ich nachvollziehen, und sehe auch eindeutig das es 5 Versuche braucht.
Zusätzlich zu seiner Lösung (111;122;233;312;321) müßte es ja noch mind. zwei weitere geben (222;233;311;123;132) und (333;311;122;231;213)
Es gibt immer zwei völlig unabhängge Tripel mit je 7 Zweierkombinationen, dann wegen der Überschneidung eine mit 5 und zwei mit 4 Zweier, macht zusammen 27.
Wieviel Lösungen gibt es denn insgesamt?

Naja 54 halt. 27 tripel, die einsam sein können. der rest kann auf zwei arten verteilt werden.

Also selbst in kurzform ist meine lösung nicht nachvollziehbar? Dass sie funktioniert, ist offensichtlich. Die isolierten tupel sind auch in deinen lösungsvorschlägen gut zu erkennen:

(111;122;233;312;321)
(222;233;311;123;132)
(333;311;122;231;213)

Allle ziffern kommen an der entsprechenden stelle sonst nicht mehr vor.

ich habe spaßeshalber in meine berechnungsmatrix die einsamen tripel aus den drei beispielen eingegeben. das starttripel ist dabei das einsame tripel. die anderen tripel ergeben sich durch die in der matrix angegebenen rechenoperationen.


x || -1 || +1 || -1 || +1
y ||+1 || -1 || -1 || +1
z || +1 || +1 || -1 || -1

man kann in der matrix sämtliche werte einer beliebigen zeile umkehren, dann erhält man die alternativen lösungen.

das ganze funktioniert wie ein modulo-system. landet man bei 4, zieht man 3 wieder ab. landet man bei 0, addiert man 3.

man sieht hier schön, wie das einsame tripel einsam bleibt. indem jeder wert entweder um 1 verringert oder erhöht wird, ist garantiert, dass der ursprüngliche wert in den anderen tripeln niemals wieder auftaucht.

schauen wir uns den einsamen knoten im ersten beispiel an, erhalten wir über diese berechnungsmatrix exakt die 4 punkte, die in der lösungsmenge angegeben sind.

2 || 1 || 3 || 1 || 3
3 || 1 || 2 || 2 || 1
3 || 1 || 1 || 2 || 2

man vergleiche:

(111;122;233;312;321)

mit den anderen beiden lösungsmengen funktioniert es auch.

um das nochmal etwas aufzudröseln: was sehen wir hier?

- || A || B || C || D
x || -1 || +1 || -1 || +1
y ||+1 || -1 || -1 || +1
z || +1 || +1 || -1 || -1

ich habe die spalten jetzt einfach mal benannt in ABCD. wenn wir jede zeile einfach mal benennen nach den positiven einträgen, erhalten wir:

BD
AD
AB

das sind 3 der 6 möglichkeiten, zwei aus 4 zu ziehen. diese sind nämlich:
AB AC AD BC BD CD

jeweils zwei zeilen lassen sich als komplemente verstehen. AB ist beispielsweise das gegenstück zu CD, weil dabei sämtliche werte umgedreht sind. so erhalten wir die tabelle in neuer struktur:

AB - CD
AC - BD
AD - BC

wie gesagt können wir eine beliebige zeile umdrehen, um die alternative lösung zu erhalten. das lässt sich auch beliebig oft wiederholen. vertauschen wir AC mit BD, erhalten wir:


AB - CD
AC - BD
AD - BC

lassen wir hingegen die erste und dritte zeile nach rechts wandern, erhalten wir:

AB - CD
AC - BD
AD - BC

wir können die zwei lösungen, die es für jedes beliebige vorgegebene isolierte tripel gibt, also vereinfacht folgendermaßen beschreiben, denn alle anderen varianten sind nur umstellungen dieser beiden:


AB - CD
AC - BD
AD - BC

und

AB - CD
AC - BD
AD - BC

wichtig zu verstehen ist, dass wir hier jeweils zwei ausrichtungen sehen, die zusammengehören, weil sie gegensätze zueinander bilden. wir haben also drei "kategorien" von ausrichtungen. die matrix muss also einfach einen vertreter jeder der drei kategorien beinhalten, um eine gültige lösung für das rätsel zu sein.

diese ganzen erkenntnisse kamen mir nur, weil ich den grundgedanken, dass jeder knoten gleichberechtigt sein muss, konsequent weitergedacht habe. die erste erkenntnis war:
wenn es einen algorithmus gibt, um für einen einzigen knoten eine vollständige lösung zu konstruieren, dann muss dieser algorithmus für sämtliche knoten gelten. so entstand die matrix.
dann habe ich mir gedacht: es gibt zwei lösungen, die ich für meinen beispielknoten sofort sehe. um von der einen zur anderen zu gelangen, kann ich einfach die z-achse umdrehen. dann dachte ich mir: wenn die umformung einer dimension zu einer alternativen lösung führt, dann muss das für alle möglichen umformungen einer beliebigen dimension der matrix gelten. und so kam ich zu dieser auflistung.

ich finde sowas bemerkenswert. das sind diese momente in der mathematik, wenn man mit seinen verständnis-fähigkeiten irgendwo an den grenzen der aufgabe entlangschrammt und erkennt, dass da viel mehr drin steckt, als man zu anfang gedacht hat.


es ist schon sehr frustrierend, dass ich nicht in der lage bin, diese schöne lösung jemandem hier verständlich zu machen.

Also ich versuche das mal mit meinen einfachen Worten zu erklären.

Eigentlich sind es gar nicht meine, sondern die meines Sohnes,
dem ich die Aufgabe gestern auf einer Wanderung gestellt habe.
Ich durfte nicht spoilern und war schon ziemlich verblüfft,
als er nach etwa zwanzig Minuten mit den Fingern Tobys Würfel
zeichnete und mir die Lösung präsentierte.

Nach seiner Erklärung finde ich das tatsächlich ziemlich eingängig.

Nehmen wir einen Würfel mit 3 x 3 x 3 Punkten.
Jeder Punkt dieses Würfels stellt eine Zahlenkombination unseres Schlosses dar.

Das schöne an dem Würfel ist nun, dass er uns bei einer eingestellten Kombination
(also einem gewählten Punkt aus den 27) über Nachbarn dieses Punktes auch gleich
die anderen sechs Kombinationen zeigt, die ebenfalls mit diesem Versuch "geöffnet"
werden. Das sind alle Punkte, die auf den geraden Linien oder Kanten liegen.

Jede ausprobierte Kombination ist also in der Lage, sieben potentielle Ergebnisse
zu erzielen.

Nun könnte man meinen, mit vier Versuchen zu je sieben ergäbe das ja 28
und es könnte eine Lösung mit vier Versuchen existieren.

Aber (!): man kann ja versuchen, vier Punkte in einem 3x3-Würfel zu finden,
deren Kanten sich nicht berühren. Das geht nicht! Damit ist b) bewiesen.

Eine Lösung mit fünf Versuchen zu finden, ist dann eigentlich trivial.
Man nimmt z.B. die beiden Eckpunkte und sucht dann dazwischen die Punkte,
die die restlichen Punkte durch Kanten abdecken.

Ich finde es faszinierend, wie eine geometrische Darstellung
eines an sich kombinatorischen Problems die Lösung so vereinfachen kann!

Und ja: mein kombinatorischer Lösungsversuch "endete" bei sechs. ;-)

ah, das entspricht meinem zweiten beweis 🙂 danke schon mal dafür an deinen sohn 👏

hast du ihm mal meinen ersten beweis zu lesen gegeben? vll versteht er ihn ja. wenn man das aufgezeichnet vor sich sieht, ist es gut verständlich.

also ich habe jetzt doch zwei rückmeldungen bekommen, dass die beweise verstanden wurden. damit geht es mir besser. diese aufgabe schließe ich damit ab. nochmal danke an alle, die mitgemacht haben.