Алгоритм Евклида — это эффективный алгоритм для нахождения НОД. Для натуральных чисел, таких как $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}$).
В доказательстве мы явно описали принцип работы алгоритма Евклида для нахождения НОД двух многочленов над одним полем.
Запишем тот же алгоритм делением в столбик.
Примеры решения задач
Решим пару простых задач, где используется алгоритм Евклида. Рекомендую решить задания самостоятельно, а потом смотреть решение.
Найти НОД $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,$ так как это последний делитель.
Найти НОД $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,$ так как это последний делитель.
Найти НОД $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$.
Найти НОД $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,$ так как это последний делитель в алгоритме.
Лимит времени: 0
Навигация (только номера заданий)
0 из 6 заданий окончено
Вопросы:
1
2
3
4
5
6
Информация
Проверка на освоение материала «Алгоритм Евклида».
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 6
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Нет рубрики0%
1
2
3
4
5
6
С ответом
С отметкой о просмотре
Задание 1 из 6
1.
Пусть даны два целых числа $A, B$ последнее деление алгоритма Евклида представлено в виде $$r_{n-1} = r_{n}q_{n+1}+r_{n+1},$$ где $r_{n+1} = 0,$ где $r_{n} \neq A, r_{n} \neq B$ тогда НОД $A$ и $B$ будет:
Правильно
Неправильно
Задание 2 из 6
2.
Выберите верные утверждения.
Правильно
Неправильно
Задание 3 из 6
3.
Найдите НОД двух чисел.
Элементы сортировки
2
40
7
4
1
5
10
15
9854 и 9214
5000 и 6520
8512 и 5551
7012 и 6312
Правильно
Неправильно
Задание 4 из 6
4.
Найдите НОД $987$ и $123$.
Правильно
Неправильно
Задание 5 из 6
5.
Найдите НОД двух многочленов: $x^4+x^3+x^2+x+1$ и $4x^3+3x^2+2x+1$.
Правильно
Неправильно
Задание 6 из 6
6.
Распишите числа, написанные в Алгоритме Евклида, по убыванию (от набольшего к наименьшему), если $A > B$ и $A,B \in Z^+,$ где $r_k$ — остаток. При $k = 1,2,3…n$.
Общие перпендикуляры к противоположным сторонам неплоского четырехугольника $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).
Но в этом случае, применяя теорему Менелая к треугольникам $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.$
Следовательно, $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CY}{YD} \cdot \frac{DV}{VA} = 1,$ и по теореме Менелая точки $X,$ $Y,$ $U,$ $V$ лежат в одной плоскости. Отсюда сразу следует утверждение задачи.
Определение. Пусть функция $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$, если выполнено одно из двух следующих условий.
Либо не существует $\lim\limits_{x \to x_0}f(x)$.
Либо предел $\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$ не имеет, следовательно она разрывна в этой точке.
Литература
З. М. Лысенко, Конспект по математическому анализу, Курс 1, Семестр 1
Тест по теме: «Непрерывные функции. Определение и примеры.»
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 5
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Нет рубрики0%
Математический анализ0%
максимум из 5 баллов
Место
Имя
Записано
Баллы
Результат
Таблица загружается
Нет данных
Ваш результат был записан в таблицу лидеров
Загрузка
1
2
3
4
5
С ответом
С отметкой о просмотре
Задание 1 из 5
1.
Количество баллов: 1
Выберите правильное определение непрерывности функции $latex f$ в точке $latex x_0$ в кванторах.
Правильно
Неправильно
Задание 2 из 5
2.
Количество баллов: 1
Выберите такие функции $latex f(x)$, что $latex \lim\limits_{x \to x_0}f(x) = f(x_0)$.
Правильно
Неправильно
Задание 3 из 5
3.
Количество баллов: 1
Дополните предложение.
Функция, определенная на некотором интервале, называется (разрывной, не непрерывной, разрывная, не неприрывной, не непрерывная, расрывной, разрывнной) в точке, если данная точка принадлежит заданному интервалу, а сама функция не является непрерывной в этой точке.
Правильно
Неправильно
Задание 4 из 5
4.
Количество баллов: 1
Выберите достаточные условия того, что функция $latex f$ является разрывной в точке $latex x_0$.
Правильно
Неправильно
Задание 5 из 5
5.
Количество баллов: 1
Как называется функция $latex f$, определенная на интервале $latex (a, b)$, если любая последовательность аргументов $latex \{x_n\}$ ($latex x_n \in (a, b)$, $latex x_n \to x_0$) порождает последовательность значений функции $latex \{f(x_n)\}$, стремящуюся к $latex f(x_0)$.
Правильно
Неправильно
Таблица лучших: Непрерывные функции. Определение и примеры
Несколько кружков одинакового размера положили на стол так, что никакие два не перекрываются. Докажите, что кружки можно раскрасить в четыре цвета так, что любые два касающиеся кружка будут окрашены в разные цвета. Найдите расположение кружков, при котором трех цветов для такой раскраски недостаточно.
Доказательство
Доказательство возможности требуемой раскраски проведем индукцией по числу кружков [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] на место. Поскольку он касается не более трех из уже покрашенных кружков, его можно раскрасить в тот цвет, который не был использован при раскраске касающихся его соседей.
Утверждение доказано.
На рисунке 2 изображены 11 кружков, для нужной раскраски которых трех цветов недостаточно. Действительно, предположив, что эти кружки можно раскрасить тремя цветами, получим, что кружки [latex]A, B, C, D, E[/latex] должны быть окрашены одинаково. Но это невозможно, поскольку кружки [latex]A[/latex] и [latex]E[/latex] касаются.
Фиксируем $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$.)
Решение
Как известно, если два множества имеют одинаковое число элементов, между ними можно установить взаимно однозначное соответствие. Собственно говоря, это и есть определение того, что в множествах элементов поровну, но этот факт иногда забывается. А между тем довольно часто равенство двух чисел устанавливается именно через взаимно однозначное соответствие подходящих множеств.
Нам нужно доказать, что наборов, в которых $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$. Поэтому это соответствие не решает задачу.
Значит, необходимо более сложное соответствие. Для его построения нам понадобится понятие диаграммы Юнга данного набора.
Что это такое, проще всего объяснить на примере: набору $(0, 0, 2, 3, 5)$ соответствует диаграмма, изображенная на рисунке 2 — в каждой строке столько соответствующее число.
Дополним диаграмму Юнга до квадрата (рис. 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,$ если она входит в дополнительную.
Установленное нами соответствие между наборами, у которых $a_k = k$, и наборами, у которых $a_k < k$, очевидно, взаимно однозначно. Тем самым мы решили $a)$. Кроме того, сумма чисел исходного и дополнительного наборов равна $k^2$ (в наших примерах — 25). Поэтому сумма чисел дополнительного набора делится на $k$ тогда и только тогда, когда делится на $k$ сумма чисел исходного набора. Это решает $б)$.
Замечание. Задача $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}$.