Udowodnij istnienie
-
Dario1
- Użytkownik
- Posty: 1371
- Rejestracja: 23 lut 2012, o 14:09
- Płeć: Mężczyzna
- Lokalizacja: wawa
- Podziękował: 70 razy
- Pomógł: 14 razy
Udowodnij istnienie
Rozważmy zbiór n osób z których część wita się ze sobą przez podanie rąk. Załóżmy, że żadna para osób nie wita się ze sobą ,więcej niż jeden raz oraz, że nikt nie wita się sam ze sobą. Udowodnij, że istnieją co najmniej dwie osoby które ściskały tę samą liczbę dłoni.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Udowodnij istnienie
Jeżeli któraś osoba nie wita się z nikim, to usuwamy ją z rozważań i przechodzimy do \(\displaystyle{ n-1}\) etc.
Załóżmy więc, że każda osoba się z kimś wita. Wtedy mamy \(\displaystyle{ n}\) osób i jako że nikt nie wita się z samym sobą, to liczba dłoni uściśniętych przez jedną osobę jest ze zbioru \(\displaystyle{ \left\{ 1,2,...n-1\right\}}\). Więc z zasady szufladkowej Dirichleta któraś z tych liczb się "powtórzyła".
Załóżmy więc, że każda osoba się z kimś wita. Wtedy mamy \(\displaystyle{ n}\) osób i jako że nikt nie wita się z samym sobą, to liczba dłoni uściśniętych przez jedną osobę jest ze zbioru \(\displaystyle{ \left\{ 1,2,...n-1\right\}}\). Więc z zasady szufladkowej Dirichleta któraś z tych liczb się "powtórzyła".