Таблицы Брадиса

Действительно, рассмотрим множество целых чисел.

Действительно, рассмотрим множество целых чисел.

Элементы математики в задачах - Г. А. Мерзон

Решение. а) Ответ: нет. Действительно, рассмотрим множество целых чисел. Оно является своим подмножеством. От противного докажем, что в нем нет наименьшего элемента: пусть во множестве целых чисел есть наименьший элемент п. Но элемент п — 1 также лежит во множестве целых чисел, и при этом он меньше, чем п. Получили противоречие.

б)  Ответ: нет. Доказательство аналогично.

Задача 2. На острове Буяне все страны треугольной формы. Если две страны граничат, то по целой стороне. Докажите, что страны можно раскрасить в 3 цвета так, что соседние по стороне страны будут окрашены в разные цвета.

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

Решение. Воспользуемся аксиомой наименьшего элемента. Этот метод также носит название «метода наименьшего контрпримера». Пусть существует хотя бы один остров, не удовлетворяющий условию задачи, то есть такой, что его нельзя раскрасить требуемым способом. Выберем из всех таких островов остров В с наименьшим числом стран (если таких несколько —возьмем любой из них). Пусть число стран на В равно п > 1. Тогда для любого острова, на котором не больше п — 1 страны, утверждение задачи выполняется.

Возьмем страну, имеющую выход к морю, то есть граничащую с ним по крайней мере по одной стороне. Очевидно, у нее не более двух соседей. Теперь рассмотрим «остров», состоящий из всех стран на В, кроме этой страны. На нем меньше п стран, а значит, мы можем раскрасить их в 3 цвета так, что соседние по стороне страны будут окрашены в разные цвета. Остается только выбрать цвет для отброшенной нами страны. Если у нее один сосед, окрашенный в некоторый цвет, то мы просто красим эту страну в любой другой цвет и получаем нужную раскраску. Если соседних стран две, то мы красим нашу страну в оставшийся третий цвет и получаем требуемую раскраску.