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

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

Ликвидация безграмотности!

Индукция, Ватсон! 25 сентября 2010 года

1.

a)

Из квадрата клетчатой бумаги размером 4×4 вырезали угловую клетку. Докажите, что полученную фигуру можно разрезать на уголки из трех клеток.

b)

То же для квадрата 8×8.

c)

То же для квадрата 16×16.

d)

То же для квадрата 2ⁿ×2ⁿ.

2.

Игра «Ханойская башня». Имеется пирамида с 10 кольцами возрастающих размеров (внизу — самое большое) и еще два пустых стержня той же высоты. Разрешается перекладывать верхнее кольцо с одного стержня на другой, но при этом запрещается класть большее кольцо на меньшее. Докажите, что можно переложить все кольца с первого стержня на один из пустых стержней.

Часто требуется доказать утверждение типа: „Для каждого натурального n верно, что ...”. Такое утверждение можно рассматривать, как цепочку утверждений „Для n = 1 верно, что ...”, „Для n = 2 верно, что ...” и т.д.

Метод математической индукции состоит в том, чтобы доказать первое из этих утверждений (называемое базой или основанием индукции), что обычно достаточно просто сделать, а затем доказать шаг (или переход) индукции: „Если верно утверждение с номером n, то верно утверждение с номером (n + 1)”.

Если верна база индукции и верен шаг индукции, то все утверждения верны.

Иногда для доказательства очередного утверждения цепочки надо опираться на все предыдущие утверждения. Тогда индуктивный переход звучит так: „Если верны все утверждения с номерами от 1 до n, то верно и утверждение с номером (n + 1)”.

Пример. Докажите, что для всякого натурального n выполнено равенство:

Доказательство.
База. n = 1: 1 = ^1·2/₂ — очевидно.
Переход. Пусть верно утверждение с номером n, докажем его для n + 1. По предположению индукции верно равенство:

3.

Последовательность a_n задана правилом: a₁ = 1, a₂ = 5, а каждый член, начиная с третьего, вычисляется по формуле a_{n + 1} = 3a_n + 2. Докажите, что a_n = 3ⁿ − 1.

4.

Плоскость поделена на части несколькими прямыми. Докажите, что эти части можно раскрасить в черный и белый цвет так, чтобы любые две соседние части были раскрашены в различные цвета (соседние части – это те, которые имеют общий участок границы).

5.

Докажите, что в игре «Ханойская башня» для n колец достаточно 2ⁿ − 1 перекладывания.

6.

Докажите, наконец, что для любого натурального n выполнено тождество:

1·2 + 2·3 + ... + (n − 1)·n	=	(n − 1)n(n + 1)	.
		3

7.

Докажите неравенство Бернулли: для любого натурального n и для любого действительного α ≥ −1 выполнено неравенство: (1 + α)ⁿ ≥ 1 + nα

8.

Клетки доски 100×100 раскрашены в 4 цвета так, что в каждом квадратике 2×2 встречаются клетки всех цветов. Докажите, что и среди угловых клеток встречаются клетки всех цветов.

9.

Докажите, что если x + ¹/_x — целое число, то при любом натуральном n число xⁿ + ¹/_xⁿ также целое.

10.

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