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

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

Занятие 17 (12 марта 2016 года). Индукция

1.

Из квадрата клетчатой бумаги размером 16×16 вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на "уголки" из трёх клеток. Придумайте обобщение этой задачи.

Принцип математической индукции состоит в следующем:
Пусть есть утверждение, зависящее от натурального числа \(n\), обозначим его \(P(n)\). Тогда, если:

1. верно утверждение \(P(1)\) (база индукции);
2. для любого натурального числа \(k\) из утверждения \(P(k)\) следует утверждение \(P(k+1)\), (индукционный переход, или шаг математической индукции),

2.

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

а)

можно переложить все кольца с первого стержня на один из пустых стержней;

б)

это можно сделать за \(2^n - 1\) перекладываний.

3.

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

4.

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

5.

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

6.

Докажите, что при любых натуральных n выполняется равенство: \[1 + 3 + 5 + \ldots + (2n - 1) = n^2.\]

7.

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

8.

В концах диаметра окружности стоят единицы. На первом шаге каждая из получившихся дуг делится пополам, и в её середине пишется сумма чисел, стоящих в концах. Затем то же самое делается с каждой из четырёх полученных дуг и т.д. Такая операция проделывается \(n\) раз. Найти сумму всех полученных чисел.

9.

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