Ре­ше­ние.

Перед нами схема авиа­ли­ний стра­ны, в ко­то­рой, чтобы до­брать­ся из го­ро­да 1 в город 100 не хва­тит 71 перелёта. Ос­нов­ная часть схемы со­сто­ит из по­вто­ря­ю­щих­ся бло­ков по 4 го­ро­да, см. го­ро­да 5, 6, 7 и 8.

Для того, чтобы по­пасть из го­ро­да 1 в город 5, нужно 2 перелёта, затем из го­ро­да 5 в город 93 по 3 перелёта за каж­дые 4 го­ро­да, то есть 66 перелётов, и ещё 4 перелёта, чтобы до­брать­ся из го­ро­да 93 в город 100, итого, ми­ни­мум 72.

С дру­гой сто­ро­ны, 72 перелёта все­гда до­ста­точ­но, чтобы до­брать­ся от лю­бо­го го­ро­да до лю­бо­го.

Чтобы до­ка­зать это, по­ме­стим какой-ни­будь на­чаль­ный город на уро­вень 0, со­единённые с ним (будем на­зы­вать их со­сед­ни­ми) го­ро­да  — на уро­вень 1, их остав­ших­ся со­се­дей  — на уро­вень 2, и так далее. Каж­дый раз на уро­вень k + 1 мы по­ме­ща­ем го­ро­да, со­сед­ние с го­ро­да­ми на уров­не k, если им ранее не со­по­став­лен дру­гой уро­вень. (При­ведённый выше при­мер на­ри­со­ван как раз по этому прин­ци­пу).

Каж­дый город на уров­не k может быть со­единён толь­ко с го­ро­да­ми на уров­нях k − 1, k и k + 1.

Это зна­чит, что на каж­дых трёх под­ряд иду­щих уров­нях в сумме хотя бы 4 го­ро­да. Кроме того, на двух пер­вых уров­нях не менее 4 го­ро­дов, как и на двух по­след­них.

Это озна­ча­ет, что у нас не может быть более

уров­ней, то есть мак­си­маль­но воз­мож­ный номер уров­ня равен 72. Но номер уров­ня  — это и есть ко­ли­че­ство перелётов, не­об­хо­ди­мое, чтобы до­брать­ся в город на этом уров­не из на­чаль­но­го го­ро­да. По­сколь­ку в ка­че­стве на­чаль­но­го го­ро­да можно вы­брать любой из 100 го­ро­дов, это зна­чит, что от лю­бо­го го­ро­да до лю­бо­го можно до­брать­ся не более, чем за 72 перелёта.

 

Ответ: 72.