Witam,
Mam takie zadanie:
Udowodnij, że w grupie 10 osób zawsze będą trzy, które znają się nawzajem lub cztery, które się nie znają nawzajem.
W jaki sposób można to udowodnić?
Z góry dziękuję
zasada podziałowa?
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
zasada podziałowa?
zróbmy z tego graf nieskierowany
krawędź między wierzchołkami oznacza że osoby reprezentowane przez te wierzchołki znają się.
załóżmy że nie ma trójki znających się osób, więc że w grafie nie ma 3-elementwej kliki. na mocy twierdzenia Turana w grafie mamy maksymalnie 25 krawedzi. rozważmy teraz dopełnienie grafu. W dopełnieniu mamy co najmniej 75 wierzchołków ale znowy z tw. Turana aby nie było 4-elementowej kliki musi być nie więcej niż 33 krawędzi, co nie jest prawdą. koniec.
jak widać tezę można bardzo wzmocnić
krawędź między wierzchołkami oznacza że osoby reprezentowane przez te wierzchołki znają się.
załóżmy że nie ma trójki znających się osób, więc że w grafie nie ma 3-elementwej kliki. na mocy twierdzenia Turana w grafie mamy maksymalnie 25 krawedzi. rozważmy teraz dopełnienie grafu. W dopełnieniu mamy co najmniej 75 wierzchołków ale znowy z tw. Turana aby nie było 4-elementowej kliki musi być nie więcej niż 33 krawędzi, co nie jest prawdą. koniec.
jak widać tezę można bardzo wzmocnić
-
- Użytkownik
- Posty: 64
- Rejestracja: 3 paź 2009, o 12:15
- Płeć: Mężczyzna
- Podziękował: 16 razy
- Pomógł: 2 razy
zasada podziałowa?
O cholera, jeszcze nie mieliśmy takich rzeczy
W każdym razie, z tego co napisałeś:
Zakładam, że nie ma 3 znających się wzajemnie:
Aby tak było, muszą być nie więcej niż 25 krawędzie.
Dopełnienie grafu: 75 krawędzi
Zakładam, że nie ma 4 znających się wzajemnie:
Aby tak było, muszą być nie więcej niż 33 krawędzie.
Mam udowodnić, że zawsze będą trzy, które się znają, lub 4, które się nie znają. Jak to połączyć w logiczną całość?
Dzięki i pozdrawiam
W każdym razie, z tego co napisałeś:
Zakładam, że nie ma 3 znających się wzajemnie:
Aby tak było, muszą być nie więcej niż 25 krawędzie.
Dopełnienie grafu: 75 krawędzi
Zakładam, że nie ma 4 znających się wzajemnie:
Aby tak było, muszą być nie więcej niż 33 krawędzie.
Mam udowodnić, że zawsze będą trzy, które się znają, lub 4, które się nie znają. Jak to połączyć w logiczną całość?
Dzięki i pozdrawiam
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
zasada podziałowa?
w dopelnieniu krawedz oznacza ze sie nie znaja-- 21 października 2009, 19:43 --o qrde to rozwiazanie jest zupełnie złe bo nie wiem skąd wziąłem 100 krawędzi
zaraz pomyśle nad dobrym rozwiazaniem
zaraz pomyśle nad dobrym rozwiazaniem
-
- Użytkownik
- Posty: 64
- Rejestracja: 3 paź 2009, o 12:15
- Płeć: Mężczyzna
- Podziękował: 16 razy
- Pomógł: 2 razy
zasada podziałowa?
Na wykładach właśnie radziliśmy sobie bez grafu przy podobnym przykładzie (grafów jeszcze nie poruszaliśmy) - ale jak to zrobić, to nie mam pojęcia w dalszym ciągu