Задача
Дана таблица размера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.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь