Алгоритм Евклида

Алгоритм Евклида — это эффективный алгоритм для нахождения НОД. Для натуральных чисел, таких как $9$ и $6,$ достаточно было просто перебирать числа для нахождения НОД. Если же перебирать числа для более сложных примеров, как, например, $52152$ и $9875,$ то процесс нахождение НОД будет слишком долгим. Поэтому, вместо того чтобы перебирать числа, можно просто выполнить ряд простых действий.

Определение. Даны числа $A, B \in \mathbb{Z}^{+},$ где $A \geqslant B$ и $r_{k}, q_{k} \in \mathbb{Z}^{+},$ при $k = 1,2,3…n,$ где $r_k$ — остаток, а $q_{k}$ — частное. Находим ряд равенств: $$A = Bq_{1} + r_{1}$$ $$B = r_{1}q_{2}+r_2$$ $$r_{1} = r_{2}q_{3}+r_{3}$$ $$……$$ $$r_{n-1} = r_{n}q_{n+1}+0,$$ где $r_{n}$ и будет НОД целых чисел $A$ и $B$. Все ранее написанное и называется алгоритмом Евклида.

Другими словами, мы представляем деление $A$ на $B,$ как $A = Bq + r$ и пока остаток $r \neq 0$ мы делим делитель на остаток от деления. А так как остаток всегда меньше делителя двух целых чисел ($r_{1} < B$ или $r_{n} < r_{n-1}$), то рано или поздно остаток будет равен нулю. А НОД двух чисел будет последний делитель.

Выполним те же действия, но на этот раз запишем деление в столбик.


Спойлер

Евклид не открывал этот алгоритм. Этот алгоритм был придуман Аристотелем. Евклид лишь описал этот алгоритм в двух книгах «Начал», а конкретно в VII и X книгах. В первой он описал алгоритм как нахождение НОД двух натуральных чисел, а во второй как нахождение общей меры.

[свернуть]

НОД двух многочленов

Как и с большими целыми числами, алгоритм Евклида очень удобен для поиска НОД двух многочленов.

Теорема. Наибольший общий делитель двух многочленов существует.

Пусть даны два многочлена $f\left(x\right), g\left(x\right) \in P[x],$ где $\deg \left(f\left(x\right)\right) \geqslant \deg \left(g\left(x\right)\right)$. Находим ряд равенств: $$f\left(x\right) = g\left(x\right)q_1\left(x\right)+r_1\left(x\right)$$ $$g\left(x\right) = r_{1}\left(x\right)q_{2}\left(x\right)+r_{2}\left(x\right)$$ $$r_{1}\left(x\right) = r_{2}\left(x\right)q_{3}\left(x\right)+r_{3}\left(x\right)$$ $$……$$ $$r_{n-1}\left(x\right) = r_{n}\left(x\right)q_{n+1}\left(x\right)+0,$$ где $r_{k}, q_{k} \in P[x]$ при $k = 1,2,3,…,n,$ где $r_{k}$ — остаток, а $q_{k}$ — частное. В случае с целыми числами, остатки в алгоритме убывают, при многочленах же убывают степени остатка ($\deg \left(r_{n}\left(x\right)\right) < \deg \left(r_{n-1}\left(x\right)\right) < \deg \left(r_{n-2}\left(x\right)\right) < …$), это означает, что наступит момент деления без остатка. Поэтому НОД двух многочленов, по алгоритму Евклида, будет последний отличный от нуля остаток(в нашем случае $r_{n}$).

В доказательстве мы явно описали принцип работы алгоритма Евклида для нахождения НОД двух многочленов над одним полем.

Запишем тот же алгоритм делением в столбик.

Примеры решения задач

