математическая индукция

1. Математическая индукция. Скопинцев С.

2. Наряду с дедукцией, понятием, которое всем знакомо, существует понятие индукции – перехода от частных примеров к общим закономерностям. Разберём сегодня, что такое математическая индукция.

3. Математическая индукция – метод доказательства утверждений вида: « Для каждого натурального n верно, что…» Такое утверждение можно рассматривать как цепочку утверждений: « Для n = 1 верно, что…», «Для n =2 верно, что…» и т. д. Рассмотрим пример.

4. «Шахматная» плоскость. Задача. Несколько прямых делят плоскость на части. Доказать, что можно раскрасить её в два цвета так, чтобы соседние части имели разный цвет (как на рисунке.)

5. Рассмотрим сначала ситуацию, когда прямая одна. Тогда мы легко можем раскрасить. С двумя прямыми п олучаем четыре части. А как быть, если мы проведем еще одну прямую?

6. Эта прямая поделит некоторые участки, и с обеих сторон от неё будут одинаковые цвета. Тогда поменяем все цвета с одной стороны от прямой Новый рисунок будет иметь уже правильную раскраску.

7. Аналогично мы можем добавлять еще прямые. Как же теперь решить задачу? Сотрем все прямые с плоскости, но запомним их расположение. Затем будем восстанавливать прямые по одной описанным способом, пока не получим искомый рисунок. Пришло время уточнить, что такое принцип математической индукции.

8. Определение. База индукции – первое утверждение цепочки . ( Т. е. «Для n = 1 верно, что…») Оно проверяется непосредственно. Далее следует предположение индукции. («Пусть для n = k утверждение верно.») Остаётся доказать индукционный переход: «Если верно утверждение с номером k , то верно и утверждение с номером k+1 . » Тогда утверждение оказывается верным для всех натуральных чисел.

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

10. Решаем индукцией по n - количеству человек . База индукции: n = 2 – верно. (Действительно, оба сделали по одному рукопожатию.) Предположение: пусть для n = k утверждение верно. Переход: проверим утверждение для n = k + 1 .

11. Уберем из рассмотрения одного человека и все рукопожатия с ним. Без него утверждение выполнено по предположению. Рассмотрим по очереди все рукопожатия выбранного нами человека. Возможны три различных варианта: Жмут друг другу руки два «нечётных» человека. Тогда оба они становятся «чётными», и количество «нечётных» уменьшается на 2 . ( Чётность количества не меняется.)

12. Аналогично при встрече двух «чётных» людей. Количество «нечётных» увеличивается на 2, и его чётность не меняется. При встрече «чётного» с «нечётным», они меняются чётностью, и количество нечётных не изменяется. Тем самым чётность числа «нечётных» людей не меняется, и мы доказали переход. В соответствии с принципом математической индукции задача доказана.

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

14. Задачи для отработки. Ханойская башня. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Необходимо перенести пирамиду за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее . Для любого натурального k докажите, что 2 k > k. Показать , что любую сумму, начиная с 8 копеек, можно уплатить монетами в 3 и 5 копеек .

15. В городе N домов. Какое наибольшее число заборов можно построить, если: 1) заборы не пересекаются, 2) каждый забор огораживает хотя бы один дом, 3) никакие два забора не огораживают одну и ту же совокупность домов? Докажите, что простых чисел бесконечно много. Докажите, что . На краю пустыни имеется большой запас бензина и машина, которая при полной заправке может проехать 50 километров. Имеются ( в неограниченном количестве) канистры, в которые можно сливать бензин из бензобака машины и оставлять на хранение (в любой точке пустыни). Доказать , что машина может проехать любое расстояние. (Канистры с бензином возить не разрешается, пустые можно возить в любом количестве.)  

16. Иногда для доказательства очередного утверждения цепочки надо опираться на все предыдущие утверждения. Тогда переход звучит так: «Если верны все утверждения с номерами от 1 до n , то верно утверждение с номером n + 1 ». Бывает удобен индуктивный спуск – если утверждение с номером n (n > 1) можно свести к одному или нескольким утверждениям с меньшими номерами и первое утверждение верно, то все утверждения верны.

17. Рекомендуемая литература. А. Я. Канель -Белов, А. К. Ковальджи «Как решают нестандартные задачи» А. Х. Шень «Математическая индукция»