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

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

Занятие 15. Индукция

Чтобы доказать все эти утверждения, достаточно проверить, что:

1. У₁ истинно (база индукции)
2. для каждого k: если истинно У_k, то истинно и У_k+1 (шаг индукции).

1.

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

a)

1 + 2 + 3 + … + n = n · (n + 1)/2;

б)

1 + 3 + 5 + … + (2n − 1) = n ².

2.

a)

В клетчатом квадрате n×n закрасили все клетки на главной диагонали и все клетки, лежащие ниже главной диагонали. Сколько всего клеток было закрашено?

б)

На плоскости проведено n прямых. Никакие две из них не параллельны, никакие три не пересекаются в одной точке. На сколько частей эти прямые делят плоскость?

в)

Коля рисует на клетчатой бумаге пирамидку: в первом сверху ярусе одна клетка, во втором — три, в третьем— пять, в четвёртом — семь, и так далее. Сколько всего клеточек будет в первых 20 ярусах пирамидки? Указание. Подумайте, как эта задача связана с предыдущей.

3.

a)

Докажите, что с помощью монет в 3 и 5 тугриков можно уплатить любую сумму в целое число тугриков, начиная с 8.

б)

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

в)

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

4.

a)

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

б)

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

5.

Дан клетчатый квадрат с длиной стороны 2ⁿ. Из него вырезали:

a)

угловую клетку;

б)

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

6.

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

7.

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

a)

1² + 2² + 3² + … + n² = n · (n + 1) · (2n + 1)/6;

б)

1·2 + 2·3 + 3·4 + … + (n−1)·n = (n−1) · n · (n + 1).