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

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

Условие

Петя раскрасил каждую клетку квадрата 1000×1000 в один из 10 цветов. Также он придумал такой 10-клеточный многоугольник Ф, что при любом способе положить его по границам клеток на раскрашенный квадрат, все 10 накрытых им клеток будут разного цвета. Обязательно ли Ф – прямоугольник?


Решение

  Заменим цвета цифрами.

  Первый способ. Раскрасим сначала клетки квадрата в шахматном порядке. Занумеруем все белые клетки пятью цифрами так, чтобы любой кусок длины 5 белой диагонали содержал разные цифры. Это легко сделать, так как при повороте квадрата на 45° белые клетки образуют привычную прямоугольную сетку, а куски диагоналей превращаются в прямоугольники 1×5. Аналогично занумеруем чёрные клетки пятью другими цифрами.
  На рисунке слева приведён пример такой раскраски и два положения Петиного многоугольника. Ясно, что в любом возможном положении он накрывает два диагональных куска длины 5 разного цвета, следовательно, содержит все 10 цифр.

  Второй способ. Расставим цифры в первой строке с периодом 10, как указано на рис. справа. Каждая следующая строка получается из предыдущей сдвигом на 3 клетки вправо. Поскольку 3 и 10 взаимно просты, по вертикали цифры тоже расставлены с периодом 10. Петин многоугольник имеет вид буквы Н. В двух показанных положениях он многоугольник содержит все 10 цифр. В силу периодичности он содержит все 10 цифр и при любом другом расположении.


Ответ

Не обязательно.

Замечания

1. Раскраска из второго способа годится и для фигуры из первого способа.

2. 8 баллов.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 80
Год 2017
класс
Класс 9
задача
Номер 5
олимпиада
Название Турнир городов
номер/год
Номер 38
Дата 2016/17
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 4

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

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