МАЛЫЙ МЕХМАТ МГУ

Кружок 9-10 класса

Руководители Иван Александрович Дорофеев и Степан Львович Кузнецов
2006/2007 учебный год

Листок 12. Раскраски

1.
Плоскость разбита на части несколькими прямыми. Докажите, что эти части можно раскрасить в два цвета так, что соседние (пересекающиеся по отрезку) части будут покрашены в разный цвет.
2.
Прямая раскрашена в два цвета. Докажите, что на ней найдутся три одноцветные точки A, B и C такие, что AB = BC.
3.
Плоскость раскрасили в χ цветов так, что любые две точки, находящиеся на расстоянии 1 друг от друга, раскрашены в разные цвета. а) Докажите, что при χ = 3 это невозможно. б) Придумайте пример такой раскраски при χ = 7.
Замечание. Возникает естественный вопрос: для какого минимального χ такая раскраска существует (это минимальное χ называется хроматическим числом плоскости)? Ответ на него науке не известен.
4.
Раскрасьте плоскость в два цвета так, чтобы вершины любого равностороннего треугольника со стороной 1 не были покрашены в один цвет.
5.
Докажите, что любая четырёхцветная плоскость содержит две одноцветные точки на расстоянии либо 1, либо ½ (5½ - 1) (это число называется золотым сечением).
6.
Из шахматной доски вырезали верхнее левое и нижнее правое поля. Можно ли остаток разрезать на доминошки (дощечки 1 × 2)?
7.
Фигура „верблюд” ходит по доске 10 × 10 следующим образом: сначала она сдвигается на соседнее поле, а потом ещё на три поля в перпендикулярном направлении. Может ли „верблюд” за несколько ходов перейсти с какого-то исходного поля на соседнее с ним?
8.
Фигура „слонёнок” ходит по шахматной доске, как и слон, по диагонали, но только на одно поле. Можно ли раскрасить клетки шахматной доски в два цвета так, чтобы при каждом ходе „слонёнок” переходил на поле другого цвета? Если да, то сколько существует таких раскрасок?
9.
Игра <<15>> представляет собой квадратную коробочку 4 × 4 с фишками, занумерованными числами от 1 до 15. В начале игры пустое поле располагалось в правом нижнем углу. За один ход я сдвигал одну фишку на соседнее с ней пустое поле. Через несколько ходов порядок фишек изменился, но пустое поле вновь оказалось в правом нижнем углу. Докажите, что я сделал чётное число ходов.
10.
Пространственный лабиринт состоит из 27 кубических комнат, расположенных в виде куба 3× 3× 3. Из любой комнаты можно перейти в любую соседнюю (через любую стену, пол или потолок). Исследователь лабиринта находится в центральной комнате. Сможет ли он пройти по всем комнатам, не проходя ни одной комнаты дважды?