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

Занятие 4. Раскраски

1.	Каждую грань куба 3×3×3 разбили на три прямоугольника 3×1 так, что длинные стороны прямоугольников на соседних гранях перпендикулярны друг другу. В какое наименьшее число цветов можно раскрасить 18 полученных прямоугольников, чтобы любые два прямоугольника, имеющие общий отрезок границы, были разного цвета?
2.	Плоскость раскрашена в красный и синий цвета. Докажите, что найдутся две одноцветные точки на расстоянии 1 метр друг от друга.
3.	а) Плоскость раскрашена в 4 цвета. Докажите, что найдётся трёхцветная прямая. б) Плоскость раскрашена в 3 цвета. Обязательно ли на ней найдётся трёхцветная прямая?
4.	В булке оказался запечён изюм двух сортов. Докажите, что внутри булки найдутся две такие точки на расстоянии 1 см, что либо они не принадлежат никаким из изюмин, либо принадлежат изюминам одного сорта.

Определение. Граф называют правильно раскрашенным, если все его вершины покрашены так, что любые две вершины, соединённые ребром, покрашены в разный цвет.

Определение. Карту называют правильно раскрашенной, если любые две страны, имеющие общий участок границы, покрашены в разные цвета (одна точка участком границы не считается).

5.	Плоскость разбита на части несколькими прямыми и окружностями. Докажите, что полученную карту можно правильно раскрасить в два цвета.
6.	Для каждого p придумайте граф, который нельзя правильно раскрасить в p цветов, а любой его подграф с меньшим числом вершин — можно.
7.	Расположите на плоскости несколько одинаковых квадратов так, чтобы получилась карта, не раскрашиваемая в три цвета.
8.	Остров Тото имеет форму многоугольника. На нём расположено несколько стран, каждая из которых имеет форму треугольника, причём каждые две граничащие страны имеют целую общую сторону (то есть вершина никакого из треугольника разбиения не лежит внутри стороны другого треугольника разбиения). Докажите, что карту этого острова можно правильно раскрасить тремя красками.