Найдите задачу для урока, кружка или самостоятельной работы.
Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в k цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех k цветов ровно по одному разу.
Петя и Вася нашли 100 кубиков одинакового размера, 50 из них были белого цвета и 50 – чёрного. Они придумали игру. Назовём башенкой один или несколько кубиков, стоящих друг на друге. В начале игры все кубики лежат по одному, то есть имеется 100 башенок. За один ход игрок должен одну из башенок поставить на другую (переворачивать башенки нельзя), при этом в новой башенке не должно быть подряд двух одинаковых по цвету кубиков. Ходят по очереди, начинает Петя. Кто не может сделать ход – проиграл. Кто может обеспечить себе победу, как бы ни играл его соперник?
На клетчатой доске лежат доминошки, не касаясь даже углами. Каждая доминошка занимает две соседние (по стороне) клетки доски. Нижняя левая и правая верхняя клетки доски свободны. Всегда ли можно пройти из левой нижней клетки в правую верхнюю, делая ходы только вверх и вправо на соседние по стороне клетки и не наступая на доминошки, если доска имеет размеры а) клеток; б) клеток?