Dowód - grafy

[matinf]

Witam,
Chcę udowodnić, że na każdej imprezie są dwie osoby, które znają taką samą ilość osób.

Przy czym relacja znajomości jest symetryczna.

I pewnie zostanę skrytykowany za to rozumowanie:

Przypuśćmy przeciwnie, tj, że każdy zna inną ilość osób, tj istnieje osoba, która zna najmniej (najwięcej osób).
I to jest minimum(maksimum) absolutne (tylko jedna osoba taka jest).

No więc przypuśćmy, że przychodzą osoby na imprezę. Przychodzą co minutę. Pierwszy przychodzi ten, który ma najmniej znajomych na imprezie. Potem kolejne, a na końcu przyjdzie ten, który zna najwięcej osób.

No więc przychodzi pierwsza osoba, zna ileś tam Czyli intuicyjnie:
gdy przychodzi druga osoba nie ma szans na to, żeby w momencie jej przyjścia byli wszyscy jej znajomi.
No więc jej znajomi podochodzą, ALE! Ci znajomi też mają żądania co do liczb znajomych. I w końcu nadejdzie moment, że przyjdzie przedostatnia osoba. Jak się okaże, nie będzie tylu osób ile ona zna - spokojnie jeszcze przyjdzie jedna osoba. Ale dlaczego na tą chwilę nie ma wszystkich która ona zna ? Bo musi to być więcej niż znała poprzednia osoba która przyszła, i to się tak rozciąga, aż do 2giej osoby - ale ona też w chwili przyjścia nie mogła mieć wszystkich swoich znajomych. WRESZCIE przychodzi ostatnia osoba i wszystko bierze w łeb, ona nie będzie miała na imprezie tyli znajomych ilu zna - a to sprzeczność. No nie będzie miała, bo żąda więcej niż przedostatnia. A ona przyjdzie jako ostatnia, czyli już nikt więcej nie przyjdzie - musiałoby by być tak, że przyjdzie ktoś, kto zna się z ostatnią osobą powiedzmy, ale ma tyle samo żądań co poprzedni - ale to niezgodne z założeniem nie-wprost.

To takie uzasadnienie, ale chyba dobre. To o co proszę to o pomoc w sformalizowaniu tego - indukcja, coś bardziej eleganckiego, ale jak również o ocenę logiki tego wywodu.

[miodzio1988]

No i gdzie tutaj masz jakiś graf zdefiniowany?

[Kartezjusz]

Poza tym. To zaprzeczenie, które podałeś nie jest tym dokładnie, bo pośrednie osoby mogą mieć tę samą liczbę znajomych, ale to co podałeś to szególny wniosek Z tego zaprzeczenia.

Następnie zobacz, że liczby znajomych musiałyby być bardzo szczególne ( ile znajomych może mieć najpopularniejsza osoba, a ile najmniej ) i poszereguj.

[matinf]

w takim razie jak Ty zaprzeczysz zdaniu:
Są dwie osoby, które mają tyle samo znajomych.
?

[Kartezjusz]

Każde dwie mają inną liczbę znajomych.
Czy zakładamy, że każda osoba zna co najmniej jedną

[matinf]

Ja tego nie zakładam. Ja właśnie tak zaprzeczyłem jak i Ty, więc nie rozumiem,
Tzn, że możemy posortować po ilości znajomych - jednoznacznie.

[Kartezjusz]

Dokładnie. Tylko weź gościa,ktory nie ma znajomych, potem goscia, który ma jednego znajomego etc.
Gdyby dołożyć znajomosć conajmniej jednej osoby to twoje rozumowanie jest poprawne...

[matinf]

No to jest trochę takie dziwne. Bo jeśli chcesz takie coś dopuścić oznacza, że dopuszczasz graf, który nie istnieje.

Bo mówisz: Najpierw ( z tego samego grafu!) pójdzie gość o stopniu 0, a potem z tego samego (powiedzmy dwuwierzchołkowego) o stopniu 1 - t o niemożliwe.

Więc dostarcza fixa do mojego dowodu:
Przypadek gdy tylko jedna osoba nie zna nikogo - zapominamy o niej (nie ma jej) i dowód działa.
Gdy dwie lub więcej osób nie znają nikogo to teza jest OK

Teraz ?

[Kartezjusz]

Tak, o ten fix chodziło,ale to co mi przedstawiłeś musisz też dołączyć.

[matinf]

Okey, to dobrze.

A jakąś bardziej wyrafinowaną metodą da sie ?

[Kartezjusz]

To jest wyrafinowana. Tylko jak Miodzio1988 sugeruje ,zapisać w języku teorii grafów.