МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Индукция 1

Допустим, мы хотим доказать, что каждое третье целое число делится на три. Как это делать? Вот 6 делится на три, в результате 2 будет. 9 тоже, ведь это \(6+3\), значит после деления будет \(2+1\). И \(12\) — это \(9+3\), значит после деления будет \(2+1+1\). Ну и так далее. В этом случае это «и так далее» отлично сработало, задача решена. К сожалению, есть случаи, когда говоришь «и так далее», но в итоге получается не решение, а какая-то ерунда (пример можно посмотреть в конце листка). Для того, чтобы этот метод давал всё время правильные результаты, математики сделали его более формальным. Сейчас он называется математической индукцией, разберём его на примере:

1.

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

Доказательство. База. Если прямая одна, то частей всего две, так что просто красим их, одну в белый, другую в чёрный.

Шаг. Допустим, для какого-то количества прямых мы умеем раскрашивать плоскость. Что делать, если прямых на единицу больше? Сотрём одну из них и раскрасим плоскость, как будто её и не было (мы ведь допустили, что уже умеем это). Теперь снова добавим её. Получится, что все соседние части по-прежнему разного цвета, за исключением тех, которые до добавления прямой составляли одну часть. Как это исправить? Достаточно перекрасить на противоположный цвет все части, которые находятся по одну сторону от этой прямой, тогда условие будет выполняться.

Теперь, если нас интересует случай, например, 47 прямых, то разобрать его можно так: сначала берём базу, она про случай из 1 прямой. Применим шаг, получим случай для 2 прямых. Применяем шаг ещё 45 раз, получаем интересующий нас случай 47 прямых. Получается, для любого числа прямых мы можем построить решение, надо лишь сделать достаточно шагов.

В общем, метод математической индукции выглядит так:

1. База. Разбор какого-то одного случая, как правило для 0 или 1.
2. Шаг. То, как пользуясь уже разобранными случаями, разобрать следующий.
3. Подумать, действительно ли до любого случая можно дойти от базы, используя шаги.

2.

Ханойская башня.

а)

Есть три жерди — две пустые, а на третей пирамидка из дисков. В пирамидке на каждом диск лежит диск меньшего размера. Разрешается перекладывать по одному диску с одной жерди на другую при условии, что диск кладут или на больший диск, или на пол. Докажите, что можно перетащить все диски с третьей жерди на первую.

б)

Как сделать это за \(2^n-1\) перекладываний (\(n\) — количество дисков)?

3.

У бородатого многоугольника во внешнюю сторону растет щетина. Его пересекает несколько прямых, на каждой из которых с одной из сторон тоже растет щетина. В результате многоугольник оказался разбитым на некоторое число частей. Докажите, что хотя бы одна из частей окажется бородатой снаружи.

4.

Докажите, что:

a)

\(1+3+5+\ldots+(2n-1)=n^2\);

б)

\(1+2+3+\ldots+n=\frac{n(n+1)}{2}\);

в)

\(1^3+2^3+ \ldots +n^3 = \frac{1}{4}n^2(n + 1)^2\).

5.

Докажите, что произведение всех чисел от \(n+1\) до \(2n\) делится на \(2^n\), но не делится на \(2^{n + 1}\).

6.

Известно, что число \(x+1/x\) — целое. Докажите, что и число \(x^n+1/x^n\) тоже целое.

7.

Как соединить 50 городов наименьшим числом авиалиний так, чтобы из любого города можно было попасть в любой, сделав не более одной пересадки?

Hint

Hint. Найти пример легко, индукция понадобится для доказательства того, что он наилучший.

8.

На какое количество частей 100 прямых общего положения (не параллельны друг другу, никакие три не пересекаются в одной точке) разбивают плоскость?

9.

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

10.

Докажите, что доказанное утверждение неверно и тем самым продемонстрируйте превосходство индукции над «и так далее». Докажем, что для любого натурального \(n\) число \(n^2+n+41\) простое (не делится ни на что, кроме 1 и себя). При \(n=1\) получается 43 — простое. При \(n=2\) — 47, тоже простое. \(n=3\), 53 — простое. 61 — простое, 71 — простое, 83, 97, 113, 131, 151 — все простые. Ну и так далее.

Hint

Hint. Выписывать все значения подряд, пока не будет составное, в принципе можно, но это минут 20 займёт и не обойдётся без ошибок. Лучше подумать.