Sākums

LV.SOL.1998.11.5   lv

Valstī ir \(n\) pilsētas. Starp katrām divām pilsētām uzbūvēts tieši viens ceļš, uz kura ieviesta vienvirziena kustība; ceļu krustpunktu ārpus pilsētām nav (izmantoti viadukti).

Pierādīt, ka eksistē tāda pilsēta, uz kuru var aizbraukt no jebkuras citas, braucot pa augstākais diviem ceļiem.

Hide solution

Atrisinājums

Aplūkosim pilsētu \(A\), kurā ieiet visvairāk ceļu (šo ceļu skaitu apzīmēsim ar \(m\)). Pierādīsim, ka tai izpildās uzdevuma prasības.

Pieņemsim pretējo, ka ir tāda pilsēta \(B\), no kuras nevar aizbraukt uz \(A\) augstākais pa diviem ceļiem. Pilsētu grupā \(X\), no kurām iet ceļš uz \(A\) ir \(m\) pilsētas. Skaidrs, ka no \(B\) nevar aizbraukt uz grupas \(X\) pilsētu un uz pilsētu \(A\); tātad no šīm \(m+1\) pilsētām iet ceļš uz \(B\), bet tā ir pretruna ar pieņēmumu, ka pilsētā \(A\) ieiet visvairāk ceļu. Prasītais pierādīts.