Предположим, что на левом берегу находится только один город. Тогда, согласно второму заявлению мэра этого города, в нем нет прямых рейсов, то есть на правом берегу могут быть не более 12 городов. Пусть на левом берегу находятся два города. Согласно второму заявлению мэра первого города, в нем нет прямых рейсов, значит, во втором городе есть прямые рейсы, и по первому заявлению мэра второго города, их не менее 13. Но во втором городе должно быть не более 12 прямых рейсов на правый берег, значит, два города на левом берегу быть не могут. Рассмотрим теперь случай, когда на левом берегу три города. По второму заявлению мэра первого города, в нем нет прямых рейсов, значит, все 13 рейсов на правый берег идут из второго города. Но по первому заявлению мэра второго города, во второй город их идет не менее 13. Значит, на правом берегу должно быть не менее 13 очередных городов. Но по первому заявлению мэра третьего города, в нем также есть прямые рейсы на правый берег, и городов на правом берегу должно быть не менее 14. Теперь рассмотрим случай, когда на левом берегу четыре города. По второму заявлению мэра первого города, в нем нет прямых рейсов, значит, все 13 рейсов на правый берег идут из второго города. Но по первому заявлению мэра второго города, во второй город их идет не менее 13. Значит, на правом берегу должно быть не менее 13 очередных городов. По первому заявлению мэра третьего города, в нем также есть прямые рейсы на правый берег, и в нем также должно быть не менее 13 городов. Но по первому заявлению мэра четвертого города, в нем также есть прямые рейсы на правый берег, значит, городов на правом берегу должно быть не менее 14. Таким образом, наименьшее число городов на левом берегу, удовлетворяющее всем условиям, равно 4. Значит, на правом берегу должно быть не менее 14 городов. Ответ: наименьшее число городов, располагающихся вдоль берегов реки, равно 18.