Es müssen mindestens 6 Personen sein:
Zunächst gehen wir von dem günstigsten Fall aus, dass es nämlich keine einzige Clique in dieser Gruppe gibt, so dass folglich auch die gesamte
Gruppe eine Anticlique bildet.
Nun suchen wir das kleinste n, so dass es mindestens 50 Teilmengen dieser n Personen gibt, die mindestens zwei Elemente enthalten.
Bekanntlich hat eine n-elementige Menge 2n Teilmengen. Da hier jedoch auch die leere Menge und alle
einelementigen Teilmengen enthalten sind,
müssen wir diese noch subtrahieren. Zu berechnen ist 2n - 1 - n
Für n=5 ergibt sich: 25 - 1 - 5 < 50 .
Für n=6 ergibt sich: 26 - 1 - 6 = 57 .
Folglich beträgt das kleinste n = 6, in einer Gruppe mit 6 Personen kann es 50 Anticliquen geben. |