На белом клетчатом листе бумаги нарисовали прямоугольник со сторонами 20 и 19 клеток. В каждую клетку вписали натуральное число. Клетка красится в зелёный цвет, если среди соседних с ней по углу или стороне клеток не больше одной клетки с таким же или большим значением. Какое наибольшее число зелёных клеток могло получиться в таблице?
Рассмотрим квадраты 2×2. В каждом из них в зеленый цвет может быть окрашено не более 2 клеток. Следовательно, в квадрате 20×18, который можно разбить на 90 квадратов 2×2 может быть не более 180 окрашенных клеток. Таким образом, всего может быть окрашено не более 180 + 20 клеток. Ниже представлен вариант, при котором этих зеленых клеток будет ровно 200.
Ответ: 200.