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

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

Листок 6. Опять индукция!

1.

a)

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

b)

Доказать, что в случае 4-х монет (фальшивая по-прежнему одна) хватит двух взвешиваний.

c)

А в случае 2ⁿ монет достаточно n взвешиваний.

2.

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

3.

Доказать, что при любом натуральном n и положительном a справедливы неравенства:
a) (1+a)ⁿ ≥ 1 + na;
b) (1+a)ⁿ ≥ 1 + aⁿ;

4.

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

5.

Доказать, что при любом натуральном n справедливо равенство:
1 + 2 + 3 + ... + n = ^{n(n + 1)}/₂

6.

На плоскости проведено несколько прямых. Никакие две из них не параллельны и никакие три не пересекаются в одной точке.
a) На сколько частей разбивается плоскость, если таких прямых проведено 2? 3? 4?
b) А если прямых n?

7.

Доказать, что следующие числа делятся на 3 при любом натуральном n:
a) 7ⁿ − 1;
b) 5ⁿ − 2ⁿ.

8.

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