Решение математической задачи.

Question

Решение математической задачи.

Решение математической задачи.В одном государстве 200 городов и каждый соединён с каждым дорогой с односторонним движением. Докажите, что можно изменить направление на одной дороге так, чтобы от любого города можно было доехать до любого города.
Предположения, советы или полное решение - что-нибудь в помощь :)

Гость

Ответ(ы) на вопрос:

Гость

Ты на листке нарисуй хотя бы 4 города дороги со стрелками и сам все поймешь.

Accepted Answer

Назовём город плохим, если в него нельзя попасть или из него нельзя выехать. Это означает, что все дороги либо ведут в город, либо выходят из города. В любой группе городов может быть не более двух плохих. Рассмотрим дорогу между ними. Изменив направление движения по этой дороге, сведем число плохих городов к нулю, что и требовалось. Будут вопросы, пиши в агент. Удачи!