M1699. Неравенство

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

Условие

Докажите, что при любом натуральном $n$ справедливо неравенство $$\left \{ \sqrt{1} \right \} + \left \{ \sqrt{2} \right \} +\dots+ \left \{ \sqrt{n} \right \} \leqslant \frac{n^2-1}{2}$$
(Здесь $\left \{ k \right \}$ — дробная часть числа $k$.)

Решение

При $n = 1$ неравенство обращается в равенство $0 = 0$. При $n > 1$ докажем, что сумма дробных частей на каждом промежутке между двумя последовательными квадратами удовлетворяет неравенству $$\sum_{k=m^2}^{m^2+2m} \left \{ \sqrt{k} \right \} \leqslant \frac{2m+1}{2}.\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(1)$$

Нетрудно проверить (например, с помощью очевидного неравенства $\displaystyle \sqrt{m^2+x} \leqslant m + \frac{x}{2m}$), что
$$\sqrt{m^2+a} + \sqrt{m^2 + m -a} \leqslant 2m+1$$
при $0 \leqslant a \leqslant m$.

Следовательно, $$\left \{ \sqrt{m^2+a} \right \} + \left \{ \sqrt{m^2 + 2m -a} \right \} \leqslant 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(2)$$

Просуммировав эти неравенства при $a =0,1,\dots,m-1$ и неравенство $\displaystyle \left \{ m^2+m \right \} \leqslant \frac{1}{2}$ (получаемое деление на $2$ обеих частей $(2)$ при $a = m$), приходим к неравенству $(1)$. Суммируя неравенство $(1)$ по всем $m$ от $1$ до $n-1$, получаем $$\sum_{k=1}^{n^2-1} \left \{ \sqrt{k} \right \} \leqslant \frac{n^2-1}{2}.$$

Остается заметить, что $\left \{ \sqrt{n^2} \right \} = 0.$

А. Храбров

М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$.

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

РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ

Решение матричных уравнений

Матричные уравнения бывают трех типов.

  • 1. A \cdot X=B
  • 2. X \cdot A=B
  • 3. C \cdot X \cdot A=B
  • Пример 1. Чтобы решить уравнение первого типа нужно обе части уравнения умножить на обратную к матрице A слева.
    \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} \cdot X= \begin{pmatrix} 3 & 5 \\ 5 & 9 \\ \end{pmatrix}, \det \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix}=-2
    A_{11}=(-1)^{1+1} \cdot 4=4
    A_{12}=(-1)^{1+2} \cdot 3=-3
    A_{21}=(-1)^{2+1} \cdot 2=-2
    A_{22}=(-1)^{2+2} \cdot 1=1
    \begin{pmatrix} 4 & -3 \\ -2 & 1 \\ \end{pmatrix}, полученную матрицу транспонируем и умножим на \det^{-1} \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix}=-1/2. Обратная матрица к \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} равна \begin{pmatrix} -2 & 1 \\ 3/2 & -1/2 \\ \end{pmatrix}.
    X=\begin{pmatrix} -2 & 1 \\ 3/2 & -1/2 \\ \end{pmatrix} \cdot  \begin{pmatrix} 3 & 5 \\ 5 & 9 \\ \end{pmatrix}, X= \begin{pmatrix} -1 & -1 \\ 2 & 3 \\ \end{pmatrix}. Сделаем проверку \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} \cdot \begin{pmatrix} -1 & -1 \\ 2 & 3 \\ \end{pmatrix}=\begin{pmatrix} 3 & 5 \\ 5 & 9 \\ \end{pmatrix}. Уравнение решили правильно.
    Пример 2. Чтобы решить уравнение второго типа нужно обе части уравнения умножить на обратную к матрице A справа.
    X \cdot \begin{pmatrix} 3 & -2 \\ 5 & -4 \\ \end{pmatrix}= \begin{pmatrix} -1 & 2 \\ -5 & 6 \\ \end{pmatrix}. Матрица обратная к \begin{pmatrix} 3 & -2 \\ 5 & -4 \\ \end{pmatrix} равна \begin{pmatrix} 2 & -1 \\ 5/2 & -3/2 \\ \end{pmatrix}. X=\begin{pmatrix} -1 & 2 \\ -5 & 6 \\ \end{pmatrix} \cdot \begin{pmatrix} 2 & -1 \\ 5/2 & -3/2 \\ \end{pmatrix}, X=\begin{pmatrix} 3 & -2 \\ 5 & -4 \\ \end{pmatrix}.
    Пример 3. Чтобы решить уравнение третьего типа нужно обе части уравнения умножить на обратную к матрице A справа и на обратную матрице C слева.
    \begin{pmatrix} 3 & -1 \\ 5 & -2 \\ \end{pmatrix} \cdot X \cdot \begin{pmatrix} 5 & 6 \\ 7 & 8 \\ \end{pmatrix}= \begin{pmatrix} 14 & 16 \\ 9 & 10 \\ \end{pmatrix}. Обратная матрица к \begin{pmatrix} 3 & -1 \\ 5 & -2 \\ \end{pmatrix} равна \begin{pmatrix} 2 & -1 \\ 5 & -3 \\ \end{pmatrix}, обратная матрица к \begin{pmatrix} 5 & 6 \\ 7 & 8 \\ \end{pmatrix} равна \begin{pmatrix} -4 & 3 \\ 7/2 & -5/2 \\ \end{pmatrix}. X=\begin{pmatrix} 2 & -1 \\ 5 & -3 \\ \end{pmatrix} \cdot \begin{pmatrix} 14 & 16 \\ 9 & 10 \\ \end{pmatrix} \cdot  \begin{pmatrix} -4 & 3 \\ 7/2 & -5/2 \\ \end{pmatrix}=\begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix}.
    Проверка \begin{pmatrix} 3 & -1 \\ 5 & -2 \\ \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} \cdot \begin{pmatrix} 5 & 6 \\ 7 & 8 \\ \end{pmatrix}= \begin{pmatrix} 14 & 16 \\ 9 & 10 \\ \end{pmatrix}.
    Пример 4. Случай когда обратная матрица не существует.
    X \cdot \begin{pmatrix} 3 & 6 \\ 4 & 8 \\ \end{pmatrix}= \begin{pmatrix} 2 & 4 \\ 9 & 18 \\ \end{pmatrix}.
    Матрицу X запишем как \begin{pmatrix} x_{1} & x_{2} \\ x_{3} & x_{4} \\ \end{pmatrix}, \begin{pmatrix} 3 \cdot x_{1}+4 \cdot x_{2} & 6 \cdot x_{1}+8 \cdot x_{2} \\ 3 \cdot x_{3}+4 \cdot x_{4} & 6 \cdot x_{3}+8 \cdot x_{4} \\ \end{pmatrix}=\begin{pmatrix} 2 & 4 \\ 9 & 18 \\ \end{pmatrix}.

    \begin{cases}
    3 \cdot x_{1}+4 \cdot x_{2} = 2\\
    6 \cdot x_{1}+8 \cdot x_{2} = 4\\
    3 \cdot x_{3}+4 \cdot x_{4} = 9\\
    6 \cdot x_{3}+8 \cdot x_{4}=18
    \end{cases}
    Эта система эквивалентна
    \begin{cases}
    3 \cdot x_{1}+4 \cdot x_{2} = 2\\
    3 \cdot x_{3}+4 \cdot x_{4} = 9
    \end{cases}
    Решив данную систему получим общей вид решения X=\begin{pmatrix} x_{1} & (2-3x_{1})/4 \\ x_{3} & (9-4x_{1})/3 \\ \end{pmatrix}
    Литература

  • 1. Белозёров Г. С. Конспект по алгебре и геометрии
  • 2. Линейная алгебра. Воеводин. В. В. М.: Наука. Главная редакция физико-математической литературы, 1980 год, стр. 211-213.
  • Сборник задач по линейной алгебре. Проскуряков. И. В. М. 1961 год, стр. 118-119.
  • Решение матричных уравнений

    Обращение матриц. Решение матричных уравнений

    Таблица лучших: Решение матричных уравнений

    максимум из 2 баллов
    Место Имя Записано Баллы Результат
    Таблица загружается
    Нет данных

    Симметрическая группа

    Множество всех подстановок порядка n с операцией умножения подстановок образуют группу S_n. Единичным элементом группы является подстановка e=\begin{pmatrix}1&2&\cdots&n\\1&2&\cdots&n\end{pmatrix}, обратной подстановкой для \pi=\begin{pmatrix}i_1&i_2&\cdots&i_n\\j_1&j_2&\cdots&j_n\end{pmatrix} является \pi^{-1}=\begin{pmatrix}j_1&j_2&\cdots&j_n\\i_1&i_2&\cdots&i_n\end{pmatrix}. Порядок этой группы равен n!.
    Группа S_n называется симметрической группой порядка n .
    При n>2 группа S_n не коммутативна.

    Пример

    Группа S_3 состоит из шести элементов: e=\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix},\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix},\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix},\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix},\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix},\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}. Эта группа не коммутативна: произведение \begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix} равно \begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}, что отлично от \begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}.

    Задача

    Доказать, что порядок группы S_n равен n!.

    ... показать

    Источники

    Структуры и подструктуры

    Тест на тему «Простейшие задачи на определение структур группы, кольца, поля. Подструктуры.Циклическая группа. Симметрическая группа.». Прочтите все четыре статьи, прежде чем проходить тест.

    Циклическая группа

    Будем говорить, что группа G является циклической, если существует такой элемент a\in G, что всякий элемент x\in G может быть записан в виде x=a^n, где n\in Z(другими словами, если отображение f: Z\rightarrow G, определяемое формулой f(n)=a^n,сюръективно). При этом элемент a называется образующей группы G. Всякая циклическая группа, очевидно, абелева.
    Примером бесконечной циклической группы служит аддитивная группа целых чисел — всякое целое число кратно числу 1, то есть это число служит образующим элементом рассматриваемой группы; в качестве образующего элемента можно было бы также взять число -1.
    Примером конечной циклической группы порядка n служит мультипликативная группа корней n-ой степени из единицы. Все эти корни являются степенями одного их них, а именно первообразного корня.

    Задача

    Пусть G — группа с групповой операцией \ast и g\in G. Доказать, что множество H=\{g^k, (g')^k|k\in N\cup \{0\}\} является группой. Группа H является циклической, порождённой g. H=\langle g\rangle.


    Решение.Введём обозначения: g'=g^{-1}, (g')^k=g^{-k}. Докажем, что для m,n\in Z выполняется g^m\ast g^n=g^{m+n}.
     m\geq 0, n\geq 0\Rightarrow g^m\ast g^n=g^{m+n}.
    -n\leq m<0

    Структуры и подструктуры

    Тест на тему «Простейшие задачи на определение структур группы, кольца, поля. Подструктуры.Циклическая группа. Симметрическая группа.». Прочтите все четыре статьи, прежде чем проходить тест.

    Таблица лучших: Структуры и подструктуры

    максимум из 7 баллов
    Место Имя Записано Баллы Результат
    Таблица загружается
    Нет данных