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

Проект МЦНМО
при участии
школы 57
Задача 110208
Темы:    [ Задачи с ограничениями ]
[ Правило произведения ]
[ Шахматные доски и шахматные фигуры ]
[ Раскраски ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Назовём раскраску доски 8×8 в три цвета хорошей, если в любом уголке из пяти клеток присутствуют клетки всех трёх цветов. (Уголок из пяти клеток – это фигура, получающаяся из квадрата 3×3 вырезанием квадрата 2×2.)  Докажите, что количество хороших раскрасок не меньше чем 68.


Решение

  Каждый уголок содержит горизонтальный прямоугольник 1×3. Любую горизонталь можно покрасить в три цвета так, чтобы каждый прямоугольник 1×3 содержал клетки трёх различных цветов, ровно 6 способами (получится раскраска ABCABCAB, а цвета A, B, C можно выбрать 6 способами).
   Это означает, что раскраска, при которой каждая горизонталь покрашена указанным способом, будет хорошей. Поскольку каждую горизонталь можно покрасить независимо от других, число хороших раскрасок такого вида будет в точности 68.
  Но есть еще хорошие раскраски, которые мы не посчитали, например такая, при которой каждая из горизонталей одноцветна, а цвета горизонталей чередуются указанным выше образом (в этом случае любой вертикальный прямоугольник 1×3 будет содержать клетки трёх различных цветов). Поэтому общее количество хороших раскрасок больше 68.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2006
Этап
Вариант 4
Класс
Класс 10
задача
Номер 06.4.10.2

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

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