Atrisinājums

(A) Pieņemsim, ka ir \(2\) pilsētas, īsākais ceļš starp kurām iet caur vismaz četrām citām pilsētām. Tad šajā ceļā noteikti ir \(2\) tādas pilsētas, starp kurām īsākais ceļš iet tieši caur \(4\) citām pilsētām.

Apzīmēsim šīs \(2\) pilsētas ar \(A_{1}\) un \(A_{6}\), bet četras pilsētas starp tām- ar \(A_{2}, A_{3}, A_{4}\) un \(A_{5}\) (skat. 9.zīm.). Ja kāda cita pilsēta \(B\) ir savienota ar \(4\) vai vairāk no \(A_{1}, A_{2}, \ldots A_{6}\), tad šo pilsētu var izmantot, lai "saīsinātu" īsāko ceļu starp \(A_{1}\) un \(A_{6}\). Piemēram, zīmējumā redzamajā gadījumā posmu \(A_{2}-A_{3}-A_{4}-A_{5}\) var aizstāt ar \(A_{2}-B-A_{5}\). Tāpēc šāda situācija nav iespējama.

Tāpēc, katra cita pilsēta \(B\) var būt savienota ne vairāk kā ar \(3\) no \(A_{1}, A_{2}, \ldots A_{6}\). Līdz ar to, ceļu skaits ir ne vairāk kā:

• \(5\) ceļi ceļā no \(A_{1}\) uz \(A_{6}\);

• Pa \(3\) ceļiem no katras citas pilsētas \(B\) uz \(A_{1}, A_{2}, \ldots A_{6}\) (kopā, tas var dot \(4 \cdot 3=12\) ceļus, jo ir \(4\) citas pilsētas \(B\)).

• \(6\) ceļi starp pārējām \(4\) pilsētām \(B_{1}, B_{2}, B_{3}, B_{4}\), jo no \(4\) pilsētām var izveidot \((4:3):2=6\) pilsētu pārus.

Tātad ir ne vairāk kā \(5+12+6=23\) ceļi.

(B) Ja \(A_{1}, A_{2}, \ldots A_{6}\) savieno, kā parādīts zīmējumā, katru citu pilsētu \(\mathrm{B}_{i}, i=1, \ldots, 4\), savieno ar \(A_{4}\), \(A_{5}\) un \(A_{6}\) un katras \(2\) pilsētas \(B_{i}\) un \(B_{j}\) savieno savā starpā, tad izveidojas \(23\) ceļi un īsākajā ceļā starp \(A_{1}\) un \(A_{6}\) ir \(4\) pilsētas. (Tajā noteikti jābūt \(A_{2}, A_{3}, A_{4}\) un vēl vienai pilsētai starp \(A_{4}\) un \(A_{6}\).)