Beweis für Clickbait-Problem

Im Januar schrieb ich über die Unlösbarkeitsdemonstration eines Instagram Clickbait-Rätsels. Ich konnte zwar durch Backtracking zeigen, dass es keine Lösung gibt, hatte jedoch keinen hübschen Beweis, der ohne Ausprobieren aller Möglichkeiten auskommt. Ein Leser hat mir neulich einen Beweis geschickt, herzlichen Dank dafür! 🙋🏻‍♂️

Beginnen wir mit dem Teil vom Graph und entfernen einmal diese Kette, die im ursprünglichen Artikel A3 bis C5 genannt war. Dann färben wie die Knoten im Schachbrettmuster ein:

Nun haben wir 7 schwarze und 6 weiße Knoten. Damit wissen wir schon, dass die Lösung jeweils auf einem schwarzen Knoten anfangen und aufhören muss, damit es hinkommen kann. Egal von welchem Knoten wir anfangen, wir können eine Lösung konstruieren.

Jetzt hängt diese Kette aber an dem weißen Knoten oben links. Da die Kette aber nur eine Kette ist, können wir sie nur einmal durchgehen. Somit ist damit schon gezeigt, dass das Problem unmöglich zu lösen ist.

Das ganze gibt uns aber auch einen Weg, um das ganze lösbar zu machen. Wir brauchen noch einen zusätzlichen weißen Knoten, der mit zwei schwarzen Knoten verbunden ist. Den können wir da an der Ecke einfügen. Und dann wird das ganze Problem auch wieder lösbar.

Wenn man es einmal gesehen hat, dann kann man sich schnell davon überzeugen, dass das ursprüngliche Problem nicht lösbar ist.