zasada podziałowa?

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
movax1
Użytkownik
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?

Post autor: movax1 »

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ę
Dumel
Użytkownik
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?

Post autor: Dumel »

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ć
movax1
Użytkownik
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?

Post autor: movax1 »

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
Dumel
Użytkownik
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?

Post autor: Dumel »

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
movax1
Użytkownik
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?

Post autor: movax1 »

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
ODPOWIEDZ