Страна и дороги

[Redirect]

В одном государстве 200 городов и каждый соединен с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.




P.S. задача взята из математической олимпиады МЭСИ
      Ответа как и решения не знаю, если кто может - решите

[Smith]

а изначально этого нельзя было сделать? или нельзя было напрямую? признаться, не совсем понимаю условие

[Redirect]

Слово-в-слово из источника, если честно сам задумался над этим, может, надо доказать, что, изменив направление движения на 1 дороге, вы не нарушите возможность попадания из 1 города в любой другой

[Smith]

впрочем, кажется не важно.
количество дорог, соединяющих каждый город с другими (вход.+исход.) составляет 199.
при этом соотношение вход./исход. в каждом отдельном городе может быть любым от 199/0 до 0/199.
однако, только 1 город (А) может иметь 199 входящих дорог, т.к. тогда из каждого оставшегося 199 городов будет выходить хотя бы 1 исходящая дорога, направленная в этот город А.
аналогично, только 1 город (В) может иметь 199 исходящих дорог, т.к. тогда в каждый из оставшихся 199 городов будет входить хотя бы 1 дорога, исходящая из города В.
в таких случаях  меняем направление дороги между А и В.
если города с 199 входящими дорогам не существует, и не существует города с 199 исходящими дорогами, то на исходный момент можно проехать из любого города в любой. тогда просто меняюм какую-либо из дорог, не нарушая при этом равновесия (не более 198 вход/исх дорог)

[Smith]

да еще. может быть ситуация, когда город с 199 входящими дорогами есть, а города со 199 исходящими нет (или наоборот). тогда действуем по принципу не более 198 вход./исход. дорог на один город.