Anton tex project

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}

\usepackage[a5paper,margin=1cm,bmargin=1.5cm]{geometry}
\usepackage{parskip}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{asymptote}
\theoremstyle{definition}
\newtheorem{problem}{}

\newenvironment{answer}{\par\emph{Ответ:}}{\par}

\newenvironment{solution}[1][Решение.]
    {\vspace{-\parskip}\begin{proof}[#1]}{\end{proof}}

\title{Спецкурс <<Набор математических текстов в~\LaTeX>>}
\author{Антон Садовничий}
\date{20--23 июня 2020 г.}

\newcommand*{\hm}[1]{#1\nobreak\discretionary{}%
    {\hbox{$\mathsurround=0pt #1$}}{}}

\begin{document}
\maketitle

\section*{Задачи}
\begin{problem}
Для любых конечных множеств $X, Y \in \mathbb{N}$ определим $f_X(k)$ как $k$-е наименьшее натуральное число, не лежащее в $X$. Пусть
\[
X * Y = X \cup \{ f_X(y) : y \in Y \} \,.
\]
Пусть $A$~--- множество из $a > 0$ натуральных чисел, а $B$~--- множество из $b > 0$ натуральных чисел. Предположим, что $A * B = B * A$. Докажите, что
\[
\underbrace{A * (A * \ldots (A * (A * A)) \ldots )}_{\text{$b$ раз по $A$}} =
\underbrace{B * (B * \ldots (B * (B * B)) \ldots )}_{\text{$a$ раз по $B$}}.
\]
a) Докажите, что операция $*$ ассоциативная.

b) Докажите, что если $|X| = |Y|$ и $X * Y = Y * X$, то $X = Y$\!.

c) Завершите решение задачи.
\end{problem}
\medskip
\begin{solution}
~\par
a) Рассмотрим конечные множества $A, B, C \in \mathbb{N}$. Докажем, что $A * (B * C) \hm{=} (A * B) * C$. Введём последовательности $\{a_n\}$ и $\{b_n\}$, такие что $a_i = f_A(i)$, $b_i = f_B(i)$ для всех $i \geqslant 1$. Тогда
\[
\begin{aligned}
A * (B * C) & = A * (\{ x \mid x \in B\} \sqcup
\{x \mid x = b_i, i \in C \}) =
\\
& = \{ x \mid x \in A\} \sqcup
\{ x \mid x = a_i, i \in B\} \sqcup
\{ x \mid x = a_{b_i}, i \in C\},
\\
(A * B) * C & = (\{ x \mid x \in A\} \sqcup
\{ x \mid x = a_i, i \in B \}) * C =
\\
& = \{ x \mid x \in A\} \sqcup
\{ x \mid x = a_i, i \in B\} \sqcup
\{ x \mid x = a_{b_i}, i \in C\}.
\end{aligned}
\]

b) Обозначим $n = |X|$. Докажем утверждение индукцией по $n$. База индукции при $n = 0$ очевидна. Переход индукции: не умаляя общности, наибольший элемент в $Y$ не менее наибольшего элемента в $X$. Обозначим этот элемент $t$. Тогда $\max{(X * Y)} = n + t$. При этом $\max{(Y * X)} \leqslant
\max{\{n + \max{X},\, t\}}$. Так как $X * Y = Y * X$, то $\max{X} = t$. Рассмотрим множества $X' = X \backslash \{t\}, Y' = Y \backslash \{t\}$. Понятно, что
\[
X' * Y' = Y' * X' = \{x \mid x \in X * Y, \, x < t\} \sqcup \{x-1 \mid x \in X * Y, \, t < x < t + n \}.
\]
По предположению индукции $X' = Y'$, поэтому $X = Y$. Утверждение доказано.

