Udowodnić, że w dowolnej grupie osób istnieją osoby o tej samej liczbie znajomych (w tej
grupie).
Jak to można udowodnić?
Udowodnić że 2 osoby mają tyle samo znajomych
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Udowodnić że 2 osoby mają tyle samo znajomych
Korzystając z zasady szufladkowej.
Pudełka etykietowane są ilością uścisków dłoni od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\). Ale nie może być jednocześnie \(\displaystyle{ 0}\) uścisków jednej osoby i \(\displaystyle{ n-1}\) uścisków innej osoby, więc zostaje \(\displaystyle{ n-1}\) pudełek dla \(\displaystyle{ n}\) osób.
Pudełka etykietowane są ilością uścisków dłoni od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\). Ale nie może być jednocześnie \(\displaystyle{ 0}\) uścisków jednej osoby i \(\displaystyle{ n-1}\) uścisków innej osoby, więc zostaje \(\displaystyle{ n-1}\) pudełek dla \(\displaystyle{ n}\) osób.
-
- Użytkownik
- Posty: 102
- Rejestracja: 4 gru 2012, o 11:36
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 77 razy
Udowodnić że 2 osoby mają tyle samo znajomych
mógłby ktoś jaśniej i na innym przykładzie bo za bardzo nie rozumiem...
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Udowodnić że 2 osoby mają tyle samo znajomych
Zacytuję z pewnej strony...
Pewna grupa osób wita się podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się podwójnie. Czy muszą być dwie osoby, które witały taką samą liczbę osób?
Gdy jest \(\displaystyle{ n}\) osób, to każda z nich przywita\(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) lub 2 lub ... \(\displaystyle{ n-1}\) osób.
Utwórzmy więc \(\displaystyle{ n}\) szuflad z etykietami \(\displaystyle{ k=0,1,2,\ldots, n-1}\)i umieśćmy osobę w szufladzie o etykiecie \(\displaystyle{ k}\), jeśli witała się z dokładnie \(\displaystyle{ k}\) osobami.
Skoro jest \(\displaystyle{ n}\) osób i \(\displaystyle{ n}\) szuflad, to ...
niewiele z tego wynika
Ale... niewiele wynika tylko jeśli wszystkie szuflady będą zajęte, a tak jest w przypadku, gdy również dwa konkretne pudełka o etykietach \(\displaystyle{ 0}\) i \(\displaystyle{ n-1}\) są zajęte. Tyle, że nie jest to możliwe - nie może być osoby, która przywitała wszystkie pozostałe i równocześnie takiej, która nie przywitała nikogo.
A zatem \(\displaystyle{ n}\) osób zajęło co najwyżej \(\displaystyle{ n-1}\) szuflad, więc w jednej z nich są co najmniej dwie osoby - takie, które przywitały tę samą liczbę osób.