Дана таблица размера 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.  
			
Комбинаторика (прочее) Геометрия на клетчатой бумаге