ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98506
Темы:    [ Шахматные доски и шахматные фигуры ]
[ Подсчет двумя способами ]
[ Доказательство от противного ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

Клетки доски 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 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2000/2001
Номер 22
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .