Udowodnij że dowolna grupa może być podzielona na dwie części tak, że co najmniej
połowa znajomych danej osoby jest w grupie, do której ta osoba nie należy.
Nie wiem jak się do tego zabrać, proszę o jakieś podpowiedzi.-- 29 paź 2015, o 20:23 --W końcu sam doszedłem do rozwiązania.
Na początku dzielimy znajomych na dwie losowe grupy.
Następnie bierzemy każą osobę której co najmniej połowa znajomych
nie jest w grupie do której ona nie należy. Przerzucamy tą osobę osobę do
drugiej grupy. Następnie jeżeli nie ma takiej osoby, to wtedy zadanie jest rozwiązane.
Natomiast jeżeli jest taka osoba to powtarzamy poprzedni schemat działania.
Z każdym przerzuceniem zwiększa się liczba przecięć(jeżeli narysujemy graf i dwie grupy oddzielimy linią).
Liczba krawędzi jest skończona więc liczba przerzuceń też jest skończona,
więc zawsze dojdziemy do sytuacji że nie możemy już nikogo przerzucić. cnd
