Задача 79384

Темы:    [ Целочисленные решетки (прочее) ] [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]

Сложность: 3+ Классы: 8,9,10

Условие

На прямоугольном листе клетчатой бумаги размером m×n клеток расположено несколько квадратов, стороны которых идут по вертикальным и горизонтальным линиям бумаги. Известно, что никакие два квадрата не совпадают и никакой квадрат не содержит внутри себя другой квадрат. Каково наибольшее число таких квадратов?

Решение

Отметим для каждого квадрата левый верхний угол. По условию для разных квадратов отмеченные точки разные. Поэтому число квадратов не превосходит mn. Ясно также, что mn клеток обладают требуемым свойством, поэтому число квадратов может быть равно mn.

Ответ

mn квадратов.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	43
Год	1980
вариант
Класс	9
задача
Номер	3