Решим пару простых задач, где используется алгоритм Евклида. Рекомендую решить задания самостоятельно, а потом смотреть решение.

  1. Найти НОД $784$ и $552$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$784 = 552 \times 1 + 232$$ $$552 = 232 \times 2 + 88$$ $$232 = 88 \times 2 + 56$$ $$88 = 56 \times 1 + 32$$ $$56 = 32 \times 1 + 24$$ $$32 = 24 \times 1 + 8$$ $$24 = 8 \times 3 + 0,$$ где число $8$ — НОД $784$ и $552,$ так как это последний делитель.

  2. Найти НОД $868$ и $923$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$923 = 868 \times 1 + 55$$ $$868 = 55 \times 15 + 43$$ $$55 = 43 \times 1 + 12$$ $$43 = 12 \times 3 + 7$$ $$12 = 7 \times 1 + 5$$ $$12 = 7 \times 1 + 5$$ $$7 = 5 \times 1 + 2$$ $$5 = 2 \times 2 + 1$$ $$2 = 1 \times 2 + 0,$$ где число $1$ — НОД $868$ и $923,$ так как это последний делитель.

  3. Найти НОД $52800$ и $54108$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$54108 = 52800 \times 1 + 1308$$ $$52800 = 1308 \times 480 + 480$$ $$1308 = 480 \times 2 + 348$$ $$480 = 348 \times 1 + 132$$ $$348 = 132 \times 2 + 84$$ $$132 = 84 \times 1 + 48$$ $$84 = 48 \times 1 + 36$$ $$48 = 36 \times 1 + 12$$ $$36 = 12 \times 3 + 0,$$ где $12$ — НОД $52800$ и $54108$.

  4. Найти НОД $x^5-10x^3-20x^2-15x-4$ и $x^4-6x^2-8x-3$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$x^5-10x^3-20x^2-15x-4 = x\left(x^4-6x^2-8x-3\right) — 4x^3-12x^2-12x-4$$ $$x^4-6x^2-8x-3 = \left(- 4x^3-12x^2-12x-4\right)\left(- \frac{x}{4}\right) — 3x^3-9x^2x-9x-3$$ $$- 4x^3-12x^2-12x-4 =\left(-3x^3-9x^2x^2-9x-3\right)\left(-\frac{4}{3}\right) + 0,$$ где $3x^3-9x^2-9x-3$ — НОД многочленов $x^5-10x^3-20x^2-15x-4$ и $x^4-6x^2-8x-3,$ так как это последний делитель в алгоритме.

Проверка на освоение материала «Алгоритм Евклида».

Смотрите также

  1. Конспект Г.С.Белозерова. Глава 3 — 15с. — С. 3-5.
  2. Д.К. Фаддеев. Лекции по алгебре: Учебное пособие для вузов. — М.: Наука, 1984. — 416 с. — С. 7-11.
  3. И.М. Виноградов. Основы теории чисел. — Москва, 1952. — 181 с. — С. 8-12.

M1815. О перпендикулярах в неплоском четырехугольнике

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

Условие

Общие перпендикуляры к противоположным сторонам неплоского четырехугольника $ABCD$ взаимно перпендикулярны.

Докажите, что они пересекаются.

Решение

Инструментом решения является теорема Менелая для пространственного четырехугольника, утверждающая, что точки $X,$ $U,$ $Y,$ $V,$ взятые на сторонах четырехугольника $AB,$ $BC,$ $CD,$ $DA$ или их продолжениях, лежат в одной плоскости тогда и только тогда, когда $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CY}{YD} \cdot \frac{DV}{VA} = 1.$

Для доказательства теоремы Менелая продолжим прямые $XU$ и $YV$ до пересечения с $AC.$ Точки $X,$ $U,$ $Y,$ $V$ лежат в одной плоскости тогда и только тогда, когда все три прямые пересекаются в одной точке $P$ либо параллельны (рис. 1).

Рис. 1

Но в этом случае, применяя теорему Менелая к треугольникам $ABC$ и $ACD,$ получаем $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CP}{PA} = 1$ и $\frac{CY}{YD} \cdot \frac{DV}{VA} \cdot \frac{AP}{PC} = 1.$ Перемножая эти равенства, получим требуемое соотношение.

Пусть теперь $XY$ – перпендикуляр к сторонам $AB$ и $CD,$ $UV$ – перпендикуляр к $AD$ и $BC.$ При ортогональной проекции на плоскость, параллельную $XY$ и $UV,$ прямой угол между прямыми $AB$ и $XY$ остается прямым. Поэтому четырехугольник $ABCD$ проецируется в прямоугольник $A’B’C’D’,$ а прямые $XY$ и $UV$ – в параллельные его сторонам прямые $X′Y′$ и $U′V′$ (рис. 2). Очевидно, что $\frac{A’X’}{X’B’} \cdot \frac{B’U’}{U’C’} \cdot \frac{C’Y’}{Y’D’} \cdot \frac{D’V’}{V’A’} = 1.$

Рис. 2

Следовательно, $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CY}{YD} \cdot \frac{DV}{VA} = 1,$ и по теореме Менелая точки $X,$ $Y,$ $U,$ $V$ лежат в одной плоскости. Отсюда сразу следует утверждение задачи.

А.Заславский

4.1 Непрерывные функции. Определение и примеры

Определение. Пусть функция $f$ определена на интервале $(a, b)$ и точка $x_0 \in (a, b)$. Говорят, что функция $f$ непрерывна в точке $x_0$, если $$\lim\limits_{x \to x_0}f(x) = f(x_0).$$

Замечание. В отличие от определения предела функции $f$ в точке $x_0$, здесь мы требуем, чтобы функция $f$ была определена не только в проколотой окрестности точки $x_0$, а в целой окрестности точки $x_0$. Кроме того, $\lim\limits_{x \to x_0}f(x)$ не просто существует, а равен определенному значению, а именно, $f(x_0)$.

Используя определение предела функции в смысле Коши, определение непрерывности функции $f$ в точке $x_0$ в кванторах можно записать следующим образом: $$\forall \varepsilon > 0 \; \exists \delta = \delta(\varepsilon) > 0: \forall x \in (a, b): |x — x_0| < \delta \Rightarrow \Big|f(x) — f(x_0)\Big| < \varepsilon.$$

В этом определении можно не требовать выполнения условия $|x — x_0| > 0$, т. к. при $|x − x_0| = 0$ неравенство $\Big|f(x) − f(x_0)\Big| < \varepsilon$, очевидно, выполнено.

Так как величина $\lim\limits_{x \to x_0}f(x)$ зависит лишь от тех значений, которые функция $f$ принимает в сколь угодно малой окрестности точки $x_0$, то непрерывность – это локальное свойство функции.

В терминах окрестностей определение непрерывности выглядит следующим образом.

Определение. Функция $f$ называется непрерывной в точке $x_0$, если для любой окрестности $V$ точки $f(x_0)$ найдется такая окрестность $U$ точки $x_0$, что для всех $x \in U$ значение $f(x) \in V$, т. е. $f\Big(U \cap (a, b)\Big) \subset V$.

Применяя определение предела функции в смысле Гейне, определение непрерывности можно сформулировать так.

Определение. Функция $f$, определенная на интервале $(a, b)$, называется непрерывной в точке $x_0 \in (a, b)$, если любая последовательность аргументов $\{x_n\}$ $\Big(x_n \in (a, b), x_n \to x_0\Big)$ порождает последовательность значений функции $\{f(x_n)\}$, стремящуюся к $f(x_0)$.

Применяя понятие, одностороннего предела (т. е. предела слева и справа) в точке $x_0$, можно дать определения непрерывности слева (справа) в точке $x_0$. Именно, функция $f$ называется непрерывной слева (справа) в точке $x_0$, если $\lim\limits_{x \to x_0-0}f(x) = f(x_0)$ $\Big(\lim\limits_{x \to x_0+0}f(x) = f(x_0)\Big).$ При этом в определении непрерывности слева достаточно считать, что функция $f$ определена лишь в левой полуокрестности точки $x_0$, т. е. на $(a, x_0]$, а для
непрерывности справа – на $[x_0, b)$.

Легко видеть, что справедливо следующее

Утверждение. Для того чтобы функция $f$ была непрерывной в точке $x_0$, необходимо и достаточно, чтобы $f$ была непрерывной слева и справа в точке $x_0.$

Определение. Функция $f$, определенная на интервале $(a, b)$, называется разрывной в точке $x_0 \in (a, b)$, если $f$ не является непрерывной в этой точке.

Итак, функция $f$ является разрывной в точке $x_0$, если выполнено одно из двух следующих условий.

  1. Либо не существует $\lim\limits_{x \to x_0}f(x)$.
  2. Либо предел $\lim\limits_{x \to x_0}f(x)$ существует, но он не равен $f(x_0)$.

Пример 1. $f(x) ≡ C = Const$. Эта функция непрерывна в каждой точке $x_0 \in \mathbb{R}$, т. к. для любого $x \in \mathbb{R}$ $\Big|f(x) − f(x_0)\Big| = 0$.

Пример 2. $f(x) = x^2$, $-\infty \lt x \lt +\infty$, $x_0 \in \mathbb{R}$. Зададим $\varepsilon > 0$. Тогда из неравенства $$|x^2 — {x_0}^2| \leqslant \Big(|x| + |x_0|\Big)|x − x_0|$$ следует, что при $|x − x_0| < \delta = \min\Big(1, \frac{\varepsilon}{2|x_0| + 1}\Big)$ справедливо неравенство $|x^2 — {x_0}^2| < \varepsilon$, т. е. $\lim\limits_{x \to x_0}x^2 = {x_0}^2$, а значит, функция $f(x) = x^2$ непрерывна в любой точке $x_0 \in \mathbb{R}$.

Пример 3. $f(x) = \sqrt{x}$, $0 \leqslant x \leqslant +\infty$ Если $x_0 \in (0, +\infty)$, то $$\Big|\sqrt{x} — \sqrt{x_0}\Big| = \frac{|x — x_0|}{\sqrt{x} + \sqrt{x-0}} \leqslant \frac{1}{\sqrt{x_0}}|x — x_0| \lt \varepsilon$$ если только $|x − x_0| \lt \delta \equiv \sqrt{x_0} \cdot \varepsilon$. Таким образом, функция $f(x) = \sqrt{x}$ непрерывна в каждой точке $x_0 \gt 0$. В точке $x_0 = 0$ можно ставить вопрос о непрерывности справа. Имеем $\Big|\sqrt{x} — \sqrt{0}\Big| = \sqrt{x} \lt \varepsilon$, если только $0 \leqslant x \lt \delta \equiv \varepsilon^2$. Итак, $\lim\limits_{x \to 0+}\sqrt{x} = 0 = \sqrt{0}$, т. е. функция $f(x) = \sqrt{x}$ непрерывна справа в точке $0$.

Пример 4. $f(x) = \sin x$, $-\infty \lt x \lt +\infty$. Пусть $x_0 \in \mathbb{R}$. Тогда $$|\sin x − \sin x_0| = \bigg|2\cos{\frac{x + x_0}{2}}\sin{\frac{x — x_0}{2}}\bigg| \leqslant 2\bigg|\sin{\frac{x — x_0}{2}}\bigg| \leqslant |x — x_0|,$$ где последнее неравенство в этой цепочке следует из доказанного выше неравенства $|\sin t| \leqslant |t|$ ($0 \lt |t| \lt \frac{\pi}{2}$). Можем считать, что $|x − x_0| \lt \pi$. Тогда при $|x − x_0| \lt \delta \equiv \min(\pi, \varepsilon)$ справедливо $|\sin{x} − \sin{x_0}| \lt \varepsilon$, т. е. функция $f(x) = \sin{x}$ непрерывна в каждой точке $x_0 \in \mathbb{R}$. Аналогично доказываем, что функция $f(x) = \cos{x}$ непрерывна в каждой точке $x_0 \in \mathbb{R}$.

Пример 5. $f(x) = x \cdot \sin{\frac{1}{x}}$ при $x \neq 0$ и $f(0) = 0$. Покажем, что функция $f$ непрерывна в точке $x_0 = 0$. Имеем $f(0) = 0$ и $$\lim\limits_{x \to 0}f(x) = \lim\limits_{x \to 0}x\sin{\frac{1}{x}} = 0$$ (т. к. $\Big|f(x) − 0\Big| = \Big|x\sin{\frac{1}{x}}\Big| \leqslant |x| \lt \varepsilon$, если только $|x − 0| = |x| \lt \delta \equiv \varepsilon$). Итак, $\lim\limits_{x \to x_0}f(x) = f(0)$, так что $f$ непрерывна в точке $0$.

Пример 6. $f(x) = \text{sign}\;x$, $x \in \mathbb{R}$. Если $x_0 \neq 0$, то функция $f$ постоянна в некоторой окрестности точки $x_0$ и, следовательно, непрерывна в этой точке. Если же $x_0 = 0$, то не существует предела функции $f$ при $x \to 0$. Значит, функция $f$ разрывна в точке $0$. Более того,$\lim\limits_{x \to 0+}\text{sign}\; x = 1$, $\lim\limits_{x \to x_0}f(x)\text{sign}\;x = −1$, $\text{sign}\;0 = 0$, так что функция $\text{sign}\; x$ разрывна в точке $0$ как слева, так и справа.

Пример 7. Рассмотрим функцию Дирихле $$\mathcal{D}(x) =
\begin{cases}
1, & \text{если $x \in \mathbb{Q}$;} \\
0, & \text{если $x \in {\mathbb{R} \backslash \mathbb{Q}}$.}
\end{cases}$$ Пусть $x_0 \in \mathbb{R}$. Покажем, что не существует предела функции $\mathcal{D}$ при $x \to x_0$. Для этого выберем последовательность $\{x^\prime\}$ отличных от $x_0$ рациональных чисел, стремящуюся к $x_0$. Тогда $\mathcal{D}(x^\prime_n) = 1$ и, значит, $\lim\limits_{n \to +\infty}\mathcal{D}(x^\prime_n) = 1$. Если же взять последовательность ${x^{\prime\prime}_n}$ отличных от $x_0$ иррациональных чисел, стремящуюся к $x_0$, то получим, что $\mathcal{D}(x^{\prime\prime}_n) = 0$ и $\lim\limits_{n \to +\infty}\mathcal{D}(x^{\prime\prime}_n) = 0$. В силу определения предела функции по Гейне получаем, что функция $\mathcal{D}$ не имеет предела в точке $x_0$. Так как $x_0 \in \mathbb{R}$ – произвольная точка, то это означает, что функция Дирихле разрывна в каждой точке.

Пример 8. $f(x) = x \cdot \mathcal{D}(x)$, $x \in \mathbb{R}$. Функция $f$ разрывна в каждой точке $x_0 \neq 0$. В самом деле, если $\{x^\prime_n\}$ и $\{x^{\prime\prime}_n\}$ соответственно последовательности рациональных и иррациональных отличных от $x_0$ чисел, стремящиеся к $x_0$, то $\lim\limits_{n \to \infty}f(x^{\prime}_n) = x_0$ и $\lim\limits_{n \to \infty}f(x^{\prime\prime}_n) = 0$, так что, в силу определения предела функции по Гейне, функция $f$ не имеет предела в точке $x_0$. Если же $x_0 = 0$, то $\lim\limits_{n \to 0}f(x) = 0 = f(0)$. Действительно, $|f(x)| = |x \cdot \mathcal{D}(x)| \leqslant |x| \lt \varepsilon$, если только $|x − 0| = |x| \lt \delta \equiv \varepsilon$. Это означает, что данная функция непрерывна в единственной точке $x_0 = 0$.

Пример 9. Дана функция $$f(x) =
\begin{cases}
\frac{\sin x}{x}, & \text{если $x \neq 0$;} \\
1, & \text{если $x = 0$.}
\end{cases}$$ Проверить на непрерывность в точке $x_0 = 0$.

Решение

$$\lim\limits_{x \to x_0 — 0}\frac{\sin x}{x} = \lim\limits_{x \to 0 + 0}\frac{\sin x}{x} = 1 = f(x_0)$$ Отсюда следует, что $f(x)$ непрерывна в точке $x_0$, т. к. для того чтобы функция $f$ была непрерывной в точке $x_0$, необходимо и достаточно, чтобы $f$ была непрерывной слева и справа в точке $x_0.$

Пример 10. Покажите, что функция $f(x) = \frac{x + 3}{x — 2}$ разрывна в точке $x_0 = 2.$

Решение

Для этого достаточно показать, что предел данной функции при $x \to x_0$ либо не равен значению функции в точке $x_0$, либо не существует. $$\lim\limits_{x \to 2 — 0}\frac{x + 3}{x — 2} = -\infty$$ $$\lim\limits_{x \to 2 + 0}\frac{x + 3}{x — 2} = +\infty$$ Т. к. левосторонний и правосторонний пределы $f(x)$ не совпадают, то предела функция в точке $x_0$ не имеет, следовательно она разрывна в этой точке.

Литература

Непрерывные функции. Определение и примеры

Тест по теме: «Непрерывные функции. Определение и примеры.»


Таблица лучших: Непрерывные функции. Определение и примеры

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

M683. О расположении разноцветных кружков

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

Условие

Несколько кружков одинакового размера положили на стол так, что никакие два не перекрываются. Докажите, что кружки можно раскрасить в четыре цвета так, что любые два касающиеся кружка будут окрашены в разные цвета. Найдите расположение кружков, при котором трех цветов для такой раскраски недостаточно.

Доказательство

Доказательство возможности требуемой раскраски проведем индукцией по числу кружков [latex]n[/latex]. При [latex]n\leq 4[/latex] утверждение очевидно. Предположим, что оно справедливо для любого расположения [latex]k[/latex] кружков. Пусть на столе лежит [latex]k+1[/latex] кружков. Зафиксируем на плоскости произвольную точку [latex]M[/latex] и рассмотрим кружок, центр [latex]O[/latex] которого находится на наибольшем расстоянии от [latex]M[/latex] (если таких кружков несколько, возьмем любой из них). Нетрудно убедиться, что выбранного кружка касается не более двух других (центры всех кружков лежат в круге [latex]\left ( M, \left | OM \right | \right )[/latex] — рис. 1). Отбросим кружок с центром [latex]O[/latex] и раскрасим нужным образом в четыре цвета оставшиеся [latex]k[/latex] кружков (по предположению индукции это можно сделать). Вернем теперь кружок с центром [latex]O[/latex] на место. Поскольку он касается не более трех из уже покрашенных кружков, его можно раскрасить в тот цвет, который не был использован при раскраске касающихся его соседей.

Утверждение доказано.

Рисунок 1.

На рисунке 2 изображены 11 кружков, для нужной раскраски которых трех цветов недостаточно. Действительно, предположив, что эти кружки можно раскрасить тремя цветами, получим, что кружки [latex]A, B, C, D, E[/latex] должны быть окрашены одинаково. Но это невозможно, поскольку кружки [latex]A[/latex] и [latex]E[/latex] касаются.

Рисунок 2.

M610. Об «интересных» наборах чисел

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

Условие

Фиксируем $k \in \mathbb N$.
$а)$ Рассмотрим множество всех наборов целых чисел $a_1, \ldots , a_k$ таких, что $0 \le a_1 \le a_2 \le \ldots \le a_k \le k$; обозначим число таких наборов через $N.$ Рассмотрим среди них те, для которых $a_k = k$; пусть их число равно $M$. Докажите, что $N=2M$.
$б)$ Наложим на рассматриваемые наборы дополнительное ограничение: сумма $a_1 + \ldots + a_k$ делится на $k$. Пусть соответствующие числа равны $N’$ и $M’$. Докажите, что $N’ = 2M’$ (Из рисунка 1 видно, что при $k=3$ эти числа равны $M=10$, $N=20$; $M’=4$, $N’=8$.)

Рис. 1.

Решение

Как известно, если два множества имеют одинаковое число элементов, между ними можно установить взаимно однозначное соответствие. Собственно говоря, это и есть определение того, что в множествах элементов поровну, но этот факт иногда забывается. А между тем довольно часто равенство двух чисел устанавливается именно через взаимно однозначное соответствие подходящих множеств.

Нам нужно доказать, что наборов, в которых $a_k = k$ ровно половина. Поэтому попробуем установить взаимно однозначное соответствие между этими наборами и оставшимися, теми, у которых $a_k < k$.

Сопоставить набору $(a_1, a_2, \ldots, a_k)$ набор $(a_k, a_{k-1}, \ldots, a_1)$ нельзя, так как новый набор — невозрастающий. Можно попробовать сопоставить набору $(a_1, \ldots, a_k)$ набор $k-a_k, k-a_{k-1}, \ldots, k-a_1)$: он уже — неубывающий, но… $k-a_1$ не обязательно быть меньше $k$. Поэтому это соответствие не решает задачу.

Значит, необходимо более сложное соответствие. Для его построения нам понадобится понятие диаграммы Юнга данного набора.

Рис. 2

Что это такое, проще всего объяснить на примере: набору $(0, 0, 2, 3, 5)$ соответствует диаграмма, изображенная на рисунке 2 — в каждой строке столько соответствующее число.

Дополним диаграмму Юнга до квадрата (рис. 3). Тогда становится ясно, что наша первоначальная идея заключалась в том, что отсчитывать диаграмму не из красных, а из белых квадратиков (и, соответственно, не слева-снизу, а справа-сверху).

Рис. 3

Попытаемся теперь дополнить рисунок 3 вертикальной диаграммой — как на рисунке 4. Отсчитывая эту диаграмму снизу-слева, получим набор $(2, 2, 3, 4, 4)$. Назовем этот набор дополнительным к набору $(0, 0 , 2, 3, 5)$. Еще один пример изображен на рисунке 5.

Ясно, что если исходный набор $(a_1, \ldots, a_k),$ а дополнительный — $(b_1, \ldots, b_k)$, то $(a_k = k)$ тогда и только тогда, когда $b_k < k$. В самом деле, $a_k = k$, если верхняя правая клетка входит в основную диаграмму Юнга, и $a_k < k,$ если она входит в дополнительную.

Рис. 4

Установленное нами соответствие между наборами, у которых $a_k = k$, и наборами, у которых $a_k < k$, очевидно, взаимно однозначно. Тем самым мы решили $a)$. Кроме того, сумма чисел исходного и дополнительного наборов равна $k^2$ (в наших примерах — 25). Поэтому сумма чисел дополнительного набора делится на $k$ тогда и только тогда, когда делится на $k$ сумма чисел исходного набора. Это решает $б)$.

Рис. 5

Замечание. Задача $a)$ имеет и другое решение: можно непосредственно посчитать числа $N$ и $M$.

Лемма. Число наборов целых чисел $a_1, \ldots, a_m$ таких, что $0 \le a_1 \le \ldots \le a_m \le k$ равно $C^m_{k+m}$.

Доказательство. Рассмотрим набор $(b_1, \ldots, b_m)$ где $b_i = a_i + i : b_1 = a_1 +1, b_2 = a_2 +2 $ и т. д. Тогда, очевидно, $1 < b_1 < b_2 < \ldots < b_m \le k+m$, то есть $(b_1, \ldots, b_m)$ — произвольный возрастающий набор $m$ целых чисел их первых $k+m$ чисел. Число таких наборов равно $C^m_{k-m}$.

Поэтому число наборов, в которых $a_k \le k$, по лемме равно $C^k_{2k}$. Если же $a_k = k$, то нам остается выбрать числа $a_1, \ldots, a_{k-1}$ так, что $0 \le a_1 \le \ldots \le a_{k-1} \le k$; их число равно $C^{k-1}_{2k-1}$. Остается посчитать, что $2C^{k-1}_{2k-1}$ равно $C^k_{2k}$.

А. Толпыго