7. Zadatak

Prvo rješenje.

Neka je $A$ neki grad iz kojeg polazi najveći broj linija. Tvrdimo da je $A$ grad s traženim svojstvom.

Neka su $B_1,\ldots,B_k$ gradovi u koje dolaze linije iz $A$. Neka je $C$ bilo koji drugi grad (različit od $A,B_1,\ldots,B_k$). Tada postoji linija iz $C$ u $A$.

Ako postoji linija iz nekog grada $B_i$ u $C$, onda iz $A$ u $C$ možemo doći jednim presjedanjem.

Ako bi sve linije između $C$ i gradova $B_1,\ldots,B_k$ polazile iz $C$, onda bi iz $C$ polazilo barem $k+1$ linija, dakle više nego iz $A$, što je suprotno načinu kako smo odabrali $A$.

Dakle, iz grada $A$ u svaki drugi grad možemo doći direktno ili jednim presjedanjem.

Drugo rješenje.

Tvrdnju dokazujemo matematičkom indukcijom po broju gradova.

Za bazu indukcije možemo uzeti situaciju s dva grada $A$ i $B$ među kojima postoji linija iz $A$ u $B$. Tada je $A$ traženi grad.

Pretpostavimo da tvrdnja vrijedi kad imamo $n$ gradova. Promotrimo situaciju s $n+1$ gradova i među njima odaberimo bilo koji grad $C$. Prema pretpostavci, među svim gradovima bez grada $C$ postoji grad $A$ iz kojeg je moguće doći do svih drugih gradova različitih od $C$ direktno ili jednim presjedanjem. Kao u prethodnom rješenju možemo gradove do kojih se može doći direktno iz $A$ označiti $B_1,\ldots,B_k$.

Ako postoji linija iz $A$ ili iz bilo kojeg grada $B_i$ u $C$, onda iz $A$ možemo doći i u $C$ s najviše jednim presjedanjem, pa je dokaz gotov i traženi grad je grad $A$.

Ako iz $C$ polaze linije prema $A$ i prema svim gradovima $B_1,\ldots,B_k$, onda je traženi grad $C$. Zaista, za bilo koji grad $D$ koji je različit od $A,C,B_1,\ldots,B_k$, postoji linija iz nekog grada $B_i$ u $D$ jer se iz $A$ može doći u $D$ s presjedanjem, a to onda pokazuje da se i iz grada $C$ preko $B_i$ može doći u $D$.

Time smo proveli korak indukcije, pa prema principu matematičke indukcije tvrdnja vrijedi za bilo koji broj gradova.