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

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

Занятие 4. Индукция (12–08 special edition).

• Докажите, что при любом натуральном n:
  а) \(1+2+...+n=\frac{n(n+1)}{2}\);
  б) \(1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}\);
  в) \(1^3+2^3+...+n^3=(1+2+...+n)^2\).


• Докажите, что квадрат можно разрезать на любое число квадратов (не обязательно одинаковых), начиная с шести.


• На плоскости проведены n прямых, среди которых никакие две не параллельны и никакие три не пересекаются в одной точке. Докажите, что области, на которые эти прямые разбивают плоскость, можно покрасить в два цвета «в шахматном порядке», то есть так, чтобы любые две соседние по стороне части были разных цветов.

1.

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

a)

\(1\cdot 1! + 2 \cdot 2! + ... + n \cdot n! = (n + 1)! - 1;\)

б)

\(\left(1 - \frac{1}{4}\right) \left(1 - \frac{1}{9}\right) \left(1 - \frac{1}{16}\right) ... \left(1 - \frac{1}{n^2}\right) = \frac{(n+1)}{2 n}.\)

2.

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

3.

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

4.

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

a)

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

б)

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

в)

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

5.

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

6.

Докажите, что для любых натуральных 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\).

7.

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

8.

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