Ekstrema»Zadanie 2
W pewnym kraju jest skończona liczba miast, każde dwa z nich łączy droga jednokierunkowa. Wykaż, że istnieje miasto, z którego można dojechać do każdego z pozostałych (niekoniecznie bezpośrednio).
W pewnym kraju jest skończona liczba miast, każde dwa z nich łączy droga jednokierunkowa. Wykaż, że istnieje miasto, z którego można dojechać do każdego z pozostałych (niekoniecznie bezpośrednio).
będzie miastem, z którego można dojechać do największej
liczby z pozostałych. Załóżmy, że istnieje miasto
do którego nie
można dotrzeć z
Droga łącząca
i
prowadzi więc
z
do
Wtedy z miasta
można dojechać do
oraz dalej do wszystkich miast, do których można dotrzeć z
Łącznie więc z
można dojechać do większej liczby miast
niż z
sprzecznie z wyborem
