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

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

Руководитель Михаил Владимирович Шеблаев
2010/2011 учебный год

Занятие 17

Индукция

1.
Докажите неравенство: 2n > n.
2.
Известно, что x + 1/x целое число. Докажите, что xn + 1/(xn) — также целое при любом целом 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.
У бородатого многоугольника во внешнюю сторону растет щетина. Его пересекает несколько прямых, на каждой из которых с одной из сторон тоже растет щетина. В результате многоугольник оказался разбитым на некоторое число частей. Докажите, что хотя бы у одной из частей вся борода окажется снаружи.