Задача 35186

Темы:    [ Комбинаторика (прочее) ] [ Геометрия на клетчатой бумаге ]

Сложность: 3+ Классы:

Условие

Дана таблица размера 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-сайт

задача