Нахождение квадратов – 1
На этой сетке красным цветом обозначены два квадрата 1 на 1 и один квадрат 2 на 2 с горизонтальной и вертикальной сторонами.
CHALLENGE
Найдите количество квадратов всех размеров с горизонтальными и вертикальными сторонами в этой сетке.
РАЗВЕДКА
Поэкспериментируйте с сетками еще большего размера. Сможете ли вы найти систематический способ подсчета всех квадратов? Как изменится ваш ответ, если он вообще изменится, если сетка точек будет представлять собой прямоугольник, а не квадрат?
Заметки
CHALLENGE
Возможные квадраты имеют стороны длиной от 1 до 4.
Для каждого размера квадрата верхний левый угол считается начальной позицией. Вы можете создать все квадраты этого размера в сетке, перемещая этот начальный квадрат. Вы можете переместить его вправо или вниз на оставшееся количество позиций. Это независимые выборы, поэтому вы получаете квадрат такого размера квадрат.
Например, предположим, вы считаете квадраты 1х1 в этой сетке 4х4. Квадрат 1х1 в верхнем левом углу может быть сдвинут на 1 или 2 вправо и на 1 или 2 вниз. Таким образом, существует 3 возможных положения по горизонтали (считая исходное положение) и 3 возможных положения по вертикали. Следовательно, таких квадратов 1х1 всего 3х3.
Для исходной задачи с сеткой 4х4 это дает следующее количество:
- Квадраты 1х1: 3х3 = 9
- Квадраты 2х2: 2х2 = 4
- Квадраты 3х3: 1х1 = 1.
Всего существует 3 х 3 + 2 х 2 + 1 х 1 = 9 + 4 + 1 = 14 возможных квадратов.
РАЗВЕДКА
Для любой квадратной сетки общее количество квадратов будет равно сумме квадратов, меньших по размеру, чем размер сетки. Например, сетка 7 на 7 будет содержать 36 + 25 + 16 + 9 + 4 + 1 = 91 квадрат.
В случае прямоугольных сеток подсчет квадратов почти так же прост. Меньшее из двух измерений прямоугольника ограничивает максимальный размер возможных квадратов. Подсчет производится аналогично случаю квадратной сетки. Вместо общего случая, давайте рассмотрим лишь один иллюстративный пример.
Предположим, вы считаете квадраты в сетке 5 на 7. Поскольку рядов всего 5, ни один квадрат не может быть больше 4 на 4.
- Квадраты 1х1: 4х6 = 24
- Квадраты 2х2: 3х5 = 15
- Квадраты 3х3: 2х4 = 8
- Квадраты 4х4: 1х3 = 3
Общее количество квадратов равно 24 + 15 + 8 + 3 = 50.