Sándor Horváth (Eötvös-Loránd-Universität Budapest): Ein einfacher simultaner Beweis für das Fine-Wilf-Theorem und seine Schärfe

Das Theorem von Fine und Wilf ist ein oft benutztes Resultat in der Kombinatorik von Wörtern. Es besagt: Wenn |X| ≥ 2, s,t ∈ X+, und wenn sω und tω ein gemeinsames Anfangsstück der Länge l = |s| + |t| - ggt(|s|,|t|) haben, dann gibt es ein z ∈ Xggt(|s|,|t|) mit s,t ∈ z+. Wir geben einen einfachen neuen Beweis für dieses Theorem und zugleich auch für seine Schärfe, und mit demselben Argument geben wir die genaue Anzahl von Gegenbeispielen, wenn wir l-1 anstatt l nehmen.