Zbiór zadań, (zadania różne)
Zadanie 158
Pewien przewoźnik zaplanował system połączeń pomiędzy wybraną liczbą miast, w taki sposób, że każde miasto ma połączenie z co najwyżej trzema innymi miastami oraz z każdego miasta do każdego innego miasta można dostać się z co najwyżej jedną przesiadką. Jaka maksymalna liczba miast została objęta takim systemem połączeń?
Rozwiązanie
Z dowolnego miasta A objętego systemem połączeń można bezpośrednim kursem dostać się do co najwyżej trzech miast, a z każdego z tych miast można bezpośrednim kursem dostać się do co najwyżej dwóch miast (nie wliczając miasta A). Wszystkich miast nie może być więcej niż 1 + 3 + 3 · 2 = 10. Dla dziesięciu miast można taką sieć połączeń zrealizować tworząc pary połączonych miast: A1A2, A2A3, A3A4, A4A5, A5A1, A1A6, A2A7, A3A8, A4A9, A5A10, A6A8, A6A9, A7A9, A7A10, A8A10.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>