М1762. Две тысячи делителей

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

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров

М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)

Условие

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

  1. отрезки AB и CD
  2. AB и BC.

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

Решение

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

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

    рисунок2

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

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

    рис1

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

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

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

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

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

  3. рисунок4

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

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

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

Условие

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

Решение

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

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

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


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

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


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

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

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

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