Manfred Börgens
Mathematische Probleme  # 99
Liste aller Probleme mit Lösungen
voriges Problem
zur Leitseite


Pfadfinder dürfen eigentlich nicht lügen.


... 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.

Acht Pfadfinder
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.


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.

Acht Pfadfinder
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

Binomialformel

Für diese Formel soll nun  an = an-2 + an-3  nachgewiesen werden. Zu zeigen ist also:

Beweis-Ansatz

Die Formel für benachbarte Binomialkoeffizienten lautet:

Binomial-Summenformel

Also machen wir auf der rechten Seite von (1) eine Indexverschiebung:

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.

Pascal-Dreieck

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

a_32


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




Publiziert 2017-06-11          Stand 2016-05-08


voriges Problem   |   Liste aller Probleme mit Lösungen


Manfred Börgens   |    zur Leitseite