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

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

Занятие 17

Индукция

1.

Докажите неравенство: 2ⁿ > n.

2.

Известно, что x + ¹/_x целое число. Докажите, что xⁿ + ¹/_(xⁿ) — также целое при любом целом n.

3.

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

4.

Докажите тождество: 1 + 3 + 5 +...+ (2n − 1) = n².

5.

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

6.

Что больше: 1 + 2 + 4 + 8 + 16 + 32 + 64 или 128? 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 или 2048? 1 + 2 + 4 + ... + 2n или 2n + 1?

7.

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