Ясно что во время пу­те­ше­ствий ни­ка­кие два бо­га­тых ту­ри­ста (или два бед­ных) не могли ока­зать­ся в одном го­ро­де. С дру­гой сто­ро­ны, усло­вие за­да­чи не за­пре­ща­ет на­хо­дить­ся в одном го­ро­де од­но­вре­мен­но бед­но­му и бо­га­то­му ту­ри­сту, важно лишь, чтобы в на­чаль­ный и в ко­неч­ный мо­мент в каж­дом го­ро­де было по од­но­му ту­ри­сту.

До­пу­стим, что среди ту­ри­стов име­ет­ся 25 (или более) «бо­га­чей». На­ри­су­ем граф: вер­ши­ны  — это го­ро­да, из каж­до­го го­ро­да про­ве­дем самый до­ро­гой вы­хо­дя­щий путь. Тогда этот граф пред­став­ля­ет собой лес, в каж­дом де­ре­ве ко­то­ро­го все ребра на­прав­ле­ны к корню, за ис­клю­че­ни­ем един­ствен­но­го ребра, вы­хо­дя­ще­го из корня,  — это ребро в де­ре­ве как бы дву­сто­рон­нее. Возь­мем бо­га­ча, ко­то­рый рас­по­ло­жен ближе всего к корню сво­е­го де­ре­ва. Этот богач будет в те­че­ние 25 ходов самым близ­ким к корню. Зна­чит, он про­едет по го­ро­дам, в ко­то­рых еще не было дру­гих бо­га­чей. Это может быть толь­ко если граф  — это путь из 50 вер­шин, бо­га­чи за­ни­ма­ют пер­вые 25 вер­шин этого пути (т. е. по­ло­ви­ну) и гусь­ком дви­жут­ся по этому пути в сто­ро­ну вто­рой по­ло­ви­ны. От­сю­да сле­ду­ет, что бо­га­чей не может быть боль­ше 25, а также что ко­ли­че­ство пе­ре­ез­дов тоже не пре­вос­хо­дит 25. Тогда бед­ных ту­ри­стов тоже 25 и они дви­га­ют­ся по ана­ло­гич­но­му «бед­но­му» пути, при­чем в на­чаль­ный мо­мент они за­ни­ма­ют всю вто­рую по­ло­ви­ну «бо­га­то­го» пути. Эти пути не имеют общих зве­ньев, и при этом дви­же­ние бед­ня­ков та­ко­во, что с каж­дым ходом они долж­ны осво­бож­дать от сво­е­го при­сут­ствия оче­ред­ную вер­ши­ну вто­рой по­ло­ви­ны бо­га­то­го пути, сме­ща­ясь гусь­ком в первую по­ло­ви­ну. Тогда дви­же­ние ту­ри­стов может про­ис­хо­дить, на­при­мер, сле­ду­ю­щим об­ра­зом. Обо­зна­чим го­ро­да До­пу­стим, что путь

со­став­лен из самых до­ро­гих авиа­ли­ний, для опре­де­лен­но­сти пусть цена пе­ре­ле­та равна руб­лей. А «бед­ный путь» пусть сна­ча­ла про­хо­дит по го­ро­дам с боль­ши­ми чет­ны­ми но­ме­ра­ми, потом  — по го­ро­дам с боль­ши­ми не­чет­ны­ми, а далее  — с ма­лы­ми: сна­ча­ла с чет­ны­ми, потом с не­чет­ны­ми:

Цены этих авиа­ли­нии пусть убы­ва­ют от 49 до 1 рубля при дви­же­нии вдоль этого пути. Цены осталь­ных авиа­ли­ний на­зна­чим про­из­воль­но в диа­па­зо­не от 100 до 100 000 руб­лей.

Ответ: при