№ 2 *{Серьги с бриллиантами} В ювелирную лавку пришла покупательница и заказала особенные серьги-пластины. Каждая серьга - это поле из клеток . В каждую клетку мастер может вставить бриллиант или оставить её пустой. Но есть прихоть заказчицы. Для каждого

Добавлена: 29.04.2026
Обновлена: 29.04.2026
Предмет: Геометрия
Автор: Кэмп

#Дискретная математика
#Теория оптимизации

№ 2 *{Серьги с бриллиантами} В ювелирную лавку пришла покупательница и заказала особенные серьги-пластины. Каждая серьга - это поле из клеток . В каждую клетку мастер может вставить бриллиант или оставить её пустой. Но есть прихоть заказчицы. Для каждого

Условие:

№ 2

\section*{Серьги с бриллиантами}

В ювелирную лавку пришла покупательница и заказала особенные серьги-пластины. Каждая серьга - это поле из клеток $7 \times 7$ . В каждую клетку мастер может вставить бриллиант или оставить её пустой.

Но есть прихоть заказчицы. Для каждого квадрата размера $3 \times 3$ , полностью входящего в поле $7 \times 7$ , должно выполняться условие: хотя бы половина клеток этого квадрата (то есть не меньше 5) занята бриллиантами. У ювелира очень много других заказов, поэтому он попросил вас о помощи. Расставьте минимально возможное количество бриллиантов так, чтобы условие заказчицы выполнялось. Чем меньше бриллиантов вы используете, тем больше баллов вы получите.

Решение:

Имеется поле 7×7 клеток. Любой квадрат 3×3, полностью содержащийся в нём, должен иметь не менее 5 заполненных бриллиантами клеток. Всего таких квадратов 5×5 =
25.
Если обозначить через x_ij индикатор того, что в клетке (i,j) стоит бриллиант, то условие для каждого 3×3 квадрата выглядит так: сумма x_ij по клеткам внутри квадрата должна быть ≥
5.
Просуммируем неравенства по всем 25 квадратам. При этом каждая клетка поля может входить в несколько 3×3 квадратов. Всего каждый такой квадрат содержит 9 клеток, значит суммарное «требование» получается...