ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98224
Темы:    [ Раскраски ]
[ Принцип Дирихле (углы и длины) ]
[ Шахматные доски и шахматные фигуры ]
[ Примеры и контрпримеры. Конструкции ]
[ Четность и нечетность ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В какое наименьшее число цветов нужно раскрасить клетки бесконечного листа клетчатой бумаги, чтобы
  а) каждые две клетки на расстоянии 6 были покрашены в разные цвета?

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


Решение

  а) См. задачу 97823.

  б) Пример восьмицветной раскраски показан на рис. слева.

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


Ответ

а) В 4 цвета;  б) в 8 цветов.

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

журнал
Название "Квант"
год
Год 1984
выпуск
Номер 9
Задача
Номер М883

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .