Показать скрытый текст
Пусть раскраска, в которой есть 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 , и черных клеток не меньше, чем треть, что и требовалось.
Записан