Пусть $ p $ и $ q $ — натуральные числа, большие 1. Известно, что $ q^3-1 $ делится на $ p $, а $ p-1 $ делится на $ q $. Докажите, что $ p = q^{\frac{3}{2}}+1 $ или $ p = q^2 + q + 1 $.
Решение
Будем рассуждать так.
Имеем $ q^3 — 1 = pk $ для некоторого $ k \geqslant 1 $. Так как $ p = 1 \pmod {q}$, то $ k = -1 \pmod {q}$, т.е. $ k = lq-1$ для некоторого $ l \geqslant 1 $. Из равенства $ \displaystyle p = \frac{(q^3-1)}{(lq-1)}$ следует, что $ l < q^2 $, а также то, что числа $ q^2-l $ и $ q-l^2 $ делятся на $ lq-1 $. Предположим теперь, что $ p \neq q^{\frac{3}{2}} + 1$ (в частности, $ l \neq q^{1/2}$). Если $ 1 < l < q, l \neq q^{\frac{1}{2}} $, то $ 0 < \left|q-l^2\right| < lq-1 $ и, следовательно, делимость $ q-l^2 $ на $ lq-1 $ невозможна. Если же $ q \leqslant l < q^2$, то $ 0 < q^2-l < lq-1$ и невозможна делимость $ q^2-l$ на $ lq-1$. Таким образом, $ l = 1$ и $p = q^2 + q + 1 $. Этим всё доказано.
Выпуклый многогранник имеет шесть вершин — по одной на каждой из полуосей прямоугольной системы координат. Докажите, что восемь проекций начала координат на грани многогранника принадлежат одной сфере.
Решение
Пусть три вершины многогранника $X_{0}, Y_{0}$ и $Z_{0}$ лежат на отрицательных полуосях, а три другие вершины $X_{1}, Y_{1}$ и $Z_{1}$ на положительных полуосях, точка $O$ — начало координат. Четыре проекции точки $O$ лежат на гранях многогранника $Z_{1}X_{1}Y_{1}$, $Z_{1}Y_{1}X_{0}$, $Z_{1}X_{0}Y_{0}$ и c $Z_{1}Y_{0}X_{1}$ — это точки $A$, $B$, $C$ и $D$ соответственно. Так как $\angle Z_{1}AO =\angle Z_{1}CO = \angle Z_{1}DO =90^{\circ}$, то сфера $S$, построенная на $Z_{1}O$ как на диаметре, содержит точки $A$, $B$, $C$ и $D$. Докажем, что точки $A$, $B$, $C$ и $D$ принадлежат одной окружности, т.е. сечению сферы $S$. Спроектировав эти точки из точки $Z_{1}$ на ребра многогранника $X_{1}Y_{1}$, $Y_{1}X_{0}$ $X_{0}Y_{0}$ и $Y_{0}X_{1}$, получим точки $A_{1}$, $B_{1}$, $C_{1}$ и $D_{1}$, соответственно. Эта проекция — стереографическая, и как только мы докажем, что $A_{1}$, $B_{1}$, $C_{1}$ и $D_{1}$ принадлежат одной окружности, так сразу убедимся, что точки $A$, $B$, $C$ и $D$ тоже принадлежат одной окружности. Заметим, что точки $A_{1}$, $B_{1}$, $C_{1}$ и $D_{1}$ — это проекции точки $O$ на стороны четырехугольника $X_{1}Y_{1}X_{0}Y_{0}$ , диагонали которого $X_{1}X_{0}$ и $Y_{1}Y_{0}$ перпендикулярны и пересекаются в точке $O$ (см. рисунок). В треугольнике $X_{0}Y_{1}X_{1}$ отрезок $B_{1}A_{1}$ антипараллелен стороне $X_{0}X_{1}$, т.е. $\angle Y_{1}B_{1}A_{1} =\angle Y_{1}X_{1}X$, a $\angle Y_{1}A_{1}B_{1} = \angle Y_{1}X_{0}X_{1}$; аналогичные равенства углов получим в треугольниках $Y_{1}X_{0}Y_{0}$, $X_{0}Y_{0}X_{1}$ и $Y_{0}X_{1}Y_{1}$. После этого простой подсчет покажет, что суммы противоположных углов в четырехугольнике $A_{1}B_{1}C_{1}D_{1}$ равны по $180^{\circ}$, т.е. около $A_{1}B_{1}C_{1}D_{1}$ можно описать окружность. Значит, точки $A$ $B$, $C$ и $D$ принадлежат одной окружности, а четырехугольник $ABCD$является одной из шести граней многогранника $M$, восемь вершин которого — это восемь проекций точки $O$ на грани исходного многогранника. Все грани многогранника $M$ (кубоида) являются четырехугольниками, около каждого из которых можно описать окружность. Рассмотрим сферу $Q$, содержащую две окружности, описанные около двух смежных граней многогранника $M$. Нетрудно убедиться, что сфера $Q$ содержит все вершины многогранника $M$.
Пусть [latex]p_{n}\left(k\right)[/latex] — число перестановок множества из [latex] n (n \geq 1) [/latex] элементов, имеющих ровно $k$ неподвижных точек. Докажите, что:
Перестановкой конечного множества $S$ называется взаимно однозначное отображение $f$ множества $S$ на себя; число всех перестановок множества из $n$ элементов равно [latex] n! = 1 \cdot 2 \cdot \ldots \cdot n [/latex]
Доказательство
Заметим прежде всего, что $$\begin{equation}
\sum\limits_{k=0}^n p_{n}\left(k\right) = n!,
\end{equation}
$$ так как в левой части стоит суммарное число перестановок, имеющих $0,1,\ldots,n$ неподвижных точек, т.е. просто число всех перестановок. Теперь докажем, что при $1 \leqslant k \leqslant n$ $$\begin{equation}
k \cdot p_{n}\left(k\right) = n \cdot p_{n-1} \cdot \left(k-1\right),
\end{equation}
$$ считая, что $p_{0}\left(0\right) = 1 $. Для этого подсчитаем двумя способами число $N$ пар $\left(f,i\right)$, где $f$ — произвольная перестановка $n$ элементов с $k$ неподвижными точками, а $i$ — любая из этих точек $f\left(i\right)=i$. С одной стороны, каждая из этих $p_{n}\left(k\right)$ перестановок входит в $k$ пар, поэтому $N=k \cdot p_{n}\left(k\right)$. Суммируя равенства (2) по $k = 1,\ldots,n$ и учитывая (1) ( с заменой $n$ на $n-1$), получим $$\sum\limits_{k=0}^n k \cdot p_{n}\left(k\right) = n \cdot \sum\limits_{k=1}^n p_{n-1}\left(k-1\right) = n \cdot \left(n-1\right)! = n!$$
Докажем сразу более общее тождество $$\begin{equation}
s\left(n,m\right) = \sum\limits_{k=m}^n \frac {k!}{\left(k-m\right)!} \cdot p_{n}\left(k\right) = n!
\end{equation}$$ $n \gneq m$, $m = 0,1,2,…$ (по определению, $0!=1$). При $m=0$ оно совпадает с (1), при $m=1$ — с утверждением 1, а при $m=2$ эквивалентно 2, поскольку $$ \begin{multline*} \sum\limits_{k=0}^n \left(k-1\right)^2 \cdot p_{n}\left(k\right) = \sum\limits_{k=0}^n k \cdot \left(k-1\right) \cdot p_{n}\left(k\right) — \sum\limits_{k=0}^n k \cdot p_{n}\left(k\right)+{}\\{}+\sum\limits_{k=0}^n p_{n}\left(k\right) = s\left(n,2\right)-s\left(n,1\right)+s\left(n,0\right). \end{multline*} $$
Из тождества (2) следует, что при $1\le m\le n\le k$ $$ \begin{multline*} \frac {k!}{\left(k-m\right)!} \cdot p_{n}\left(k\right) = k \cdot \left(k-1\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n}\left(k\right) = {}\\ {}=n \cdot \left(k-1\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n-1}\left(k-1\right) = {}\\ {} = n \cdot \left(n-1\right) \cdot \left(k-2\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n-2}\left(k-2\right)= {}\\ {} = n \cdot \left(n-1\right) \cdot \ldots \cdot (n-m+1) \cdot p_{n-m}\left(k-m\right)= {}\\ {} = \frac {n!}{\left(n-m\right)!} \cdot p_{n-m}\left(k-m\right). \end{multline*} $$ Суммируем эти равенства по $k = 1,\ldots,n$: $$s\left(n,m\right)=\frac {n!}{\left(n-m\right)!} \cdot s\left(n-m,0\right) = n! $$
Другое доказательство $(3)$ можно получить из почти очевидного соотношения $p_{n}\left(k\right) = C^k_{n} \cdot p_{n-k}\left(0\right)$, где $C^k_{n} = \frac {n!}{k! \left(n-k\right)!}$ — число $k$ -элементных подмножеств множества из $n$ элементов (число сочетаний).
На сторонах $AB$, $BC$ и $CA$ треугольника $ABC$ как на основаниях вне его построены треугольники $ABC_{1}$, $BCA_{1}$, $CAB_{1}$, у каждого из которых отношение высоты к основанию равно $k$. Такие же треугольники $ABC_{2}$, $BCA_{2}$ и $CAB_{2}$ построены и по другую (внутреннюю) сторону от оснований. Докажите, что площади $S$, $S_{1}$ и $S_{2}$ треугольников $ABC$, $A_{1}B_{1}C_{1}$ и $A_{2}B_{2}C_{2}$ связаны соотношением $$S_{1} \pm S_{2} = S \cdot \left(\frac12 + 6k^2\right) $$ (знак «$+$» или «$-$» зависит от ориентации треугольника $A_{2}B_{2}C_{2}$ по отношению к $ABC$).
Доказательство
Вершины треугольников с площадями $S_{1}$ и $S_{2}$ лежат на серединных перпендикулярах к сторонам треугольника $ABC$, проходящих через центр $O$ его описанной окружности. Если обозначить через $R$ радиус этой окружности, а через $\alpha$, $\beta$, $\gamma$ — углы треугольника $ABC$, то из рис.1 видно, что, поскольку синусы углов между перпендикулярами равны синусам углов между соответствующими сторонами, то $$ 2S_{1} = OA_{1} \cdot OB_{1} \cdot \sin \gamma + OB_{1} \cdot OC_{1} \cdot \sin \alpha + OC_{1} \cdot OA_{1} \cdot \sin \beta . $$ рис.1
Пусть $t$ — тангенс угла наклона стороны равнобедренного треугольника к основанию $(t = 2 \cdot k)$. Тогда отрезки от $O$ до вершин легко выразить через радиус $R$ и получить, что $$\begin{multline} \frac{2S_1}{R^2} = \left(\cos \alpha + t \sin \alpha \right) \cdot \left( \cos \beta + t \sin \beta \right) \cdot \sin \gamma + {} \\\\ {} + \left( \cos \beta+ t \sin \beta \right) \cdot \left( \cos \gamma+ t \sin \gamma \right) \cdot \sin \alpha + {} \\\\ {} + \left(\cos \gamma+ t \sin \gamma \right) \cdot \left( \cos \alpha+ t \sin \alpha \right) \cdot \sin \beta.\end{multline}$$
Отношение же $\frac{ 2S_{2} }{R^2}$ (для случая, изображенного на рис.1) равно аналогичному выражению, где вместо $t$ стоит $-t$. Сложив оба эти выражения и раскрыв скобки, мы увидим, что коэффициент при $t^1$ равен $0$, коэффициент при $t^2$ равен $6 \cdot \sin \alpha \cdot \sin \beta \cdot \sin \gamma$, а свободный член (здесь нужно использовать равенство $\alpha + \beta + \gamma = \pi$, откуда $ \cot \alpha \cdot \cot \beta + \cot \beta \cdot \cot \gamma + \cot \alpha \cdot \cot \gamma = 1$) равен $2 \cdot \sin \alpha \cdot \sin \beta \cdot \sin \gamma$. По известной формуле $S = \frac{abc}{4R}$, выражающей площадь $S$ через стороны $a$, $b$, $c$ и радиус описанной окружности $R$, $$2 \cdot \sin \alpha \cdot \sin \beta \cdot \sin \gamma = 2\frac{abc}{8R^3} = \frac{S}{R^2}$$
Откуда получаем нужную формулу $$\begin{equation} S_{1} + S_{2} = \frac{1+3t^2}{2} S = S \cdot \left(\frac12 + 6k^2\right) \end{equation} $$.
Эти рассуждения необходимо несколько уточнить, чтобы они оказались применимы не только для случая, изображенного на рис.1, но и для случая, когда внутренние треугольники налегают друг на друга, в частности, когда $A_{2}B_{2}C_{2}$ имеет противоположную ориентацию. Вместо этого мы посмотрим на наши рассуждения с более общей точки зрения.
Верен такой общий факт: если три точки $K$, $L$ и $M$ с постоянными скоростями движутся по трем прямым, то площадь ориентированного треугольника $KLM$ как функция,зависящая от времени $t$, выражается квадратным трехчленом от $t:S = F\left(t\right)$. Легко доказать это, например, с помощью метода координат (формула ориентированной площади треугольника с вершинами $\left(x_1, y_1\right)$, $\left(x_2, y_2\right)$, $\left(x_3, y_3\right)$ выглядит так: $$ S = \frac{x_1 y_2 — x_2 y_1 + x_2 y_3 — x_1 y_2 + x_3 y_1 — x_1 y_3}{2}.$$ Ясно, что если каждая координата выражается линейной функцией от $t$, то $S$ — квадратный трёхчлен от $t$).
Будем считать, что при $t=0$ наши точки совпадают с серединами сторон треугольника $ABC$ и двигаются по серединным перпендикулярам (при $t>0$ во внешнюю сторону) со скоростями, пропорциональными длинам $a$, $b$, $c$ соответствующих сторон треугольника: при некотором $t$ они занимают положения $A_{1}$, $B_{1}$, $C_{1}$, а при противоположном значении $\left(-t\right)$ — положения $A_{2}$, $B_{2}$, $C_{2}$. Нас интересует сумма $F\left(t\right)+F\left(-t\right)$, то есть свободный и старший (содержащий $t^2$) члены $F\left(t\right)$, которые по сущетсув мы и вычисляли выше (1).
Интересно заметить, однако, что они имеют геометрический смысл, так что можно найти их без вычислений. Свободный член $F\left(0\right)$ — это $\frac{S}{4}$ (площадь треугольника из средних линий $ABC$). Чтобы найти старший коэффициент, — он определяется как отношение площади $S_{1}$ к $t^2$ в пределе при $t$ стремящемся к бесконечности, — заметим, что при очень большом $t$ треугольник $ABC$ можно считать «почти точкой» $O$. При этом векторы $OA_{1}$, $OB_{1}$, $OC_{1}$ перпендикулярны соответствующим сторонам треугольника и им пропорциональны ( с коэффициентом $k=\frac{t}{2}$ ). Сумма этих векторов $OA_{1}$, $OB_{1}$ и $OC_{1}$ равна нулю (как и векторов, образующих стороны треугольника), то есть они служат отрезками медиан треугольника $A_{1}B_{1}C_{1}$, причем последний по площади в 3 раза больше треугольника $A_{1}OD$ (рис.2), подобного $ABC$ с коэффициентом $k$. Отсюда ясно, что старший член $F\left(t\right)$ имеет вид $3 k^2 \cdot S = 3 \frac{t^2 \cdot S}{4}$. рис.2
Итак, $F\left(t\right) = \frac {S \left(1+ \ldots +3 t^2\right)}{4}$, откуда следует нужная формула (2) для $S_1 \pm S_2 = F\left(t\right)+F\left(-t\right)$.
Отметим интересные частные случаи нашей формулы: если на сторонах строятся правильные треугольники, то $t = \sqrt{3}$, так что $S_1 \pm S_2 = 5S$; если равнобедренные прямогульные, то $-t = 1$ и $S_1 \pm S_2 = 2S$; а если $t = \frac{\sqrt{3}}{6}$ (при этом новые точки — центры правильных треугольников, построенных на сторонах), то $S_1 \pm S_2 = S$.
Восемь клеток одной диагонали шахматной доски назовем забором. Ладья ходит по доске, не наступая на одну и туже клетку дважды и не наступая на клетки забора[latex]([/latex]промежуточные клетки не считаются посещенными[latex])[/latex]. Какое наибольшее число прыжков через забор может совершить ладья?
Ответ: 47 прыжков.
Решение
рис.1
Разделим доску на четыре квадрата [latex]4\times4[/latex]. Заметим, что если ладья прыгает через забор, то либо начальная, либо конечная клетка прыжка закрашена цветом [latex]-[/latex] голубым или розовым [latex]-[/latex] на рисунке [latex]1[/latex]. Так как закрашенных клеток [latex]24[/latex] и через каждую может проходить максимум два прыжка, то всего может оказаться не более [latex]48[/latex] прыжков. При этом, если их ровно 48, то из каждой закрашенной клетки должно быть сделано два прыжка в не закрашенные клетки[latex]([/latex] в предыдущем подсчете прыжок из закрашенной в закрашенную будет подсчитан два раза![latex])[/latex]. Тогда все ходы из голубых клеток будут вести в белый квадрат под диагональю, а оттуда [latex]-[/latex] только в голубые клетки[latex]([/latex] либо в другие клетки этого же квадрата [latex])[/latex]. Значит подобным образом ладья никогда не попадет в розовые клетки. Противоречие. Таким образом, количество прыжков не превосходит [latex]47[/latex].
Один из возможных примеров с [latex]47[/latex] прыжками показан на рисунке [latex]2([/latex] числа в клетках указывают, в каком порядке ладья по ним ходит[latex])[/latex].