c) Обозначим
\[
\left\{
\begin{aligned}
& X = \underbrace{A * (A * \ldots (A * (A * A)) \ldots )}_{\text{$b$ раз по $A$}}\,,
\\
& Y = \underbrace{B * (B * \ldots (B * (B * B)) \ldots )}_{\text{$a$ раз по $B$}}.
\end{aligned}
\right.
\]
Так как операция $*$ ассоциативная, и $A * B = B * A$, то эта операция также является коммутативной, когда все <<множители>>~--- это множества $A$ и $B$, поэтому $X * Y = Y * X$. Так как $|X| = |Y| = a b$, то $X = Y$ по предыдущему пункту.
\end{solution}
\bigskip
\begin{problem}
\label{problem:geo}
Многоугольник $P_1 P_2 {\ldots} P_{100}$ вписан в окружность. Будем считать, что $P_i \hm{=} P_{i + 100}$. Обозначим за $Q_i$ точку пересечения диагоналей $P_{i - 2} P_{i + 1}$ и $P_{i - 1} P_{i + 2}$.

Предположим, что для некоторой точки $P$ и всех $i$ выполнено $P P_i \perp P_{i - 1} P_{i + 1}$. Докажите, что точки $Q_1, Q_2, \ldots, Q_{100}$ лежат на одной окружности.

a) Обозначим за $K_i$ точку пересечения $P P_i$ и $P_{i-1} P_{i+1}$. Докажите, что точки $K_i$ лежат на одной окружности.

b) Обозначим окружность из пункта а) за $\gamma$. Докажите, что если $P_{i-1} P_{i+1}$ пересекают $\gamma$ вторично в точках $E_i$, то перпендикуляры к $P_{i-1} P_{i+1}$, восстановленные в $E_i$, пересекаются в одной точке.

c) Докажите, что через эту же точку проходят все прямые $E_i Q_i$.

d) Завершите решение задачи.
\end{problem}
\begin{figure}[ht]\centering
\begin{asy}[width=1\linewidth]
import geometry;

real mr = 0.5cm; // mark radius

point p1 = dir(200);
point p2 = dir(170);
point p3 = dir(130);
point p4 = dir(85);

line lP2 = perpendicular(p2, line(p1, p3));
line lP3 = perpendicular(p3, line(p2, p4));
point pP = intersectionpoint(lP2, lP3);
point p5 = reflect(parallel((0, 0), line(p4, pP))) * p3;
point p6 = reflect(parallel((0, 0), line(p5, pP))) * p4;
point k1 = extension(p2, pP, p1, p3);
point k2 = extension(p3, pP, p2, p4);
point k3 = extension(p4, pP, p3, p5);
point k4 = extension(p5, pP, p4, p6);
point h1 = extension(p1, p3, p2, p4);
point h2 = extension(p2, p4, p3, p5);
point h3 = extension(p3, p5, p4, p6);
circle cK = circumcircle(k1, k2, k3);
point pO = cK.C;
point pPp = pO + pO - pP;
point q1 = extension(p1, p4, p2, p5);
point q2 = extension(p2, p5, p3, p6);

point e1 = reflect(parallel(pO, line(pP, p2))) * k1;
point e2 = reflect(parallel(pO, line(pP, p3))) * k2;
point e3 = reflect(parallel(pO, line(pP, p4))) * k3;
point e4 = reflect(parallel(pO, line(pP, p5))) * k4;


draw(circumcircle(e2, e3, q1), green);
draw(p1--p4 ^^ p2--p5 ^^ p3--p6, gray(0.9) + dashed);
draw(pPp--e1 ^^ pPp--e2 ^^ pPp--e3 ^^ pPp--e4, dashed + gray(0.5));
draw(p2--p3 ^^ p3--p4 ^^ p4--p5, gray(0.5));
clipdraw(cK, blue + dashed);
clipdraw(circumcircle(p1, p2, p3));
draw(p1--p3 ^^ p2--p4 ^^ p3--p5 ^^ p4--p6);
draw(p2--pP ^^ p3--pP ^^ p4--pP ^^ p5--pP);

perpendicularmark(line(p2, pP), line(p1, p3), quarter=4, size=0.4mr);
perpendicularmark(line(p3, pP), line(p2, p4), quarter=1, size=0.4mr);
perpendicularmark(line(p4, pP), line(p3, p5), quarter=4, size=0.4mr);
perpendicularmark(line(p5, pP), line(p4, p6), quarter=1, size=0.4mr);

void edot(Label L, point pX, align align, pen p=defaultpen)
    { dot(L, pX, align, p, Fill(white)); }

