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.

Метод математической индукции

Под методом математической индукции понимают следующий способ доказательства: если требуется доказать истинность утверждения $latex P(n), \forall n \in \mathbb{N},$ то сначала проверяют данное утверждение для некоторого натурально числа $latex n_0 $, обычно $latex n_0=1$, а потом допускают истинность выражения $latex P(k).$ Далее доказывают истинность утверждения $latex P(k+1).$

Упражнение:

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

Доказываемое утверждение: все лошади одного цвета.

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

Проведем доказательство по индукции.

База индукции:

Одна лошадь, очевидно, одного (одинакового) цвета.
Шаг индукции:
Пусть доказано, что любые $latex K $ лошадей всегда одного цвета. Рассмотрим $latex K+1 $ каких-то лошадей. Уберем одну лошадь. Оставшиеся $latex K $ лошадей одного цвета по предположению индукции. Возвратим убранную лошадь и уберем какую-то другую. Оставшиеся $latex K $ лошадей снова будут одного цвета. Значит, все $latex K+1 $ лошадей одного цвета.

Отсюда следует, что все лошади одного цвета. Утверждение доказано.

В чем ошибка?
Решение

Спойлер

Опровержение

Противоречие возникает из-за того, что шаг индукции не сообразуется с базой. Он верен лишь при $latex K \geq 2 $. При $latex K = 1 $ (база индукции) получаемые множества оставшихся лошадей не будут пересекаться, и утверждение о равенстве цветов всех лошадей сделать нельзя.

[свернуть]

Пример:

$latex 1)$ Доказать равенство: $latex 1^{2}+2^{2}+3^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6}, n\in \mathbb{N}.$

$latex \square$ $latex 1)$  $latex 1^{2}=\frac{1(1+1)(2+1)}{6}=1.$

$latex 2)$ Пусть данное утверждение верно для $latex n=k:$   $latex 1^{2}+\cdots+k^{2}=\frac{k(k+1)(2k+1)}{6}.$

$latex 3)$ Докажем истинность утверждения для $latex n=k+1.$

$latex \overbrace{1^{2}+2^{2}+\cdots+k^{2}}^{\frac{k(k+1)(2k+1)}{6}}+(k+1)^{2}= $

$latex \frac{(k+1)(k+2)(2(k+1)+1)}{6} $

$latex \frac{k(k+1)(2k+1)}{6}+(k+1)^{2}= $

$latex \frac{(k+1)(k+2)(2k+3)}{6} $

$latex \frac{k(k+1)(2k+1)+6(k+1)^{2}}{6}= $

$latex \frac{(k+1)(k+2)(2k+3)}{6} $

$latex k(2k^{2}+k+2k+1)+6(k^{2}+2k+1)= $

$latex (k+1)(2k^{2}+3k+4k+6) $

 $latex 2k^{3}+3k^{2}+k+6k^{2}+12k+6= $

$latex 2k^{3}+7k^{2}+6k+2k^{2}+7k+6 $

$latex 2k^{3}+9k^{2}+13k+6= $

$latex 2k^{3}+9k^{2}+13k+6.$   $latex \blacksquare$

$latex 2)$ Доказать, что для всех натуральных чисел $latex n$ справедливо неравенство $latex n \leq 2^{n}$.

$latex \square$ Для $latex n=1$ неравенство принимает вид $latex 1 \leq 2$, т.е. оно справедливо.

Предположим, требуемое неравенство имеет место при некотором $latex n=k$ и покажем, что оно же справедливо и для $latex n=k+1$.

Сложим предположение индукции $latex k \leq 2^{k}$ с неравенством $latex 1 \leq 2 \leq 2^{k}$. Находим $latex k+1 \leq 2^{k}+2^{k}=2^{k+1}$, что и требовалось доказать. $latex \blacksquare$

Тест "Метод математической индукции"

Тестовые вопросы по вышеизложенному материалу.

Таблица лучших: Тест "Метод математической индукции"

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

Список литературы:

  • Лысенко З.М. Конспект лекций по курсу математического анализа.
  • В.И.Коляда, А.А.Кореновский «Курс лекций по мат.анализу, часть 1» (Одесса «Астропринт» , 2009г.), стр.4.