Pfadfinder dürfen eigentlich nicht lügen.
Die Lösung steht im unteren Teil der Seite.
... tun manche von ihnen aber doch - jedenfalls in der folgenden Geschichte. Die habe ich mir nicht ausgedacht, sondern sie stammt aus einer Zeitschrift, also nehme ich auch keine Beschwerden von gekränkten Pfadfindern an. In der Zeitschrift wurde die Geschichte als "Rätsel" angekündigt, die "Lösung" fand sich passenderweise in der gleichen Ausgabe. Der Name der Zeitschrift wird hier mildherzig verschwiegen, denn das Rätsel und die angegebene Lösung sind barer Unsinn. Aber dadurch wird die Sache erst interessant und verlangt nach einer genaueren Untersuchung.
Hier kommt das "Rätsel":
In einer großen Runde am Lagerfeuer sitzen Pfadfinder. Einige sind notorische Lügner, die anderen sagen immer die Wahrheit. Jeder sagt, seine beiden Sitznachbarn seien Lügner. Ein Junge sagt "Wie witzig, wir sind genau 99 Pfadfinder hier am Feuer". Darauf antwortet einer seiner Nachbarn: "Du lügst, wir sind genau 100 ." Wieviele Pfadfinder saßen am Feuer?
Aua.
Hier kommt die "Lösung":
Neben jedem Lügner müssen zwei sitzen, die die Wahrheit sagen, sonst könnte nicht jeder seine Nachbarn Lügner nennen. Deshalb muss die Zahl gerade sein. 100 ist also richtig.
Nochmal aua.
Erstens
Was ist falsch an der Lösung? Was bedeutet das für die Lösbarkeit des Rätsels?
Zweitens
Sei n die Anzahl der Pfadfinder. Da jeder zwei Nachbarn haben soll, ist n ≥ 3 . Machen Sie eine kleine Tabelle, in der für n = 3,...,10 die Anzahl der möglichen Sitzordnungen der Pfadfinder eingetragen wird. In Bild 1 sieht man alle vier möglichen Sitzordnungen für n = 8 . Weiße Kreise stehen für wahrheitsliebende Pfadfinder, schwarze für Lügner. Für die Zählung wird folgendes vereinbart: Man fixiert einen der Wahrheitsliebenden (grüner Pfeil in Bild 1) und zählt dann alle unterschiedlichen Anordnungen aus seiner Sicht.
Bild 1
Drittens
Für die Identifikation von Folgen ganzer Zahlen gibt es die ausgezeichnete Datenbank OEIS. Geben Sie die Anzahlen für die möglichen Sitzordnungen für n = 3,...,10 dort ein. OEIS gibt Ihnen den Namen der Folge, weitere Folgenglieder und eine Rekursionsformel an. Beachten Sie, dass es verschiedene Möglichkeiten gibt, bei welchem Glied man die Folge beginnen lässt. Bei unserer Aufgabenstellung wird die Folge (an)n≥3 gebildet, also z.B. a8 = 4 (Bild 1). Überzeugen Sie sich, dass die Rekursionsformel für die von Ihnen gefundenen Folgenglieder stimmt.
Viertens
Die Rekursionsformel für die Folge aus OEIS muss man nicht einfach glauben. Es sollte überprüft werden, ob sie für beliebige n auf unser Pfadfinder-Problem anwendbar ist. Dazu ist es hilfreich, die Sitzordnung zu codieren. Ausgehend von der fixen Position (grüner Pfeil in Bild 1) notiert man die Sitzordnung im Uhrzeigersinn. Man erkennt, dass es nur Zweiergruppen (weiß-schwarz) und Dreiergruppen (weiß-schwarz-schwarz) gibt. Für das Beispiel n = 8 (Bild 1) ist die Abfolge bei den vier Möglichkeiten:
2 2 2 2
3 3 2
3 2 3
2 3 3
Die Summe dieser Zahlen muss zeilenweise natürlich wieder n = 8 ergeben. Das bedeutet allgemein, dass hier die natürlichen Zahlen n in geordnete Summanden 2 und 3 zerlegt werden. Aus dieser Überlegung ergibt sich dann der Beweisansatz für die Richtigkeit der Rekursionsformel.
Fünftens
Nun soll noch eine geschlossene Formel für die an gefunden werden. OEIS hat uns ja den Namen der Folge genannt. Wenn man diesen in der deutschen Wikipedia recherchiert, findet man eine Summenformel mit Binomialkoeffizienten. Auch hier (wie schon in OEIS) muss man auf die Nummerierung der Folge aufpassen, da aus der Rekursionsregel nicht hervorgeht, an welcher Stelle die Folge beginnen soll.
Zeigen Sie, dass diese Formel für die an der Rekursionsformel genügt.
Tipp: Das geht über die Summenformel für benachbarte Binomialkoeffizienten im Pascal'schen Dreieck; aber vorher muss man eine Indexverschiebung durchführen.
Sechstens
Suchen Sie die Binomialkoeffizienten aus der Summenformel im Pascal'schen Dreieck auf. Sie bilden ein interessantes Muster.
Siebtens
Ganz am Anfang stand ein Rätsel aus einer Zeitschrift. Was lässt sich nun dazu sagen?
Lösung
Erstens
Was ist falsch an der Lösung? Was bedeutet das für die Lösbarkeit des Rätsels?
"Jeder sagt, seine beiden Sitznachbarn seien Lügner." Folglich hat jeder wahrheitsliebende Pfadfinder zwei Lügner als Nachbarn. Umgekehrt gilt das jedoch nicht. Wenn ein Lügner dies sagt, muss er lediglich mindestens einen wahrheitsliebenden Nachbarn haben. Einer seiner Nachbarn kann sehr wohl ein Lügner sein.
Für n ≥ 3 erhalten wir also Sitzordnungen, die zwingend sowohl wahrheitsliebende als auch lügnerische Pfadfinder enthalten müssen und in denen die Wahrheitsliebenden einzeln sitzen und die Lügner einzeln oder zu zu zweit sitzen. Das bedeutet insbesondere, dass sowohl gerade als auch ungerade Anzahlen von Pfadfindern vorkommen können. Durch Ausprobieren für kleine n sieht man, dass für n ≥ 5 die Sitzordnung nicht eindeutig ist. Für das in der Zeitschrift gestellte Rätsel heißt das, dass es sowohl für n = 99 als auch für n = 100 zahlreiche Möglichkeiten gibt, die Pfadfinder um das Lagerfeuer zu setzen.
Aber Vorsicht: Wissen wir, dass 99 und 100 die einzig möglichen Anzahlen der Pfadfinder sind? Wir schauen uns die Aussagen nochmal an:
A: "Wir sind genau 99 Pfadfinder."
B: "A lügt, wir sind genau 100 ."
A und B sitzen nebeneinander. Also gibt es drei Möglichkeiten:
(1) A sagt Wahrheit, B lügt.
(2) A lügt, B sagt Wahrheit.
(3) A lügt, B lügt.
Nun ist nicht völlig klar, was "B lügt" genau bedeutet. Dafür gibt es zwei Möglichkeiten:
(a) B macht nur eine einzige Aussage: "A lügt UND wir sind 100 ." Falls B lügt, ist (mind.) EINE der beiden Teilaussagen falsch, also gilt "A sagt Wahrheit ODER wir sind nicht 100 ".
(b) B macht zwei getrennte Aussagen: "A lügt." und "Wir sind 100." Falls B lügt, sind beide Aussagen falsch, d.h. es gilt "A sagt Wahrheit" UND "Wir sind nicht 100 ".
(1a) und (1b) passen: Es sind genau 99 Pfadfinder.
(2) passt: Es sind genau 100 Pfadfinder.
(3a) passt: Es sind weder 99 noch 100 Pfadfinder.
(3b) passt nicht.
Wir wissen nicht, ob (1), (2) oder (3) gilt, und ob (a) oder (b) gemeint ist. Somit ist der Problemstellung nicht zu entnehmen, ob 99, 100 oder eine ganz andere Anzahl von Pfadfindern in der Runde sitzen. Es könnten z.B. 5 Pfadfinder sein, davon 3 Lügner, unter denen A und B nebeneinander sitzen. Da beide lügen, kommt (b) nicht in Frage. Also können es nicht 99 oder 100 Pfadfinder sein; mehr weiß man nicht; dies ist mit der Anzahl 5 kompatibel.
Die Aufgabenstellung ist somit wertlos, da sie keine Lösung erlaubt. Schaut man in die falsche angegebene "Lösung", so wird klar, dass der Autor des Problems fälschlicherweise davon ausgegangen ist, dass genau eine Anordnung der Pfadfinder möglich ist, nämlich Wahrheitsliebende und Lügner immer abwechselnd. In Wirklichkeit kommen aber schon ab 5 Pfadfindern mehrere Sitzanordnungen in Frage. Dass das "Pfadfinder-Problem" hier in die Rubrik "Mathematische Probleme" aufgenommen wurde, hat nicht den Grund, Fehler bei einem anderen Autor zu entlarven, sondern weil das Problem eine interessante Fragestellung nach sich zieht: Wieviele Sitzanordnungen gibt es? (Jedenfalls nicht nur eine, wie behauptet wird.)
Zweitens
Sei n die Anzahl der Pfadfinder. Da jeder zwei Nachbarn haben soll, ist n ≥ 3 . Machen Sie eine kleine Tabelle, in der für n = 3,...,10 die Anzahl der möglichen Sitzordnungen der Pfadfinder eingetragen wird. In Bild 1 sieht man alle vier möglichen Sitzordnungen für n = 8 . Weiße Kreise stehen für wahrheitsliebende Pfadfinder, schwarze für Lügner. Für die Zählung wird folgendes vereinbart: Man fixiert einen der Wahrheitsliebenden (grüner Pfeil in Bild 1) und zählt dann alle unterschiedlichen Anordnungen aus seiner Sicht.
Bild 1
Durch systematisches Ausprobieren erhält man die folgende Tabelle:
a3 = 1
a4 = 1
a5 = 2
a6 = 2
a7 = 3
a8 = 4
a9 = 5
a10 = 7
Drittens
Für die Identifikation von Folgen ganzer Zahlen gibt es die ausgezeichnete Datenbank OEIS. Geben Sie die Anzahlen für die möglichen Sitzordnungen für n = 3,...,10 dort ein. OEIS gibt Ihnen den Namen der Folge, weitere Folgenglieder und eine Rekursionsformel an. Beachten Sie, dass es verschiedene Möglichkeiten gibt, bei welchem Glied man die Folge beginnen lässt. Bei unserer Aufgabenstellung wird die Folge (an)n≥3 gebildet, also z.B. a8 = 4 (Bild 1). Überzeugen Sie sich, dass die Rekursionsformel für die von Ihnen gefundenen Folgenglieder stimmt.
Gibt man bei OEIS die Zahlenfolge 1, 1, 2, 2, 3, 4, 5, 7 ein, wird man sofort fündig: Es handelt sich um die Padovan-Folge, benannt nach dem britischen Architekten Richard Padovan. Sie wird unter der Nummer A000931 geführt. Die Rekursionsformel lautet:
an = an-2 + an-3
Das ist eine Differenzengleichung vom Fibonacci-Typ. Wir wollen uns einen Überblick verschaffen, wie die verschiedenen Definitionen der Folge zusammenpassen. Zunächst zu den Abkürzungen:
Pfadfinder an
OEIS A000931 a(n)
MathWorld und englische Wikipedia P(n)
deutsche Wikipedia Pn
Für n ≥ 3 gelten dann folgende Umrechnungen:
a(n+3) = an P(n-2) = Pn-2 = an
Viertens
Die Rekursionsformel für die Folge aus OEIS muss man nicht einfach glauben. Es sollte überprüft werden, ob sie für beliebige n auf unser Pfadfinder-Problem anwendbar ist. Dazu ist es hilfreich, die Sitzordnung zu codieren. Ausgehend von der fixen Position (grüner Pfeil in Bild 1) notiert man die Sitzordnung im Uhrzeigersinn. Man erkennt, dass es nur Zweiergruppen (weiß-schwarz) und Dreiergruppen (weiß-schwarz-schwarz) gibt. Für das Beispiel n = 8 (Bild 1) ist die Abfolge bei den vier Möglichkeiten:
2 2 2 2
3 3 2
3 2 3
2 3 3
Die Summe dieser Zahlen muss zeilenweise natürlich wieder n = 8 ergeben. Das bedeutet allgemein, dass hier die natürlichen Zahlen n in geordnete Summanden 2 und 3 zerlegt werden. Aus dieser Überlegung ergibt sich dann der Beweisansatz für die Richtigkeit der Rekursionsformel.
Beweis:
Stellt man n als geordnete Summe dar, deren Summanden alle 2 oder 3 sind, so gibt es für den letzten Summanden nur zwei Möglichkeiten:
1. Fall: Der letzte Summand ist 2 . Für alle Summanden vor dieser letzten 2 gibt es an-2 Möglichkeiten.
2. Fall: Der letzte Summand ist 3 . Für alle Summanden vor dieser letzten 3 gibt es an-3 Möglichkeiten.
Insgesamt gibt es also an-2 + an-3 Möglichkeiten.
Fünftens
Nun soll noch eine geschlossene Formel für die an gefunden werden. OEIS hat uns ja den Namen der Folge genannt. Wenn man diesen in der deutschen Wikipedia recherchiert, findet man eine Summenformel mit Binomialkoeffizienten. Auch hier (wie schon in OEIS) muss man auf die Nummerierung der Folge aufpassen, da aus der Rekursionsfolge nicht hervorgeht, an welcher Stelle die Folge beginnen soll. Zeigen Sie, dass diese Formel für die an der Rekursionsformel genügt.
Tipp: Das geht über die Summenformel für benachbarte Binomialkoeffizienten im Pascal'schen Dreieck; aber vorher muss man eine Indexverschiebung durchführen.
Wegen an = Pn-2 ist
Für diese Formel soll nun an = an-2 + an-3 nachgewiesen werden. Zu zeigen ist also:
Die Formel für benachbarte Binomialkoeffizienten lautet:
Also machen wir auf der rechten Seite von (1) eine Indexverschiebung:
(1) ist zu zeigen; (1) und (3) sind äquivalent. In (3) stimmen die Summanden für jedes j wegen (2) überein. Also muss nur noch geklärt werden, ob die Summen trotz der unterschiedlichen Summationsgrenzen übereinstimmen. In der Summe A fehlt für manche n das erste j aus der linken Summe in (3); in der Summe B fehlt für manche n das letzte j aus der linken Summe in (3). Es wird nun gezeigt, dass diese fehlenden j keine Rolle spielen.
Zuerst beweisen wir, dass man in der Untergrenze von A auch ⌈n/3⌉ statt ⌈(n+1)/3⌉ nehmen kann, ohne (3) zu beeinträchtigen. Nur für 3|n ist ⌈(n+1)/3⌉ > ⌈n/3⌉ . Ergänzt man in diesem Fall j = ⌈n/3⌉ = n/3 für den ersten Summanden in A , so ist dieser gleich 0 . Wir überprüfen noch die Gesamtsumme: Für j = n/3 ist der Summand auf der linken Seite in (3) gleich 1 , ebenso in B .
Nun beweisen wir, dass man in der Obergrenze von B auch ⌊n/2⌋ statt ⌊(n-1)/2⌋ nehmen kann, ohne (3) zu beeinträchtigen. Nur für gerade n ist ⌊(n-1)/2⌋ < ⌊n/2⌋ . Ergänzt man in diesem Fall j = ⌊n/2⌋ = n/2 für den letzten Summanden in B , so ist dieser gleich 0 . Wir überprüfen noch die Gesamtsumme: Für j = n/2 ist der Summand auf der linken Seite in (3) gleich 1 , ebenso in A .
Sechstens
Suchen Sie die Binomialkoeffizienten aus der Summenformel im Pascal'schen Dreieck auf. Sie bilden ein interessantes Muster.
Bild 2 Von oben nach unten: a6, a8, a12, a13, a21, a27, a30, a32
In Bild 2 stehen die Linien jeweils für die Summen von Binomialkoeffizienten im Pascal'schen Dreieck. Dargestellt sind beispielhaft a6, a8, a12, a13, a21, a27, a30 und a32 . Der einzelne Punkt zwischen a6 und a8 (also zwischen den beiden obersten Linien) steht für a7 , das nur einen Summanden hat. - Die Linien sind nicht die "normalen" Diagonalen im Pascal'schen Dreieck, sondern sie liegen flacher. Von einem Punkt zum nächsten gelangt man durch eine Art Rösselsprung. Die unterste Linie (von rechts oben nach links unten gelesen) steht für
Siebtens
Ganz am Anfang stand ein Rätsel aus einer Zeitschrift. Was lässt sich nun dazu sagen?
Es gibt sehr viele Möglichkeiten, die 99 oder 100 Pfadfinder um das Lagerfeuer zu setzen, wenn unterschiedliche Muster für die Positionen der Wahrheitsliebenden und Lügner gezählt werden:
a99 = 506.505.428.836
a100 = 670.976.837.021
Zur Erinnerung: In "Erstens" haben wir gesehen, dass noch nicht einmal klar ist, ob 99 und 100 die einzig möglichen Anzahlen sind. Deshalb ist es sinnvoll, an für alle n zu kennen.
Publiziert 2017-06-11 Stand 2024-03-14
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem
Manfred Börgens |
zur Leitseite