2022-10-26
$8n - 4$ точек расположены в виде креста (рис. для $n = 4$). Сколькими способами можно выбрать из этих точек четыре, являющиеся вершинами квадрата?
Решение:
Докажем индукцией по $n$, что искомое число равно $10n-9$. При $n = 1$, очевидно, можно получить $1 = 10 \cdot 1 - 9$ квадрат. Нетрудно убедиться, что при $n = 2$ можно выбрать $11 = 10 \cdot 2 - 9$ квадратов. Пусть утверждение верно для $n = k$, где $k \geq 2$. Рассмотрим фигуру, состоящую из $8(k + 1) - 4$ точек (рис. для $k = 3$). По предположению индукции можно выбрать ровно $10k-9$ квадратов, ни одна из вершин которых не совпадает с точками $A, B, \cdots , H$. Рассмотрим теперь квадраты, одна из вершин которых совпадает с точкой $A$. Нетрудно заметить, что найдутся лишь 3 таких квадрата: $ABB_{1}A_{1}, ACEG, AC_{1}F_{1}H$. Таким образом, существует ровно 10 4 квадратов, по крайней мере одна из вершин которых совпадает с одной из точек $A, B, \cdots, H$: 4 квадрата, конгруэнтных 4 квадрата, конгруэнтных $AC_{1}F_{1}H$,
и квадраты $ACEF, BDFH$. Всего имеем $10k - 9 + 10 = 10 (k + 1) - 9$ квадратов.