Минимальное число клеток и условие уголка: олимпиадная задача по комбинаторной геометрии

Закрасив в квадрате все клетки 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 4b , и черных клеток не меньше, чем треть, что и требовалось.