Manfred Boergens

MB Matheblog # 47

zur Leitseite
Index der gesamten Website

2026-03-16 Kommentare sind willkommen.

Pfadfinder sitzen im Kreis

Dieser Beitrag greift noch einmal das Pfadfinder-Problem # 99 auf. Es sitzen \(_~n_~\) Pfadfinder im Kreis, mit \(_~n\ge 3_~\). Einige von ihnen lügen immer, die anderen sagen immer die Wahrheit. Jeder von ihnen sagt, seine beiden Sitznachbarn seien Lügner. Folglich hat jeder wahrheitsliebende Pfadfinder zwei Lügner als Nachbarn. Wenn ein Lügner dies sagt, muss er mindestens einen wahrheitsliebenden Nachbarn haben. Einer seiner Nachbarn könnte ein Lügner sein.

Hier soll es nun detaillierter als in Problem # 99 um die Anzahl der Anordnungen der Pfadfinder gehen. Im Problem sind wir davon ausgegangen, dass diese Anordnungen aus der Sicht eines bestimmten Wahrheitssagers gezählt werden. Das bedeutet, dass man aus dem Kreis der Pfadfinder eine Reihe mit Anfang und Ende machen kann, z.B. indem man von dem ausgesuchten Wahrheitssager im Uhrzeigersinn vorgeht:

n=8
Bild 1
\(n=8~\). Weiß: Wahrheitssager; Schwarz: Lügner. Das Bild zeigt links eine mögliche "zyklische" Anordnung der Pfadfinder. Legt man, beginnend beim grünen Pfeil im Uhrzeigersinn, die Kreise nebeneinander, erhält man eine "lineare" Anordnung, die sich durch eine Abfolge von Dreien und Zweien codieren lässt (rechts).

In Bild 1 wurde eine naheliegende Codierung für die Anordnung eingetragen. Hinter einem Wahrheitssager folgt immer genau ein Lügner oder es folgen genau zwei Lügner. So erhält man eine geordnete Abfolge von Zweien und Dreien mit der Summe \(_~n_~\); hier \(_~3+3+2=8_~\).

Dieser "lineare" Ansatz wurde in Problem # 99 gewählt. Dort haben wir gesehen, dass es für \(_~n=8_~\) genau \(_~4_~\) verschiedene Anordnungen gibt. Für jedes \(_~n_~\) konnte die Anzahl der Anordnungen \(_~a_{n_~}\) angegeben werden. Wir werden später darauf zurückkommen.

Interessanter und schwieriger ist der Fall, bei dem man keinen fixen Pfadfinder als Bezugspunkt nimmt, sondern nur den Gesamtblick auf den Kreis der Pfadfinder hat. Dann soll es keine Rolle spielen, aus welcher Perspektive man auf den Kreis schaut: Zwei Anordnungen gelten als identisch, wenn sie durch Rotation ineinander überführt werden können. In Bild 1 würde das bedeuten, dass es nur eine einzige Anordung gibt, denn die möglichen Codierungen \(_~3+3+2_~\) und \(_~3+2+3_~\) und \(_~2+3+3_~\) sind unter Rotation identisch.

Für kleine \(_~n_~\) lassen sich alle möglichen dieser "zyklischen" Anordnungen aufzeichnen. Bild 2 zeigt, dass es für \(_~n=14_~\) genau \(_~5_~\) Anordnungen gibt. Die Anzahl der zyklischen Anordnungen soll mit \(_~c_{n_~}\) bezeichnet werden; also ist \(_~c_{14}=5_~\).

n=14

Bild 2 \(n=14,~~c_{14}=5\)
von links nach rechts: \(~2+2+2+2+2+2+2~~~~~~~~3+3+2+2+2+2~~~~~~~~3+2+3+2+2+2~~~~~~~~3+2+2+3+2+2~~~~~~~~3+3+3+3+2\)

Es folgt eine Tabelle für kleine \(_~n_~\) (mit \(_~a_{n_~}\) aus Problem # 99); die Nummern in der Überschrift beziehen sich auf die online-Datenbank OEIS.

n	zyklisch c_n A127687	linear a_n A182097
3	1	1
4	1	1
5	1	2
6	2	2
6	1	3
8	2	4
9	2	5
10	3	7
11	2	9
12	4	12
13	3	16
14	5	21
15	6	28
16	7	37
17	7	49
18	11	65
19	11	86
20	16	114

Zu \(_~c_{14}=5_~\) siehe Bild 2, zu \(_~a_8=4_~\) siehe Bild 1 in Problem # 99

Die Gesetzmäßigkeit von \(~a_n~\) wurde bereits in Problem # 99 beschrieben (verschobene Padovan-Folge). Dort hat eine Recherche in der Datenbank OEIS zum Erfolg geführt. Die Tabelle, empirisch erstellt für kleine \(_~n_~\), gibt uns die Möglichkeit, auch für \(_~c_{n_~}\) OEIS zu nutzen – mit Erfolg: Wir finden die Folge A127687 mit dem Kommentar "Number of cyclic compositions of \(_~n_~\) in which each term is either \(_~2_~\) or \(_~3\)". Die dort angegebenen Formeln und Programme lassen darauf schließen, dass es keine einfache geschlossene Formel für \(_~c_{n_~}\) gibt. Am einfachsten erscheint noch die folgende Darstellung: \[c_n~=~\frac{1}{n} \cdot \sum_{d|n} \phi (n/d)\cdot d \cdot \sum_{k~=~1}^{\lfloor d/2 \rfloor} \frac{1}{k} \cdot \binom{k}{d-2k}\] mit \(_~\phi(m)_~\) Eulersche phi-Funktion (Anzahl der zu \(_~m\in \textbf{N}_~\) teilerfremden natürlichen Zahlen \(_~t_~\) mit \(_~1≤t<m_~\); die äußere Summe durchläuft alle Teiler \(_~d_~\) von \(_~n_~\).

Wir kennen jetzt die Anzahl der zyklischen und linearen Anordnungen der Pfadfinder. Wir wollen noch der Frage nachgehen, welches die minimale und die maximale Anzahl von Lügnern ist und wie sich das in die Anzahl der Dreien und Zweien in der Codierung übersetzen lässt. Unterhalb der folgenden Erläuterungen gibt es eine tabellarische Zusammenfassung.

Zyklisch

Minimale Anzahl Lügner
Es müssen soviele Zweien wie möglich vorliegen. Bei geraden \(_~n_~\) sind das \(_~n/2_~\) Zweien und ebensoviele Lügner, und es gibt keine Dreien. Bei ungeraden \(_~n_~\) gibt es genau eine Drei und somit \(_~(n-3)/2_~\) Zweien; dies ergibt \(_~2 + (n-3)/2~=~n/2 + 1/2_~\) Lügner.

Zugehörige Anzahl Anordnungen
Wegen der Rotations-Invarianz gibt es sowohl für \(_~0_~\) Dreien als auch für eine Drei genau eine Anordnung.

Maximale Anzahl Lügner
Es müssen soviele Dreien wie möglich vorliegen. Ist \(_~n_~\) durch \(_~3_~\) teilbar, sind das \(_~n/3_~\) Dreien und doppelt so viele Lügner, und es gibt keine Zweien.
Für \(_~n~\text{mod}~3~=~1_~\) muss es zwei Zweien geben und somit \(_~(n-4)/3_~\) Dreien. Das ergibt \(_~2 + 2~(n-4)/3~=~(2n-2)/3_~\) Lügner.
Für \(_~n~\text{mod}~3~=~2_~\) muss es eine Zwei geben und somit \(_~(n-2)/3_~\) Dreien. Das ergibt \(_~1 + 2~(n-2)/3~=~(2n-1)/3_~\) Lügner.

Zugehörige Anzahl Anordnungen
Wegen der Rotations-Invarianz gibt es sowohl für \(_~0_~\) Zweien als auch für eine Zwei genau eine Anordnung; dies ist der Fall bei \(_~n~\text{mod}~3~=~0_~\) und \(_~n~\text{mod}~3~=~2_~\).
Für \(_~n~\text{mod}~3~=~1_~\) liegen \(_~2_~\) Zweien und \(_~(n-4)/3_~\) Dreien vor. Wieviele Dreien können zwischen diesen beiden Zweien liegen?
n gerade: Die Zweien können durch
\(0~\) bzw. \((n-4)/3\)
\(1~\) bzw. \((n-7)/3\)
...
\((n-4)/6 = (n-(n/2+2))/3\)
Dreien getrennt werden. Das ergibt \(_~(n-4)/6 + 1~=~(n+2)/6_~\) Anordnungen.
n ungerade: Man zählt wie bei \(_~n_~\) gerade, bis man bei \(_~\lfloor (n-4)/6\rfloor_~\) bzw. \(\lceil (n-4)/6\rceil_~\) trennenden Dreien angekommen ist. Die Zweien können also durch
\(0~\) bzw. \((n-4)/3\)
\(1~\) bzw. \((n-7)/3\)
...
\((n-4)/6 - 1/2~\) bzw. \((n-(n+1)/2)~/~3~=~(n-4)/6 + 1/2\)
Dreien getrennt werden. Das ergibt \(_~(n-4)/6 - 1/2 + 1~=~(n+2)/6 - 1/2_~\) Anordnungen.

Linear
Bei der minimalen bzw. maximalen Anzahl von Lügnern gibt es keinen Unterschied zwischen zyklischen und linearen Anordnungen. Nur die Anzahlen der Anordnungen unterscheiden sich.

Anzahl Anordnungen bei minimaler Anzahl Lügner
Bei geradem \(_~n_~\) gibt es nur Zweien, also auch nur eine Anordnung.
Bei ungeradem \(_~n_~\) gibt es genau eine Drei und \(_~(n-3)/2_~\) Zweien. Die Drei kann u.a. ganz am Anfang und ganz am Ende stehen, also gibt es \(_~(n-3)/2 + 1_~=_~(n-1)/2_~\) Anordnungen.

Anzahl Anordnungen bei maximaler Anzahl Lügner
Ist \(_~n_~\) durch \(_~3_~\) teilbar, so gibt es nur Dreien, also auch nur eine Anordnung.
Bei \(_~n~\text{mod}~3~=~2_~\) gibt es genau eine Zwei und \(_~(n-2)/3_~\) Dreien. Die Zwei kann u.a. ganz am Anfang und ganz am Ende stehen, also gibt es \(_~(n-2)/3 + 1~=~(n+1)/3_~\) Anordnungen.
Bei \(_~n~\text{mod}~3~=~1_~\) gibt es genau \(_~2_~\) Zweien und \(_~(n-4)/3_~\) Dreien, das ergibt zusammen \(_~(n-4)/3 + 2~=~(n+2)/3_~\) "Gruppen". Wie die beiden Zweien positioniert werden können, ergibt sich dann über den entsprechenden Binomialkoeffizienten.

Zusammenhang mit Perlenketten (Blog # 31)

Linear:
Die Anordnungen der Pfadfinder sind eine Teilmenge der offenen und orientierten Perlenketten mit genau zwei Farben (OEIS A000918), deren Anzahlen in Blog # 31 als \(_~a_{~\text{off, ori, ex}~}(n,2)_~\) aufgeführt sind, also in der zweiten Spalte von OEIS A019538.

Zyklisch:
Die Anordnungen der Pfadfinder sind eine Teilmenge der geschlossenen und orientierten Perlenketten mit genau zwei Farben ("necklaces" in OEIS und der englischen Wikipedia; OEIS A052823), deren Anzahlen in Blog # 31 als \(_~a_{~\text{geschl, ori, ex}~}(n,2)_~\) aufgeführt sind, also in der zweiten Spalte von OEIS A087854.

Kommentare sind willkommen.

Stand 2024-06-05

Inhalt Blog | voriger Eintrag

Manfred Börgens | Zur Leitseite