Комбинаторика, теорвер и теория чисел на Физтехе

Посчитаем число отрезков, на которые разбили квадрат: тогда число точек равно

Если фиксируем две точки на одной стороне квадрата, то две другие точки будут лежать на противоположной стороне, и прямоугольник будет определяться однозначно.

Рассмотрим случай, когда фиксируются две точки на соседних сторонах. Определим, когда в этом случае образуется прямоугольник:

Пусть сторона прямоугольника образует с квадратом угол Тогда получаем четыре подобных прямоугольных треугольника с гипотенузами, являющимися сторонами прямоугольника, причём противоположные треугольники равны. Их острые углы равны и

Обозначим катеты одного из треугольников за и Тогда треугольники подобны с коэффициентом

Рассмотрим два соседних треугольника. Если у одного из них катет равен то у другого катет равен

Из подобия найдём вторую сторону:

Из равенства противоположных треугольников получаем уравнение:

Откуда:

Следовательно, либо либо

Теперь посчитаем все случаи:

1. Если фиксируем две точки на одной стороне, то точки можно выбрать на вертикальной и горизонтальной сторонах квадрата. При этом сам квадрат мы посчитали дважды. Общее количество таких прямоугольников:

2. Если фиксируем точки на соседних сторонах квадрата, первую точку (без учёта вершин квадрата) можно выбрать способами. Тогда вторую точку можно выбрать двумя способами: либо либо Учтём также, что случай был посчитан дважды:

Сложив оба случая, получаем: