21-я Балканская математическая олимпиада среди юниоров. Кипр, 2019 год


Прямоугольная таблица размером $5 \times 100$ разделена на 500 единичных квадратиков, $n$ из которых покрашены в чёрный цвет, остальные — в белый. Два единичных квадратика называются соседними, если они имеют общую сторону. Каждый из единичных квадратиков в таблице имеет не более двух соседних чёрных единичных квадратиков. Найдите наибольшее возможное значение $n$.
посмотреть в олимпиаде

Комментарий/решение:

  4
2023-01-09 20:09:59.0 #

Ответ $302$

предположим что существует вариант с $303$ клетками или более, которые удовлетворяют условию. Мы будем считать сумму по всем клеткам количества черных клеток, прилегающих к каждой клетке, двумя способами. поскольку каждая клетка примыкает максимум к $2$ черным клеткам эта сумма составляет не более $500* 2 = 1000$поскольку есть как минимум $303$ черных квадратика, эта сумма составляет не менее $4*2 + 202*3 + 97* 4 = 1002$. Это явно противоречие, поэтому черных клеток не более $302$, Ч.Т.Д

  0
2023-06-01 17:43:06.0 #

У вас есть пример показывающий что это возможно?