В государстве 36 городов, причем любые два из них соединены дорогой. Однажды, после сильного снегопада все дороги оказались
Вопрос посетителя
В государстве 36 городов, причем любые два из них соединены дорогой. Однажды, после сильного снегопада все дороги оказались занесены снегом. С тех пор каждый день дорожные работники расчищают 35 дорог, а каждую ночь местная метель в районе одного из городов заново заметает все дороги, ведущие из этого города. Докажите, что дорожные работники могут действовать так, что однажды вечером заметенных дорог останется не более 18
Ответ эксперта
Решение. Разобьем 36 городов на 18 пар, и мысленно отметим соответствующие 18 дорог. Эти 18 дорог будем чистить в последнюю очередь, только если нет других заметенных снегом дорог. Если к вечеру была расчищена хотя бы 1 из этих 18 дорог, неочищенных осталось меньше 18, что и требовалось. В противном случае ночью метель заметет не более 34 очищенных дорог (из одного города ведет 35 дорог, одна из которых входит в число мысленно отмеченных 18, которые точно неочищенные). Таким образом, за сутки будет очищено 35 дорог, а вновь заметено только не более 34. То есть каждые сутки число заметенных дорог будет уменьшаться и, рано или поздно, станет не больше 18.
