Задача 110206
|
|
 |
Условие
Какое минимальное количество клеток можно закрасить черным в белом квадрате 300×300, чтобы никакие три черные клетки не образовывали уголок, а после закрашивания любой белой клетки это условие нарушалось?Решение
Закрасив в квадрате все клетки 2-й, 5-й, 8-й, 299-й горизонталей в черный цвет, получим требуемый пример. Осталось показать, что меньшим количеством закрашенных клеток не обойтись.Пусть раскраска, в которой есть b черных и w белых клеток, удовлетворяет условию задачи.
Запишем в каждую черную клетку ноль. Затем для каждой белой клетки выполним такую операцию.
Если после ее закрашивания она становится центральной клеткой черного уголка, то прибавим к обеим остальным клеткам этого уголка по 1. В противном случае прибавим 2 к центральной клетке полученного уголка.
В обоих случаях, если получилось несколько уголков, то мы выполняем указанную операцию лишь с одним из них. Тогда сумма всех чисел в черных клетках равна 2w.
Покажем,что в произвольной черной клетке A стоит число, не большее 4.
Если у нее нет черных соседей, то после перекрашивания любого белого соседа A не может стать центральной клеткой уголка, поэтому каждый сосед добавил в нее не более 1. Если у A не более двух белых соседей, то каждый из них добавил не более 2. Поэтому больше 4 в ней может добавиться только в том случае, если у нее 1 черный и 3 белых соседа (см. рис.).
Клетка C не могла добавить в A двойку, так как тогда одна из клеток X или Z была бы черной. Если C добавила в A единицу, то одна из клеток Y и T черная – пусть это Y .
Тогда после закрашивания X она (клетка X ) становится центральной клеткой уголка, и поэтому также добавляет не более 1, а Z – не более 2. Если же C ничего в A не добавляет,то в A опять же не больше 4, полученных из клеток X и Z.
Итого, в каждой черной клетке записано не более 4, поэтому сумма всех чисел не больше 4b , т.е. 2w
