On a combinatorial game (Q5905678): Difference between revisions

Es wird das folgende verallgemeinerte Mühlespiel betrachtet: Gegeben seien die Mengen \(A_k\) und es sei \(S= \bigcup ^m_{k=1}A_k\). Die beiden Spieler wählen abwechselnd je ein Element aus \(S\). Wer als erster alle Elemente einer der Mengen \(A_k\) zusammen hat, hat gewonnen. Sei \(|A_k| =n\) und sei \(m^*(n)\) die kleinste Zahl \(m\) (= Anzahl der \(A_k\)), für welche es Mengen \(A_k\) der Art gibt, daß der erste Spieler eine Gewinnstrategie besitzt. Dann gilt: \(m^*(n)=2^{n-1}\). Es werden Verallgemeinerungen betrachtet; z.B. die Spieler wählen abwechselnd die Kanten eines gegebenen Graphen; wer als erster einen vollständigen Teilgraphen mit \(k\) Kanten erhalten hat, hat gewonnen.