liczba znajomych
: 26 lis 2005, o 14:43
Mamy conajmniej 2 osoby. Wykazać, że wśród nich są 2, które mają taką samą ilość znajmomych.
rozwiązanie metodę szufladkową Dirichleta
Nie wiem dokłanie jak to zrobić.. może być tak??
Mamy n znajomych. Każda osoba nie jest swoim własnym znajomym, więc znajomy n może mieć n-1 znajomych. Z zasady szufladkowej Dirichleta wynika, że przynajmniej jedna para będzie miała taka samą ilość znajomych.
np. mamy 3 osoby - x, y, z. Osoba x może mieć 0, 1 lub 2 znajomych i osoba y może mieć 0, 1 lub 2 i osoba z może mieć 0, 1 lub 2 znajmych. Wszystkie kombinacje znajomych to: 000,111,222,011,022,012 [kolejność nieistotna]
i to chyba nie jest prawda, bo w przypadku 012 każda osoba ma inną ilość znajomych i nie ma 2 takich osób co miałby taką samą ilośc znajmych.
Prosze o wyjaśnienie jak to powinno być...
rozwiązanie metodę szufladkową Dirichleta
Nie wiem dokłanie jak to zrobić.. może być tak??
Mamy n znajomych. Każda osoba nie jest swoim własnym znajomym, więc znajomy n może mieć n-1 znajomych. Z zasady szufladkowej Dirichleta wynika, że przynajmniej jedna para będzie miała taka samą ilość znajomych.
np. mamy 3 osoby - x, y, z. Osoba x może mieć 0, 1 lub 2 znajomych i osoba y może mieć 0, 1 lub 2 i osoba z może mieć 0, 1 lub 2 znajmych. Wszystkie kombinacje znajomych to: 000,111,222,011,022,012 [kolejność nieistotna]
i to chyba nie jest prawda, bo w przypadku 012 każda osoba ma inną ilość znajomych i nie ma 2 takich osób co miałby taką samą ilośc znajmych.
Prosze o wyjaśnienie jak to powinno być...