edot("$P_{i-2}$", p1, SW);
edot("$P_{i-1}$", p2, W);
edot("$P_i$", p3, NW);
edot("$P_{i+1}$", p4, N);
edot("$P_{i+2}$", p5, NE);
edot("$P_{i+3}$", p6, E);

edot("$P$", pP, E);
edot("$P'$", pPp, E);
edot("$Q_i$", q1, 1.4S);
edot("$Q_{i+1}$", q2, 1.3dir(-53));
edot("$E_{i-1}$", e1, dir(130));
edot("$E_i$", e2, NW);
edot("$E_{i+1}$", e3, NE);
edot("$E_{i+2}$", e4, E);
dot("$O$", pO, p = blue, E, Fill(white));
edot("$K_{i-1}$", k1, dir(20));
edot("$K_i$", k2, 1.6N);
edot("$K_{i+1}$", k3, NW);
edot("$K_{i+2}$", k4, E);
edot("$H_{i-1}$", h1, 3E);
edot("$H_i$", h2, dir(110));
edot("$H_{i+1}$", h3, NE);
\end{asy}
\caption{к~задаче~\ref{problem:geo}}
\label{problem:geo:fig}
\end{figure}
\medskip
\begin{solution}
~\par
a) Заметим, что $P_i K_i K_{i+1} P_{i+1}$~--- вписанные четырёхугольники для всех $i$. Рассмотрим инверсию (или композицию инверсии и центральной симметрии) с центром в точке $P$, которая меняет местами точки $P_1$ и $K_1$. Тогда эта инверсия также меняет местами точки $P_2$ и $K_2$, \ldots, $P_{100}$ и $K_{100}$. Так как все точки $P_i$ лежат на одной окружности, то все точки $K_i$ тоже лежат на одной окружности. Обозначим эту окружность за $\gamma$, а её центр за $O$.

b) Пусть $P'$~--- отражение точки $P$ относительно точки $O$. Докажем, что перпендикуляры к $P_{i-1} P_{i+1}$, восстановленные из $E_i$, проходят через $P'$. Действительно, перпендикуляр из $P$ на $P_{i-1} P_{i+1}$ падает на $K_i$, из $O$~--- на середину отрезка $K_i E_i$, и из $P'$, соответственно, на $E_i$.

c) Обозначим $H_i = P_{i-1} P_{i+1} \cap P_i P_{i+2}$. Тогда $H_i$~--- ортоцентр треугольника $P P_i P_{i+1}$. Заметим, что относительно пары прямых $P_{i-1} P_{i+1}$ и $P_i P_{i+2}$ антипараллельны прямые $P_i P_{i+1}$ и $K_i K_{i+1}$, $P_i P_{i+1}$ и $P_{i-1} P_{i+2}$, $K_i K_{i+1}$ и $E_i E_{i+1}$. Получаем, что $P_i P_{i+1} \parallel E_i E_{i+1}$, $K_i K_{i+1} \parallel P_{i-1} P_{i+2}$ и $P_{i-1} E_i E_{i+1} P_{i+2}$~--- вписанный четырёхугольник. Так как $H_i P \perp P_i P_{i+1} \parallel E_i E_{i+1}$, то $H_i P' \perp K_i K_{i+1} \parallel P_{i-1} P_{i+2}$. Также $P_{i-1} P_{i+1} \parallel E_{i-1} E_{i+1}$, т.\,к. $K_{i-1} K_{i+1}$ и $E_{i-1} E_{i+1}$ антипараллельны относительно $P_{i-2} P_i$ и $P_i P_{i+2}$, а $K_{i-1} K_{i+1}$ и $P_{i-1} P_{i+1}$~--- относительно $P P_{i-1}$ и $P P_{i+1}$, где $P P_{i-1} \perp P_{i-2} P_i, P P_{i+1} \perp P_i P_{i+2}$. Получаем, что
\[
\frac{E_i H_{i-1}}{P_{i-1} H_{i-1}} = \frac{E_{i-1} H_{i-1}}{P_i H_{i-1}} = \frac{E_{i+1} H_i}{P_i H_i} = \frac{E_i H_i}{P_{i+1} H_i}.
\]
Значит, существует гомотетия с центром в $E_i$, которая переводит $H_{i-1}$ в $P_{i-1}$ и $H_i$ в $P_{i+1}$. Тогда эта гомотетия переводит треугольник $H_{i-1} H_i P'$ в треугольник, ортоцентр которого совпадает с $Q_i$ и лежит при этом на прямой $E_i P'$, т.\,к. $P' H_{i-1} \perp P_{i-2} P_{i+1}$ и $P' H_i \perp P_{i-1} P_{i+2}$, то есть $Q_i \in P' E_i$.

