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