Задача 64652

Темы:    [ Замощения костями домино и плитками ] [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 8,9

Условие

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

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

Решение

  Пример. Петя может отметить клетки, указанные на рисунке слева. Тогда Вася не сможет одним уголком накрыть больше одной отмеченной клетки. Но девять уголков без наложений не разместить на доске, так как  27 > 25.

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

Ответ

9 клеток.

Замечания

5 баллов

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

олимпиада
Название	Турнир городов
Турнир
Номер	35
Дата	2013/2014
вариант
Вариант	весенний тур, сложный вариант, 8-9 класс
задача
Номер	2