Задача 65873

Темы:    [ Шахматная раскраска ] [ Замощения костями домино и плитками ] [ Четность и нечетность ]

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

Условие

Автор: Кузнецов А.

Квадратная коробка конфет разбита на 49 равных квадратных ячеек. В каждой ячейке лежит шоколадная конфета – либо чёрная, либо белая. За один присест Саша может съесть две конфеты, если они одного цвета и лежат в соседних по стороне или по углу ячейках. Какое наибольшее количество конфет гарантированно может съесть Саша, как бы ни лежали конфеты в коробке?

Решение

  Оценка. При раскладке, указанной на левом рисунке, ни одну из 16 чёрных конфет съесть нельзя, а из 33 белых можно съесть не больше 32 конфет в силу чётности.

  Алгоритм. Покажем, что 32 конфеты можно съесть при любой раскладке. В трёхклеточном уголке всегда можно съесть пару конфет. Значит, в прямоугольнике 2×3 можно съесть 4 конфеты. В квадрате 7×7 можно разместить 8 таких прямоугольников (рис. справа).

Ответ

32 конфеты.

Замечания

8 баллов

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

олимпиада
Название	Турнир городов
номер/год
Номер	38
Дата	2016/17
вариант
Вариант	осенний тур, сложный вариант, 8-9 класс
задача
Номер	4