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

Кружок 8 класса

Задание 8 - Индукция

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

Часть 1. Вспомни

1.

Ханойские башни. Есть три стержня и несколько колец разного размера. Класть можно только кольцо меньшего размера на кольцо большего размера. Можно ли переместить пирамидку с одного стрежня на другой, если в пирамидке:

a)

2 кольца;

b)

3 кольца;

c)

5 колец;

d)

n колец.

2.

Рассмотрим уголок.

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

a)

4*4

b)

8*8

c)

128*128

d)

2ⁿ*2ⁿ

3.

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

Часть 2. Придумай

4.

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

5.

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

a)

2ⁿ > n

b)

1 + 2 + … + n ≤ n²

6.

Докажите, что для произвольного натурального n верно равенство: 1 + 3 + … + (2n − 1) = n²

7.

В пробирке живут амёбы. Каждую минуту происходит следующее: каждая амёба делится пополам, после чего в пробирку добавляют еще одну такую же амёбу. В начальный момент времени там была всего одна амёба. Докажите, что через n минут в пробирке будет 2^{n + 1} − 1  амёба.

8.

Ханойские башни. За какое минимальное число перекладываний можно переместить пирамидку с одного стержня на другой.

9.

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

10.

10.Доказать, что для любого натурального n сумма углов в выпуклом (n + 2)-угольнике равна n * 180.