d) Докажем, что $E_i Q_i Q_{i+1} E_{i+1}$~--- вписанный. Так как $P_{i-1} E_i E_{i+1} P_{i+2}$ вписанный, то прямые $E_i E_{i+1}$ и $P_{i-1} P_{i+2}$ антисимметричны относительны пары прямых $P_{i-1} P_{i+1}$ и $P_i P_{i+2}$. Тогда они антисимметричны и относительно пары прямых $P' E_i$ и $P' E_{i+1}$, так как $P_{i-1} P_{i+1} \perp P' E_i$ и $P_i P_{i+2} \perp P' E_{i+1}$, поэтому $E_i,Q_i,Q_{i+1},E_{i+1}$ концикличны. Значит, аналогично пункту a) существует инверсия (возможно с центральной симметрией) с центром в точке $P'$, которая меняет местами точки $E_i$ и $Q_i$, поэтому точки $Q_i$ лежат на одной окружности.
\end{solution}
\bigskip
\begin{problem}
В одной из вершин правильного $n$-угольника записана единица, а в остальных~--- нули. Хулиган Миша одновременно прибавил к числу в каждой вершине его соседа по часовой стрелке; затем он прибавил к числу в каждой вершине число, стоящее от него через две вершины по часовой стрелке и т.\,д.; наконец, он прибавил к числу в каждой вершине его соседа против часовой стрелки. После этих операций $n-1$ из записанных чисел оказались равны. Чему могло быть равно число $n$?

a) Докажите, что если после всех операций все $n$ чисел оказались равны, то $n$~--- это степень двойки.

b) Проделаем с числами дополнительно ещё одну операцию: прибавим к каждому числу его самого. От этого количество равных чисел не изменится. Занумеруем вершины многоугольника числами от $0$ до $n-1$. Сопоставим числам в вершинах многоугольника многочлен $f(t) = a_{n-1} t^{n-1} + a_{n-2} t^{n-2} + \ldots + a_1 t + a_0$, где $a_k$~--- число, стоящее в вершине с номером $k$. Докажите, что многочлен, соответствующий финальной расстановке, сравним с многочленом $P(t) = (1 \hm{+} t)(1+t^2)(1+t^3)\cdots(1+t^n)$ по модулю $R(t) = t^{n-1} + \ldots + t + 1$.

c) Пусть $n$ чётно. Докажите, что если в финальной расстановке $n-1$ чисел равны, то в ней все $n$ чисел равны. Тем самым из пункта a) получаем, что если чётное $n$ подходит, то $n$ является степенью двойки.

d) Пусть $n$~--- степень двойки. Докажите, что тогда все числа в финальной расстановке равны. Тем самым, все степени двойки подходят.

e) Пусть $n$~--- простое нечётное число. Докажите, что оно подходит.

f) Наконец, докажите, что нечётные составные $n$ не подходят.
\end{problem}
\medskip
\begin{answer}
$n$~--- натуральная степень двойки или нечетное простое число.
\end{answer}
\begin{solution}
~\par
a) Заметим, что после каждой операции сумма чисел в вершинах удваивается. Таким образом, после всех операций сумма чисел равна $2^{n-1}$. Так как все числа равны, то $n \mid 2^{n-1}$ и $n$~--- степень двойки.

