Atrisinājums

Pats mazākais ceļu skaits ir \(\frac{100 \cdot 99}{2}-(100-2)=4852\). Atrisināsim uzdevumu vispārīgajā gadijumā ar \(n\) pilsētām un pamatosim, ka mazākais iespējamais ceļu skaits ir \(\frac{n(n-1)}{2}-(n-2)\), lai no jebkuras pilsētas noteikti varētu aizbraukt uz jebkuru citu pilsētu.

Vispirms pamatosim, ka ar mazāku ceļu skaitu nepietiek. Atliek parādīt vienu piemēru, kā pilsētām jābūt savienotām ar ceļiem, lai uz vienu no pilsētām nevar nokļūt. Aplūkosim gadīumu, kad kopējais ceļu skaits ir par vienu mazāks, tas ir, \(\frac{n(n-1)}{2}-(n-1)\), un ka ir kāda pilsēta, uz kuru neiet neviens ceļs̆, bet katras divas atlikušās pilsētas ir savā starpā savienotas ar ceļu. Tādā gadījumā tam vajag tieši \(\frac{(n-1)(n-2)}{2}=\frac{n(n-1)}{2}-(n-1)\) ceļus. Tātad meklētais piemērs ir atrasts un ceļu skaits nevar būt mazāks par \(\frac{n(n-1)}{2}-(n-2)\).

Pamatosim, ka ar \(\frac{n(n-1)}{2}-(n-2)\) ceļiem pietiek, lai no jebkuras pilsētas noteikti varētu aizbraukt uz jebkuru citu pilsētu. Uzbūvēsim no sākuma lielāko iespējamo ceļu skaitu starp \(n\) pilsētām, tas ir, \(\frac{n(n-1)}{2}\). Pēc tam nojauksim \((n-2)\) ceļus. Pamatosim, ka arī pēc to nojaukšanas izpildās uzdevuma nosacījumi. Aplūkosim divas patvaļīgas pilsētas, apzīmēsim tās ar \(A\) un \(B\), pārējās \((n-2)\) pilsētas apzīmēsim attiecīgi ar \(X_{1}, X_{2}, \ldots, X_{n-2}\). Aplūkosim \((n-1)\) maršrutu, kā no pilsētas \(A\) var nokļūt pilsētā \(B\): maršrutu \(A \leftrightarrow B\) un \((n-2)\) maršrutus \(A \leftrightarrow X_{i} \leftrightarrow B\). Ievērojam, ka viena ceļa nojaukšana sabojā ne vairāk kā vienu no šiem maršrutiem, tāpēc pēc \((n-2)\) ceļu nojaukšanas vismaz viens no šiem maršrutiem, pa kuru nokļūt no pilsētas \(A\) uz \(B\), vēl paliks. Tātad ar \(\frac{n(n-1)}{2}-(n-2)\) ceļiem pietiek, lai izpildītos uzdevuma nosacījumi.