Pewnego dnia na zlocie motocyklistów spotkało się przypadkiem czterech znajomych ze szkolnych lat. Ile było wymienionych uścisków dłoni między nimi, jeśli każdy z nich przywitał się z resztą w ten sposób?

Jest tez podpowiedz
Ponumeruj przyjaciół, a następnie potraktuj uścisk dłoni jako zbiór dwuelementowy , gdzie oraz to numery osób. Zbiór reprezentuje uścisk między osobami oraz . Przypomnij sobie, że w zbiorze kolejność elementów nie ma znaczenia. Policz ile jest zbiorów postaci .
pomózcie :(

1

Odpowiedzi

Najlepsza Odpowiedź!
2010-01-16T02:08:26+01:00
Odpowiedź to 6 uścisków.

Wytłumaczenie:

proste: narysować na płaszczyźnie 4 punkty i połączyć je kreskami - ile kresek, tyle uścisków. Dla 4 jest prosto (jeżeli narysujemy je jako wierzchołki kwadratu to "uściskami" będą 4 jego boki oraz 2 przekątne), ale co gdyby osób było 3 miliardy?

Zatem załóżmy, że wita się n osób (n jest tu liczbą naturalną > 0)

Zastanówmy się:
mamy n osób, każda się wita z każdą - zatem każda podaje rękę n-1 osobom (wszystkim z wyjątkiem siebie samej).
to dałoby nam n(n-1) uścisków, ale zauważmy, że każdy uścisk liczymy dwukrotnie (niech to będzie uścisk pomiędzy osobami A i B - liczymy zdarzenia: osoba A podaje rękę osobie B i osoba B podaje rękę osobie A - a wiemy, że dwie osoby witają się tylko raz), stąd ilość uścisków to: n(n-1)/2
dla n=4 mamy 4*3/2 = 6.
dla 3 miliardów mamy: 3000000000*2999999999/2 = 4499999998500000000 uścisków.

Ogólnie przedstawiono tu problem ilości krawędzi w grafie pełnym o n wierzchołkach.