Valstī Alfa ir \(n\) pilsētas, \(n \geq 2\). Dažas no šīm pilsētām ir savienotas ar dažām citām ar ceļiem. Ir zināms, ka katrs ceļš savieno tieši divas dažādas pilsētas, katras divas pilsētas savieno ne vairāk kā viens ceļš, turklāt pa izbūvētajiem ceļiem no jebkuras pilsētas ir iespējams aizbraukt uz jebkuru citu vienā vienīgā veidā.
(A) Pierādīt, ka ir vismaz viena pilsēta, no kuras iziet tieši viens ceļš.
(B) Pierādīt, ka pilsētas var sanumurēt ar skaitļiem \(1,2, \ldots, n\) tā, lai jebkuru divu pilsētu, kuras ir savienotas ar ceļu, numuru reizinājums būtu pāra skaitlis.
(A) Ar matemātisko indukciju pamatosim, ka ir vismaz divas pilsētas, no kurām no katras iziet tieši viens ceļš.
Ja \(n=2\), tad apgalvojums ir acīmredzami patiess (starp divām pilsētām var būt uzbūvēts tikai viens ceļš, kas savieno šīs pilsētas).
Pieņemsim, ka vajadzīgais ir pamatots pie \(n < k\) pilsētām un pamatosim to arī \(k\) pilsētu gadījumā, \(k \geq 3\). Patvaļīgi izvēlēsimies vienu ceļu, pieņemsim, ka tas savieno pilsētas \(A\) un \(B\). „Nodzēsīsim" (pieņemsim, ka tas vairs nav izbraucams) ceļu \(AB\), un visas pilsētas sadalīsim divās grupās grupā \(V_{1}\) (pilsētas, uz kurām iespējams nokļūt no pilsētas \(A\), ieskaitot pašu \(A\)), un grupā \(V_{2}\) (pilsētas, uz kurām iespējams nokļūt no \(B\), ieskaitot pašu \(B\)). Ievērosim, ka katra pilsēta ietilpst tieši vienā no grupām: ja būtu tāda pilsēta \(C\), kurā iespējams nokļūt gan no \(A\), gan \(B\), tad sākotnēji valstī Alfa no pilsētas \(A\) uz \(B\) varētu nokļūt vairāk nekā vienā veidā (uz \(B\) no \(A\) varētu nokļūt gan pa ceļu \(AB\), gan pa ceļiem, kas savieno \(A\) ar \(C\) un \(C\) ar \(B\) )- pretruna. Vismaz vienā no grupām (pienemsim, ka tā ir \(V_{1}\) ) ir vismaz divas pilsētas; tas nozīmē, ka, saskaņā ar induktīvo hipotēzi, tajā ir vismaz divas pilsētas, no kurām no katras iziet tieši viens ceļš. Ja neviena no šīm pilsētām nav \(A\), tad vajadzīgais ir pamatots (arī sākotnēji no katras šīm pilsētām iziet tikai viens ceļš). Apskatām gadījumu, kad viena no šīm pilsētām ir \(A\) (otru pilsētu apzīmēsim ar \(X\) ). Ir divas iespējas:
Līdz ar to ir pamatota induktīvā pāreja un apgalvojums ir pierādīts.
(B) Ar matemātisko indukciju parādīsim, ka katrai no pilsētām var piešķirt vērtību \(-1\) vai \(1\) tā, lai jebkuru divu pilsētu, kuras ir savienotas ar ceļu, vērtības būtu pretējas. Ja \(n=2\), tad apgalvojums acīmredzami ir patiess. Pieņemsim, ka vajadzīgais ir pierādīts, ja \(n=k\) un pamatosim, ka tas ir patiess arī, ja \(n=k+1\). Izvēlamies jebkuru pilsētu \(A\), no kuras iziet tieši viens ceļš (pieņemsim, ka šis ceļš iet uz pilsētu \(B\) ). Aplūkosim visu pilsētu (neskaitot \(A\) ) un visu ceļu (neskaitot ceļu \(AB\) ) veidoto sistēmu. Saskaņā ar induktīvo hipotēzi, šīm \(k\) pilsētām var piešķirt vērtības \(1\) un \(-1\) vajadzīgajā veidā. Tad pilsētai \(A\) piešķir vērtību \(-v\), kur \(v\) ir pilsētas \(B\) vērtība. Induktīvā pāreja izdarīta.
Ja pilsētām ir piešķirtas vērtības aprakstītajā veidā, tad apzīmēsim ar \(m\) to pilsētu skaitu, kurām vērtība ir \(1\), bet ar \(l\)- to pilsētu skaitu, kurām vērtība ir \(-1\). Ja \(m < l\), tad visām pilsētām, kurām vērtība ir \(1\), piekārto pāra numurus; ja \(l \leq m\), tad pāra numurus piekārto pilsētām, kuru vērtība ir \(-1\) . Pārējām pilsētām atlikušos numurus piekārto patvaļīgi.
Tā kā katrām divām ar ceļu savienotām pilsētām ir pretējas vērtības, tad no jebkurām divām ar ceļu savienotām pilsētām vismaz vienai ir piekārtots pāra numurs. Taču tad šo pilsētu numuru reizinājums ir pāra skaitlis.