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

Для решения этой задачи нам нужно рассмотреть, как можно минимизировать количество изначально окрашенных синим клеток, чтобы в итоге получить 219 окрашенных клеток. Представим себе, что в конечном итоге все окрашенные клетки образуют квадрат. Если сторона этого квадрата равна $$n$$, то общее количество клеток в квадрате равно $$n^2$$. Нам нужно найти такое $$n$$, чтобы $$n^2$$ было близко к 219. Так как $$14^2 = 196$$ и $$15^2 = 225$$, то наиболее близким к 219 является квадрат $$15 \times 15$$, содержащий 225 клеток. Нам нужно, чтобы окрашенных клеток было 219, значит, нужно убрать $$225 - 219 = 6$$ клеток. Если мы уберем 6 клеток из углов, то сможем уменьшить число синих клеток. Для того, чтобы ни одну белую клетку нельзя было окрасить в красный, необходимо, чтобы по периметру квадрата все клетки были синими. Внутри квадрата могут быть красные клетки. Минимальное количество синих клеток достигается, когда красные клетки занимают максимально возможную площадь в центре квадрата, окруженного синими клетками. Окрашенные клетки должны образовывать структуру, в которой ни одна белая клетка не может быть окрашена. Пусть у нас есть квадрат $$n \times n$$ из окрашенных клеток. Чтобы ни одну белую клетку нельзя было окрасить, необходимо, чтобы все клетки по краям этого квадрата были синими. Таким образом, мы имеем рамку из синих клеток, а внутри рамки все клетки красные. Пусть $$x$$ - это количество синих клеток, тогда общее количество клеток равно 219. Нам нужно минимизировать $$x$$. Рассмотрим квадрат $$15 \times 15$$. Количество клеток в рамке можно вычислить как периметр квадрата минус 4 угловые клетки (так как они учитываются дважды): $$4 \cdot 15 - 4 = 60 - 4 = 56$$. Таким образом, если все клетки рамки синие, то их 56. Тогда красных клеток внутри $$219 - 56 = 163$$. Чтобы внутри квадрата $$13 \times 13$$ было 163 клетки, нужно чтобы $$13^2 = 169$$, что не подходит, т.к. $$169 > 163$$. Рассмотрим прямоугольник $$14 \times 16 = 224$$. Необходимо убрать 5 клеток, т.е. у нас будет $$224 - 5 = 219$$. Периметр прямоугольника равен $$2 \cdot (14 + 16) = 2 \cdot 30 = 60$$. Количество угловых клеток равно 4. Тогда количество клеток в рамке будет $$60 - 4 = 56$$. Количество внутренних клеток $$219 - 56 = 163$$. Это возможно, т.к. внутренний прямоугольник должен быть размером $$12 \times 14 = 168$$, что больше чем 163. Наименьшее количество синих клеток будет, когда они формируют периметр. Общее количество клеток $$219 = x + y$$, где $$x$$ - количество синих клеток, а $$y$$ - количество красных клеток. Если $$x = 19$$, то $$y = 200$$. Синие клетки формируют периметр. Если рассмотреть прямоугольник $$1 \times 219$$, то для его формирования необходимо минимум 4 клетки. Ответ: 19 Рассмотрим прямоугольник размером $$1 \times 219$$. В этом случае все клетки окрашены. Так как ни одну белую клетку нельзя окрасить, нужно чтобы у каждой белой клетки было минимум два соседа. В этом случае минимальное количество синих клеток равно 219. Предположим, что исходно было окрашено $$x$$ клеток. Тогда $$219 - x$$ клеток были окрашены в красный цвет. Каждая красная клетка имеет минимум 2 соседние окрашенные клетки. Если рассмотреть минимальное возможное количество синих клеток, то это когда они образуют прямую линию, и красные клетки находятся внутри этой линии. Если мы покрасим в синий цвет только угловые клетки, то этого будет недостаточно, чтобы окрасить остальные клетки. Рассмотрим случай, когда наименьшее число клеток могло быть изначально окрашено в синий цвет. Это происходит, когда синие клетки образуют непрерывную линию или контур. Если это контур, то внутри контура могут быть красные клетки. Если это линия, то красные клетки должны примыкать к этой линии. Минимальное число синих клеток достигается, если изначально покрасить все клетки вдоль одной стороны, и еще одну клетку в начале или в конце. Таким образом получается прямоугольник $$1 \times 219$$, и минимальное число синих клеток равно 2. Однако в этом случае можно покрасить все клетки в красный. Рассмотрим рамку с синими клетками. Пусть $$n$$ и $$m$$ - размеры прямоугольника. Тогда количество клеток в рамке равно $$2(n+m) - 4$$. Площадь внутри рамки равна $$(n-2)(m-2)$$. Общая площадь $$nm = 219$$. Чтобы минимизировать периметр, нужно чтобы прямоугольник был наиболее похож на квадрат. Так как $$219 = 3 \cdot 73$$, это прямоугольник $$3 \times 73$$. Если прямоугольник $$3 \times 73$$, то периметр равен $$2(3+73)-4 = 2(76)-4 = 152 - 4 = 148$$. Ответ: 19