b) Докажем, что $f(t) \equiv P(t) \pmod{t^n - 1}$. Так как $R(t) \mid t^n - 1$, этого достаточно. Пусть после $k-1$ операции числа в вершинах равны $b_0,b_1,\ldots,b_{n-1}$. Тогда после $k$-й операции они станут равны $b_0+b_{-k},b_1+b_{-k+1},\ldots,b_{n-1}+b_{n-k-1}$, где индексы берутся по модулю $n$. Понятно, что $(b_{n-1}t^{n-1}+\ldots+b_1+b_0) (1+t^k) \hm{\equiv} (b_{n-1} \hm{+} b_{n-k-1})t^{n-1}+\ldots+(b_1+b_{-k+1})t+(b_0+b_{-k}) \pmod{t^n-1}$. С учётом того, что изначальный многочлен равен $1$, финальный сравним с $(1+t)(1+t^2)\ldots(1+t^n)$ по модулю ${t^n-1}$.

c) Предположим, что в финальной расстановке ровно $n-1$ чисел равны. Обозначим за $k$ номер отличающегося от остальных числа, которое на $s$ больше, чем остальные ($s$ может быть отрицательным). Тогда $f(t) - s t^k$ делится на $R(t)$, так как все его коэффициенты равны. По предыдущему пункту получаем, что $P(t) - s t^k$ тоже делится на $R(t)$. При этом для чётного $n$ у многочленов $P(t)$ и $R(t)$ есть общий корень $-1$, поэтому $s t^k$ должно делиться на $t+1$, что невозможно при ненулевом $s$. Значит, все $n$ чисел равны и $n$~--- степень двойки.

d) Пусть $n = 2^k$. Покажем, что $P(t)$ делится на $R(t)$. Рассмотрим $\varepsilon$~--- корень $R(t)$. Понятно, что $\varepsilon^n=1$. Обозначим за $2^i$ наименьшую степень, в которой $\varepsilon$ дает $1$. Так как $1$ не является корнем $R(t)$, $i > 0$, поэтому $\varepsilon$~--- корень $1 + t^{2^{i-1}}$, то есть корень $P(t)$. Получаем, что любой корень $R(t)$ является корнем $P(t)$, поэтому $P(t)$ делится на $R(t)$ и все числа после $n$ операций равны.

e) Обозначим за $\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n$ корни $n$-ой степени из единицы, где $\varepsilon_1$~--- корень с наименьшим аргументом из них и $\varepsilon_i = \varepsilon_1^i$ для всех $i$. Докажем, что $P(t) \equiv 2 \pmod{R(x)}$. Подставим в $P(t)$ $\varepsilon_i$ для $1\leqslant i \leqslant n-1$:
\[
P(\varepsilon_i) = (1+\varepsilon_i)(1+\varepsilon_i^2)\cdots(1+\varepsilon_i^n) =
(1+\varepsilon_1)(1+\varepsilon_2)\cdots(1+\varepsilon_n)=2 \,,
\]
так как $n$~--- простое, и все симметрические многочлены от $\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n$, кроме произведения, равны нулю, как коэффициенты многочлена $t^n-1$. Получаем, что $P(t)$ сравним с $2$ по модулю всех взаимно простых многочленов $t-\varepsilon_1, t \hm{-} \varepsilon_2,\ldots,t-\varepsilon_{n-1}$, и, соответственно, сравним с $2$ по модулю их произведения, равного $R(t)$. Значит, для простых нечётных $n$ после всех операций будут равны все числа, кроме одного, которое больше остальных на 2.

f) Предположим, что для нечётного составного $n$ после всех операций будут равны $n-1$ чисел. Обозначим за $k$ номер отличающегося от остальных числа, которое на $s$ больше остальных. Тогда, как и в пункте c), $P(t) \equiv s t^k \pmod{R(t)}$. Аналогично пункту e) введём $\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n$~--- корни $t^n-1$. Дополнительно обозначим за $p$ какой-нибудь простой делитель $n$. Тогда
\[
\left\{
\begin{aligned}
& P(\varepsilon_1) = (1+\varepsilon_1)(1+\varepsilon_2)\cdots(1+\varepsilon_n) = 2 = s\varepsilon_k,
\\
& P(\varepsilon_p) = ((1+\varepsilon_p)(1+\varepsilon_{2p})\cdots(1+\varepsilon_n))^p = 2^p = s\varepsilon_k^p.
\end{aligned}
\right.
\]
Это, очевидно, невозможно, поэтому нечётные составные $n$ не подходят.
\end{solution}
\end{document}