szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 paź 2015, o 23:11 
Użytkownik

Posty: 102
Lokalizacja: Polska
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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2016, o 17:48 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Tutaj jest rozwiązanie wzorcowe: http://archom.ptm.org.pl/?q=node/664.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Teoria grafów-podstawy.  Natt  1
 Podział osób na grupy - zadanie 4  klejstofeles  2
 Liczba osób uprawiających dwie dyscypliny  Zaker  1
 Produkt grafów  gnegneri  1
 Ze zbioru (1, 2 3.........,102) losujemy dwie liczby....  arturrud  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl