М1787. Диафантово уравнение

Задача из журнала «Квант» (2002 год, 2 выпуск)

Условие

Пусть $ 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 $. Этим всё доказано.

Н. Осипов

M927. Замена пересекающихся отрезков

Задача из журнала «Квант» (1985, №10)

Условие

На плоскости дано конечное множество точек, никакие три из которых не лежат на одной прямой. Проведено несколько отрезков с концами в данных точках. Эти отрезки разрешается менять: если какие-то два из них, [latex]AC[/latex] и [latex]BD[/latex], пересекаются, их можно стереть и провести

  1. отрезки [latex]AB[/latex] и [latex]CD[/latex]
  2. [latex]AB[/latex] и [latex]BC[/latex].

(Если «новый» отрезок уже проведён, проводить его второй раз не нужно.)
Можно ли после нескольких таких замен (только по правилу 1 или по правилу 2, но не по обоим) вернуться к исходному набору отрезков?

Решение

  1. Докажем, что через конечное число операций «типа 1» — замены пересекающихся [latex]AB[/latex] и [latex]CD[/latex] — мы придём к конфигурации, в которой уже не будет пересекающихся отрезков.

    Рассмотрим сумму [latex]s[/latex] длин всех отрезков конфигурации. При каждой операции «типа 1» она уменьшается:
    [latex]AB + CD < AC + BD[/latex] (*)
    (для треугольников [latex]APB[/latex] и [latex]CPD[/latex], где [latex]P[/latex] — точка пересечения [latex]AC[/latex] и [latex]BD[/latex] — рис. 1, выполнены неравенства [latex]AB < AP + PB[/latex] и [latex]CD < CP + PD[/latex]; сложив их, получим (*)).

    рисунок2

    С другой стороны, величина [latex]s[/latex] может принимать лишь конечное число различных значений, поскольку существует лишь конечное число различных конфигураций из отрезков с вершинами в данных точках. Поэтому через конечное число шагов мы придём к конфигурации, с которой уже нельзя проделать операцию, уменьшающую [latex]s[/latex].

    Это решение даёт очень грубую верхнюю оценку для максимального количества [latex]T_n[/latex] операций, которое может быть проделано с конфигурацией на [latex]n[/latex] точках — можно сказать лишь что оно меньше числа всех конфигураций, то есть [latex]2^{n\cdot(n-1)/2}[/latex], [latex]n\cdot(n-1)/2[/latex] — это число различных отрезков с концами в данных [latex]n[/latex] точках.

    рис1

    Приведём идею другого решения, дающего значительно лучшую оценку. Рассмотрим произвольное разбиение [latex]f[/latex] данных точек на два непустых множества, каждое из которых лежит целиком по одну сторону от некоторой прямой [latex]l[/latex]. Таких прямых для данного разбиения, конечно, бесконечно много, но одну из них всегда можно получить, повернув по часовой стрелке прямую, соединяющую две какие-либо точки [latex]A[/latex] и [latex]B[/latex] на очень маленький угол вокруг середины отрезка [latex]AB[/latex] (рис. 2); эту прямую обозначим [latex]l_i[/latex]. Число прямых [latex]l_i[/latex], и значит, что число рассматриваемых «выпуклых» разбиений не превосходит числа пар точек [latex]n\cdot(n-1)/2[/latex].

    Назовём балансом конфигурации суммарное число [latex]b[/latex] пересечений её отрезков со всеми прямыми [latex]l_i[/latex]; ясно, что [latex]0 \le b \le (n\cdot(n-1)/2)^2[/latex]. При операции типа 1 число пересечений любой прямой [latex]l_i[/latex] с отрезками конфигурации не увеличивается, а по крайней мере для одной прямой оно уменьшается на 2. Следовательно, [latex]T_n \le n^2 \cdot (n-1)^2 / 8[/latex]. Интересно было бы получить ещё более точную оценку для [latex]T_n[/latex].

  2. рисунок1Приведём пример, показывающий, что для операции «типа 2» — замены пересекающихся отрезков [latex]AC[/latex] и [latex]BD[/latex] не имеющих общий конец [latex]AB[/latex] и [latex]BC[/latex] — процесс может «зациклиться» и тем самым продолжаться неограниченно. Расположим 18 точек в вершинах правильного 18-угольника и обозначим через [latex]D(k, l)[/latex] конфигурацию из 36 отрезков, в которой каждая из 18 точек соединена [latex]k[/latex]-й и [latex]l[/latex]-й от неё по счёту.

    Чтобы пройти за 54 операции путь [latex]D(4, 8) \to D(5, 9) \to D(6, 7) \to D(4, 8)[/latex] (рис. 3), достаточно каждую из операций, изображенных на рисунке 4, проделать по 18 раз (поворачивая картинку каждый раз на [latex]20^{\circ}[/latex]).

    По-видимому, существуют и примеры с существенно меньшим числом точек [latex]n[/latex] и длинной цикла [latex]T[/latex], чем [latex]n = 18[/latex] и [latex]T = 54[/latex].

  3. рисунок4

    Н.Б. Васильев, В.Е. Колосов

M1722. Количество целых точек

Задача из журнала «Квант»(2000, №5)

Условие

Пусть [latex]a,b[/latex] — натуральные числа. Проведем через точку [latex](a;b)[/latex] прямую, отсекающую от первого координатного угла треугольник.
а) Докажите, что количество точек с целыми неотрицательными координатами, которые лежат внутри или на сторонах этого треугольника, больше, чем [latex]2 \cdot a \cdot b + a + b[/latex].
б) Докажите, что эта оценка точная: через точку [latex](a;b)[/latex] можно провести прямую, отсекающую от первого координатного угла треугольник, внутри и на сторонах которого всего [latex]2 \cdot a \cdot b + a + b[/latex] точек с целыми неотрицательными координатами.

Решение

Рассмотрим прямоугольник [latex]OABC[/latex] с центром в точке [latex]P(a;b)[/latex], и сторонами, параллельными осям координат(рис.1). Внутри и на сторонах этого прямоугольника всего [latex](2 \cdot a + 1) \cdot (2 \cdot b+1) = [/latex] [latex] 4\cdot a \cdot b + 2\cdot a + 2 \cdot b +1[/latex] целочисленных точек.
 
method-draw-image (8)
Pис.1
 
Чуть-чуть сдвинем точку [latex]A[/latex] вправо. Через полученную точку [latex]A'[/latex] и точку [latex]P[/latex] проведем прямую до пересечения с осью ординат в точке [latex]C'[/latex]. Если сдвиг был достаточно мал, то в треугольнике [latex]OA’C'[/latex] не появится ни одной точки с целыми координатами, которой не было бы в треугольнике [latex]OAC[/latex].
При центральной симметрии относительно [latex]P[/latex] любая целочисленная точка прямоугольника [latex]OABC[/latex] переходит в целочисленную точку этого же прямоугольника. Поэтому все отличные от [latex]P[/latex] целочисленные точки прямоугольника разбиваются на пары точек, симметричных относительно [latex]P[/latex].
Итак, если [latex]A'[/latex] достаточно близка к точке [latex]A[/latex], то внутри и на границе треугольника [latex]OA’C'[/latex] расположена ровно половина отличных от [latex]P[/latex] целочисленных точек, т.е. [latex]2 \cdot a \cdot b + a + b[/latex] точек. Вместе с точкой [latex]P[/latex] получаем всего [latex]2 \cdot a \cdot b + a + b + 1[/latex] точек. Мы решили пункт б).
 
Теперь займемся пунктом а). Для определенности, пусть прямая отсекает от первого координатного угла треугольник [latex]OA_1C_1[/latex], где точка [latex]A_1[/latex] расположена правее точки [latex]A[/latex](рис.2).
 
method-draw-image (9)
Рис.2
 
Чтобы получить треугольник [latex]OA_1C_1[/latex] из треугольника [latex]OAC[/latex], достаточно «отрезать» от последнего треугольник [latex]CC_{1}P[/latex] и добавить треугольник [latex]AA_{1}P[/latex].
Но при центральной симметрии относительно точки [latex]P[/latex] треугольник [latex]CC_{1}P[/latex] переходит в треугольник, являющийся частью треугольника [latex]AA_{1}P[/latex](закрашенный на рисунке 2). Целочисленные координаты при этом переходят в целочисленные. Задача решена.

Критерии прямой суммы

Даны пространства [latex]U, V\subseteq \mathbb{R}^{n}[/latex], заданные следующим образом [latex]U=\{(x_1,\ldots,x_n)\in \mathbb{R}^{n}|x_1+\ldots+x_n=0\}[/latex], [latex]V=\{(x_1,\ldots,x_n)\in \mathbb{R}^{n}|x_1=x_2=\ldots=x_n\}[/latex]
Докажем, что [latex]\mathbb{R}^{n} = U \oplus V[/latex]


Если [latex]U\cap V = \{0\}[/latex], то [latex]U+V=U\oplus V[/latex] (по второму критерию прямой суммы)
Предположим, что существует ненулевой вектор [latex]x[/latex] удовлетворяющий условиям
[latex]x_1=x_2=\ldots=x_n[/latex] и [latex]x_1+x_2+\ldots+x_n=0[/latex], то есть [latex]x\in U \cap V[/latex]
Так как [latex]x\ne 0[/latex], то одна из его координат отлична от нуля, а из первого условия следует, что и все координаты ненулевые.
Положим [latex]x_1=\ldots=x_n=a(a\ne 0, a\in \mathbb{R})[/latex] и используя второе условие получим, что [latex]na=0[/latex], и так как [latex]n>0 \Rightarrow a=0 \Rightarrow x=0[/latex] получим противоречие с тем, что [latex]x\ne 0 \Rightarrow[/latex][latex]U\cap V=\{0\}\Rightarrow[/latex][latex]U+V=U\oplus V[/latex].
Найдем размерности [latex]U[/latex] и [latex]V[/latex].
Очевидно, что [latex]\dim V=1[/latex] и ее базисом может быть вектор [latex](1, 1,\ldots, 1)[/latex](ЛНЗ тривиальна, полнота очевидна)
Теперь докажем, что система из [latex]n-1[/latex] векторов
[latex]\langle (1, -1, 0,\ldots, 0), (1, 0, -1,\ldots, 0),[/latex][latex]\ldots, (1, 0, 0,\ldots, -1)\rangle[/latex] базис [latex]U[/latex]. Очевидно что она ЛНЗ, т.к.
[latex]rk = \begin{pmatrix} 1 & -1 & 0 & \ldots & 0 \\ 1 & 0 & -1 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ 1 & 0 & 0 & \ldots & -1 \\ \end{pmatrix}=n-1[/latex]
Теперь проверим полноту системы. Покажем, что для [latex] \forall x\in U[/latex] выполняется условие [latex]x_1+x_2+\ldots+x_n=0 (x=(x_1, x_2,\ldots, x_n))[/latex].
Составим линейную комбинацию:
[latex]x=x_1(1,-1,0,\ldots, 0)+\ldots+\alpha_{n-1}(1,00,\ldots, -1)=[/latex]
[latex]=(\alpha_1+\ldots+\alpha_{n-1}, -\alpha_1, \ldots, -\alpha_{n-1})[/latex]
[latex]\alpha_1+\ldots+\alpha_{n-1}+(-\alpha_1)+\ldots+(-\alpha_{n-1})=0 \Rightarrow[/latex] любой вектор из [latex]U[/latex] выражается через эту систему.
Следовательно [latex]\langle (1, -1,\ldots, 0),\ldots,(1, 0,\ldots, -1)\rangle[/latex] базис [latex]U[/latex] и [latex]\dim U = n-1[/latex]. Из формулы [latex]\dim(V+U)=\dim V + \dim U — \dim(V+U)[/latex] получаем, что [latex]\dim(U+V)=\dim(U\oplus V)=n\Rightarrow[/latex] т.к. [latex]U, V\subseteq \mathbb{R}^{n}[/latex], то [latex]U\oplus V = \mathbb{R}^{n}[/latex].

[latex]V, U\subseteq \mathbb{R}^{n}[/latex] [latex]U=\langle (1, 1, 1, 1), (-1, -2, 0, 1)\rangle[/latex] [latex]V=\langle (-1, -1, 1, -1), (2, 2, 0, 1)\rangle[/latex]
Докажем, что [latex]\mathbb{R}_{4}=U\oplus V[/latex]


[latex]rk(S) = \begin{pmatrix} 1 & 1 & 1 & \ldots & 1 \\ 1 & 0 & -1 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ 1 & 0 & 0 & \ldots & -1 \\ \end{pmatrix}=n-1[/latex]

Теперь докажем, что система из [latex]n-1[/latex] векторов
[latex] S=\langle (1, -1, 0,\ldots, 0), (1, 0, -1,\ldots, 0),\ldots, (1, 0, 0,\ldots, -1)\rangle [/latex].

Покажем, что [latex] \forall x\in U [/latex] на
[latex] x=x_1(1,-1,0,\ldots, 0)+\ldots+\alpha_{n-1}(1,00,\ldots, -1)= [/latex]
[latex] =(\alpha_1+\ldots+\alpha_{n-1}, -\alpha_1, \ldots, -\alpha_{n-1}) [/latex] на [latex] x=x_1(1,-1,0,\ldots, 0)+\ldots+\alpha_{n-1}(1,0,\ldots, -1)=[/latex]
[latex] =(\alpha_1+\ldots+\alpha_{n-1}, -\alpha_1, \ldots, -\alpha_{n-1})[/latex].

Из формулы [latex] \dim(V+U)=\dim V + \dim U — \dim(V+U)[/latex] получаем, что [latex] \dim(U+V)=\dim(U\oplus V)=n\Rightarrow [/latex], так как [latex]U, V\subseteq \mathbb{R}^{n}[/latex], то [latex] U\oplus V = \mathbb{R}^{n} [/latex].
Так как сумма прямая, то по первому критерию объединение базисов суммируемых пространств: есть базис суммы этих пространств [latex] \dim(U+V)=\dim(U\oplus V)=n=\dim(\mathbb{R}^{n}) \Rightarrow U\oplus V=\mathbb{R}^{n}[/latex].

Прямое дополнение

Дано пространство $ U \subseteq \mathbb{R}^4,$ натянутое на вектора $ a_1=(2,1,0,-3),$ $ a_2=(2,3,-1,0),$ то есть $ U = \langle (2,1,0,-3), (2,3,-1,0)\rangle. $
Найдем какое-либо дополнение $ V$ к $ U$ в $ \mathbb{R}^4$.

Проверим ЛНЗ $ a_1$ и $ a_2$.
$ rank \begin{pmatrix}
2 & 1 & 0 & -3 \\
2 & 3 & -1 & 0\end{pmatrix}= $ $ rank \begin{pmatrix}
2 & 1 & 0 & -3 \\
0 & 0 & -1 & 3\end{pmatrix}= 2 \Rightarrow$
$ \langle a_1, a_2\rangle$ — базис $ U$.
$ V$ удовлетворяет условию $ V \oplus U= \mathbb{R}^4$.
Из первого критерия прямой суммы получаем, что объединение базисов $ V$ и $ U$ образуют базис $ \mathbb{R}^4$. Так как $ \dim \mathbb{R}^4= 4$ и $ \dim U= 2 \Rightarrow $ $ \dim V= 2$. Найдем какой-либо базис $ V$ . Дополним для этого систему из векторов $ \langle a_1, a_2\rangle$ до базиса векторами стандартного базиса $ (e_1,e_2,e_3,e_4)$ в $ \mathbb{R}^4$.
Зафиксируем в полученной системе вектора $ a_1$, $ a_2$ и выделим из этой системы ЛНЗ систему, содержащую эти вектора
$ \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
2 & 1 & 0 & -3 \\
2 & 3 & -1 & 0 \end{pmatrix} \sim \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & -3\\
0 & 0 & -1 & 0\end{pmatrix} \sim \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & -3\\
0 & 0 & -1 & 0\end{pmatrix} \sim \begin{pmatrix}
e_1 \\
e_2 \\
a_1 \\
a_2 \end{pmatrix} \Rightarrow $
$ \langle e_1, e_2, a_1, a_2\rangle$ -ЛНЗ,
так как эта система максимальна, она и образует базис $ \mathbb{R}^4$.
Отсюда и из рассуждения в начале получаем, что $ L \langle e_1, e_2\rangle= V$ одно из прямых дополнений к $ U$.