Олимпиадные задачи из источника «1999 год» для 10 класса - сложность 3 с решениями

Раскраска вершин графа называется <i>правильной</i>, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в <i>k</i> цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех <i>k</i> цветов ровно по одному разу.

Найдите все такие целые положительные k, что число

1...12...2-2...2 является квадратом целого числа. (В первом слагаемом (уменьшаемом) всего 2000 цифр, из которых на последних местах стоят цифры "2" в количестве k штук, а остальные цифры - "1"; второе слагаемое (вычитаемое) состоит из 1001 поряд стоящих цифр "2")

2<i>n</i> радиусов разделили круг на 2<i>n</i> равных секторов: <i>n</i> синих и <i>n</i> красных, чередующихся в произвольном порядке. В синие сектора, начиная с некоторого, записывают против хода часовой стрелки числа от 1 до <i>n</i>. В красные сектора, начиная с некоторого, записывают те же числа, но по ходу часовой стрелки. Докажите, что найдётся полукруг, в котором записаны все числа от 1 до <i>n</i>.