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

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

Руководители А. В. Антропов, М. А. Лимонов и А. Ю. Шапцев
2010/2011 учебный год

Версия для печати

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

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

1.
a)
Из квадрата клетчатой бумаги размером 4×4 вырезали угловую клетку. Докажите, что полученную фигуру можно разрезать на уголки из трех клеток.
b)
То же для квадрата 8×8.
c)
То же для квадрата 16×16.
d)
То же для квадрата 2n×2n.
2.
Игра «Ханойская башня». Имеется пирамида с 10 кольцами возрастающих размеров (внизу — самое большое) и еще два пустых стержня той же высоты. Разрешается перекладывать верхнее кольцо с одного стержня на другой, но при этом запрещается класть большее кольцо на меньшее. Докажите, что можно переложить все кольца с первого стержня на один из пустых стержней.

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

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

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

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

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

1 + 2 + ... + n = n(n + 1) .
2

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

1 + 2 + ... + n = n(n + 1) .
2
Имеем:
1 + 2 + ... + n + (n + 1) = n(n + 1) + (n + 1) = n² + n + 2n + 2 = (n + 1)(n + 2) .
222
Переход доказан.

3.
Последовательность an задана правилом: a1 = 1, a2 = 5, а каждый член, начиная с третьего, вычисляется по формуле an + 1 = 3an + 2. Докажите, что an = 3n − 1.
4.
Плоскость поделена на части несколькими прямыми. Докажите, что эти части можно раскрасить в черный и белый цвет так, чтобы любые две соседние части были раскрашены в различные цвета (соседние части – это те, которые имеют общий участок границы).
5.
Докажите, что в игре «Ханойская башня» для n колец достаточно 2n − 1 перекладывания.
6.
Докажите, наконец, что для любого натурального n выполнено тождество:
1·2 + 2·3 + ... + (n − 1)·n = (n − 1)n(n + 1) .
3
7.
Докажите неравенство Бернулли: для любого натурального n и для любого действительного α ≥ −1 выполнено неравенство: (1 + α)n ≥ 1 + nα
8.
Клетки доски 100×100 раскрашены в 4 цвета так, что в каждом квадратике 2×2 встречаются клетки всех цветов. Докажите, что и среди угловых клеток встречаются клетки всех цветов.
9.
Докажите, что если x + 1/x — целое число, то при любом натуральном n число xn + 1/xn также целое.
10.
На плоскости даны n прямых общего положения (это значит, что никакие две не параллельны и никакие три не проходят через одну точку). На сколько частей они разбивают плоскость?

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS