Несколько кружков одинакового размера положили на стол так, что никакие два не перекрываются. Докажите, что кружки можно раскрасить в четыре цвета так, что любые два касающиеся кружка будут окрашены в разные цвета. Найдите расположение кружков, при котором трех цветов для такой раскраски недостаточно.
Доказательство
Доказательство возможности требуемой раскраски проведем индукцией по числу кружков [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] касаются.
Про [latex]n[/latex] чисел, произведение которых равно [latex]p[/latex], известно, что разность между [latex]p[/latex] и каждым из этих чисел — нечётное целое число. Докажите, что все эти числа иррациональны.
Решение:
Пусть x — одно из этих n чисел. [latex]x+b_{1} , x+b_{2}, … , x+b_{n-1}[/latex] — остальные и
[latex] p = x(x+b_{1})(x+b_{2})…(x+b_{n+1})=x+c, (1)[/latex]
где, по условию, [latex]c[/latex] нечётно, а [latex]b_{1} , b_{2}, … , b_{n-1}[/latex] должны быть чётными целыми числами. Равенство [latex](1)[/latex] можно записать, раскрыв скобки в виде
где [latex]a_{1},…,a_{n-2} [/latex] — чётные, а [latex]a_{n-1}=b_{1}b_{2}…b_{n-1}-1[/latex] и [latex]c[/latex] — нечётные числа.Предположив, что [latex]x[/latex] — рациональное число, мы сразу же убедимся, что [latex]x[/latex] должно быть целым:если [latex]x=k/d[/latex] — несократимая дробь, [latex]d>1[/latex], то, подставив [latex]x[/latex] в [latex](2)[/latex] и умножив обе части на [latex]d^{n-1}[/latex] , мы придём к противоречию.Но и целым [latex]x[/latex] тоже быть не может: и при чётном, и при нечётном [latex]x[/latex] левая часть — четная (в последнем случае два крайние числа нечётны, а остальные чётны), а [latex]c[/latex] — нечётно. Полученное противоречие доказывает, что [latex]x[/latex] (и любой из остальных корней уравнения (1) с чётными [latex]b[/latex], и нечётным [latex]c[/latex]) может быть только иррациональным.
Про [latex]n[/latex] чисел, произведение которых равно [latex]p[/latex], известно, что разность между [latex]p[/latex] и каждым из этих чисел — нечётное целое число. Докажите, что все эти числа иррациональны.
Решение:
Пусть x — одно из этих n чисел. [latex]x+b_{1} , x+b_{2}, … , x+b_{n-1}[/latex] — остальные и
[latex] p = x(x+b_{1})(x+b_{2})…(x+b_{n+1})=x+c, (1)[/latex]
где, по условию, [latex]c[/latex] нечётно, а [latex]b_{1} , b_{2}, … , b_{n-1}[/latex] должны быть чётными целыми числами. Равенство [latex](1)[/latex] можно записать, раскрыв скобки в виде
где [latex]a_{1},…,a_{n-2} [/latex] — чётные, а [latex]a_{n-1}=b_{1}b_{2}…b_{n-1}-1[/latex] и [latex]c[/latex] — нечётные числа.Предположив, что [latex]x[/latex] — рациональное число, мы сразу же убедимся, что [latex]x[/latex] должно быть целым:если [latex]x=k/d[/latex] — несократимая дробь, [latex]d>1[/latex], то, подставив [latex]x[/latex] в [latex](2)[/latex] и умножив обе части на [latex]d^{n-1}[/latex] , мы придём к противоречию.Но и целым [latex]x[/latex] тоже быть не может: и при чётном, и при нечётном [latex]x[/latex] левая часть — четная (в последнем случае два крайние числа нечётны, а остальные чётны), а [latex]c[/latex] — нечётно. Полученное противоречие доказывает, что [latex]x[/latex] (и любой из остальных корней уравнения (1) с чётными [latex]b[/latex], и нечётным [latex]c[/latex]) может быть только иррациональным.
Под методом математической индукции понимают следующий способ доказательства: если требуется доказать истинность утверждения $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 $ (база индукции) получаемые множества оставшихся лошадей не будут пересекаться, и утверждение о равенстве цветов всех лошадей сделать нельзя.
