Задача 98365

Темы:    [ Деревья ] [ Раскраски ] [ Куб ] [ Доказательство от противного ] [ Перебор случаев ]

Сложность: 4+ Классы: 9,10

Условие

Автор: Шаповалов А.В.

Раскрашенный в чёрный и белый цвета кубик с гранью в одну клетку поставили на одну из клеток шахматной доски и прокатили по ней так, что кубик побывал на каждой клетке ровно по одному разу. Можно ли так раскрасить кубик и так прокатить его по доске, чтобы каждый раз цвета клетки и соприкоснувшейся с ней грани совпадали?

Решение 1

  Допустим, что существуют такая раскраска и такой способ перекатывания, о которых идёт речь в условии. Рассмотрим все общие стороны соседних клеток шахматной доски. Те из них, через которые кубик не перекатывался, закрасим красным цветом. Поскольку кубик побывал на всех клетках доски, красная фигура не разделяет доску на части. Значит, она не содержит циклов, то есть является объединением нескольких деревьев. Рассмотрим одно из этих деревьев. Оно, как известно, имеет хотя бы два листа (лист – это вершина, из которой выходит только один отрезок). Если бы эти два листа принадлежали границе доски, то красные отрезки делили бы доску на части. Значит, существует лист A, не лежащий на границе доски. Кубик обязан перекатиться через все три не красных отрезка, которые выходят из точки A. Это значит, что кубик должен "обойти" точку A, как показано на рисунке (красный отрезок изображён жирной линией). При этом обходе с клетками, граничащими по выходящему из точки A красному отрезку, соприкасается одна и та же грань кубика. Значит, эти клетки должны быть одного цвета, что противоречит шахматной раскраске.

Решение 2

Автор: Бегун Б.И.

  Будем решать более общую задачу: поставим раскрашенный в два цвета кубик на бесконечную шахматную доску и посмотрим, в какие её клетки он может “прикатиться”. Разумеется, ответ зависит от раскраски кубика. Случаи, когда все грани одного цвета и когда одна грань одного цвета, а пять – другого, не будем разбирать ввиду их очевидности. Остается четыре принципиально разных случая раскраски: в двух из них две грани одного цвета и четыре другого, в двух других – по три грани каждого цвета. Отметим, что раскраска по существу сводится к тому, что кубику запрещено перекатываться через некоторые ребра (между гранями одного цвета). Поэтому на рисунках мы изобразили не цвета граней, а эти "запретные" ребра (выделены жирным).

  Ниже для каждой из этих четырёх раскрасок кубика приведён соответствующий рисунок на плоскости. В каждом случае легко проверить, что если мы поставим кубик на любую незатенённую клетку так, чтобы жирные ребра нижней грани кубика совпали с жирными линиями на плоскости, то после перекатывания через "незапрещённое" (нежирное) ребро в соседнюю клетку, он снова попадает в положение, когда жирные рёбра нижней грани совмещаются с жирными рёбрами клетки, на которой она стоит.

  Таким образом, кубик не может выйти за пределы светлой области и в затенённую часть плоскости никогда не попадёт. В частности, во всех случаях видно, что множество “доступных” для кубика клеток не содержит ни одного квадрата 2×2.
  Другие возможные начальные положения сводятся к разобранным с помощью параллельных переносов и поворотов на 90°.

Ответ

Нельзя.

Замечания

8 баллов

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1998
выпуск
Номер	2
Задача
Номер	М1632
олимпиада
Название	Турнир городов
Турнир
Дата	1997/1998
Номер	19
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
Задача
Номер	5