|
|
 |
Условие
Дана таблица размера m×n (m, n > 1). В ней отмечены центры всех клеток. Какое наибольшее число отмеченных центров можно выбрать так, чтобы никакие три из них не являлись вершинами прямоугольного треугольника?
Подсказка
Можно уменьшать таблицу, вычеркивая ряд, в котором
расположено более двух выбранных точек.
Решение
Выберем в таблице центры всех клеток нижней строки и правого столца, за исключением правой нижней угловой клетки. Всего выбрано m + n – 2 точки, и каждая тройка отмеченных точек образует тупоугольный треугольник.
Докажем, что больше m + n – 2 центров клеток выбрать нельзя. Для каждого отмеченного центра либо в его строке, либо в его столбце других отмеченных центров нет. Пометим этот ряд. Если помечены все строки, то выбрано всего не больше m ≤ m + n – 2 центров. Аналогична ситуация, когда помечены все столбцы.
Если же помечены не все строки и не все столбцы, то всего помеченных рядов (а значит, и отмеченных центров) не больше, чем
(m – 1) + (n – 1) = m + n – 2 .
.
Ответ
m + n – 2.
Источники и прецеденты использования
| web-сайт | |
| задача |
