Zbiór zadań, (zadania różne)
Zadanie 143
Na spotkanie przybyło 15 osób. Okazało się, że każdy uczestnik spotkania znał co najwyżej pięciu innych uczestników. Jaka jest największa możliwa liczba par osób znających się? Zakładamy, że jeśli osoba A zna osobę B, to również osoba B zna osobę A.
Rozwiązanie
Przyporządkujmy osobom przybyłym na spotkanie liczby naturalne od 1 do 15.
Niech z1, z2, ..., z15 oznaczają kolejno liczbę znajomych osoby o odpowiednim numerze.
z1 + z2 + ... + z15 = 2p, gdzie p oznacza ilość par znających się nawzajem.
Mamy zatem 2p ≤ 5 · 15, skąd p ≤ 37.
Par znających się było co najwyżej 37.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>