|
|
 |
Условие
Клетки доски m×n покрашены в два цвета. Известно, что на какую бы клетку ни поставить ладью, она будет бить больше клеток не того цвета, на котором стоит (клетка под ладьей тоже считается побитой). Докажите, что на каждой вертикали и каждой горизонтали клеток обоих цветов поровну.
Решение 1
Впишем в каждую белую клетку число 1, а в каждую чёрную – (–1). Пусть bi – сумма чисел, стоящих в i-й строке, cj – сумма чисел, стоящих в j-м столбце, aij – число, стоящее на пересечении этих строки и столбца. Легко проверить, что условие эквивалентно выполнению неравенств aij(bi + cj) ≤ 0 при всех i и j. (Действительно, разность между количествами белых и чёрных клеток, которые бьёт ладья с клетки (i, j), равна bi + cj – aij. Если, например, aij = 1, то bi + cj – 1 < 0 ⇔ bi + cj ≤ 0 ⇔ aij(bi + cj) ≤ 0.)
Следовательно, .
Значит, все суммы bi и cj равны нулю.
Решение 2
Пусть на горизонтали Г белых клеток больше, чем чёрных. Отметим все вертикали, пересекающие Г по белой клетке. На каждой из них чёрных клеток больше половины. Допустим, на другой горизонтали Г' не менее половины клеток чёрные. Тогда какая-то отмеченная вертикаль пересекает Г' по чёрной клетке, и ладья с этой клетки побьёт больше чёрных. Противоречие. Значит, на всех горизонталях белых клеток больше, поэтому белых клеток больше и на всей доске.
Поставим теперь ладью на белую клетку. Больше чёрных она может побить только за счёт вертикали, то есть на этой вертикали чёрных клеток больше. Рассуждая, как выше, получаем, что и чёрных клеток на всей доске больше, чем белых. Противоречие.
Замечания
6 баллов
