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

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

Занятие 4. И снова индукция.

1.

Докажите, что при любом натуральном n:

a)

\(1+2+...+n=\frac{n(n+1)}{2}\);

a)

\(1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}\);

a)

\(1^3+2^3+...+n^3=(1+2+...+n)^2\).

2.

Через точку, отмеченную на плоскости, провели n различных прямых. Докажите, что эти прямые разбивают плоскость на 2n областей.

3.

Докажите, что при всех натуральных n:

a)

\(10^n+18n-1\) делится на 27;

б)

\(2^{5n+3}+5^n\cdot3^{n+2}\) делится на 17;

в)

\(2^{(3^n)}+1\) делится на \(3^n\);

4.

Откуда–то стало известно, что \(x+\frac{1}{x}\) — целое число. Докажите, что число \(x^n+\frac{1}{x^n}\) при любом целом n тоже является целым.

5.

При помощи индукции докажите бином Ньютона: \((a+b)^n=C^{0}_n\cdot a^n+C^1_n\cdot a^{n-1}\cdot b+...+C^k_n\cdot a^{n-k}\cdot b^{k}+...+C^{n-1}_n\cdot a\cdot b^{n-1}+C^n_n\cdot b^n\).

6.

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

7.

Докажите, что для любых натуральных n:

a)

\(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}\ge\sqrt{n}\);

б)

\(2!\cdot4!\cdot...\cdot(2n)!\ge((n+1)!)^n\).

8.

Двум гениальным математикам выдали по карточке с натуральным числом. Они знают лишь то, что эти числа отличаются на 1. После чего они по очереди говорят, знают ли они число на карточке другого. Докажите, что рано или поздно один из математиков скажет «знаю».

9.

Захватив добычу, n разбойников пытаются её поделить. У каждого из них свое мнение о ценности той или иной доли добычи, и каждый из них хочет получить не меньше, чем \(1/n\) долю добычи (со своей точки зрения). Придумайте, как разделить добычу между разбойниками.

10.

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