В государстве 36 городов, при этом любые два из их соединены дорогой.

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