Олимпиадные задачи из источника «Региональный этап» для 11 класса - сложность 4-5 с решениями

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на  2<i>N</i> + 2  республики так, чтобы никакие два города из одной республики не были соединены дорогой.

На стороне<i> AB </i>треугольника<i> ABC </i>выбрана точка<i> D </i>. Окружность, описанная около треугольника<i> BCD </i>, пересекает сторону<i> AC </i>в точке<i> M </i>, а окружность, описанная около треугольника<i> ACD </i>, пересекает сторону<i> BC </i>в точке<i> N </i>(точки<i> M </i>и<i> N </i>отличны от точки<i> C </i>). Пусть<i> O </i>– центр описанной окружности треугольника<i> CMN </i>. Докажите, что прямая<i> OD </i>перпендикулярна стороне<i> AB </i>.