Высшая лига и лига 9 классов (8)

Разделим произвольным образом все города на три республики. Пусть A — количество внутриреспубликанских дорог во всех республиках.

Если из какого-то города выходит более одной внутриреспубликанской дороги, то перенесем этот город в ту республику, в которой из него будет выходить не более одной внутриреспубликанской дороги (это возможно, так как из каждого города выходит только пять дорог). При этом сумма A уменьшится. Действительно, в первой республике пропадут, по крайней мере, две дороги, а во второй возникнет не более одной.

Так как сумма A не может уменьшаться бесконечно долго, то наступит момент, когда из каждого города будет выходить не более одной внутриреспубликанской дороги. В этот момент A не будет превосходить 1001.

Пусть A = 1001, тогда из каждого города внутрь республики ведет ровно одна дорога. Возможны три случая.

Пусть из каждого города две дороги идут в одну республику и две дороги в другую республику. Тогда во всех трех республиках равное количество городов, что невозможно (2002 не кратно трем).

Если имеется город, у которого оставшиеся четыре дороги ведут в одну республику (а в третью республику не ведет ни одной дороги), то передадим этот город в эту третью республику. Количество внутриреспубликанских дорог при этом уменьшится.

Если есть город, из которого одна дорога ведет в первую республику, а три дороги в другую республику, то перекинем его в первую. Возможно, из какого-то города в первой республике стало внутрь выходить две дороги (A при этом не изменилось). Начнем перекидывать города как вначале (из которых ведет две дороги внутрь родной республики). При первом таком перекидывании A уменьшится.

В любом случае A не превосходит 1000. Что и требовалось доказать.

Автор: А. Шаповалов.