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

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

Занятие 11 (24 ноября 2012 года)

1.

Незнайка должен был разрезать квадрат на 1000 квадратов. Но после тщательного подсчёта оказалось, что он разрезал не на 1000, а на 997 квадратов. Помогите Незнайке исправить ситуацию и получить ровно 1000 квадратов.

2.

Вначале на доске было написано некоторое число, через секунду вместо него появилось второе, и затем каждую секунду на доске появлялось новое число. Со временем Незнайка заметил закономерность: для всех n, начиная с n = 3000, n-ое число, появлявшееся на доске, было ровно на (2n − 1) больше предыдущего. Незнайка увидел, что 3798-ое число равно (3798)². Чему будет равно а) 3799-ое, б) 3801-ое число, если замеченная Незнайкой закономерность сохранится?

Индукция

Пусть требуется доказать утверждение типа: „Для каждого натурального n верно, что...”. Это всё равно, что доказать бесконечную цепочку утверждений „Для n = 1 верно, что...”, „Для n = 2 верно, что...”, ......, „Для n = 3799 верно, что...” и так далее.

Метод математической индукции состоит в том, чтобы доказать первое из этих утверждений (называемое базой индукции), а затем доказать шаг (или переход): „Если верно утверждение № n, то верно утверждение № (n + 1)”. Если верны база индукции и шаг индукции, то все утверждения верны.

3.

Докажите, что для каждого n верно утверждение: сумма натуральных чисел от 1 до n равна \(\frac{n(n+1)}{2}\).

4.

Неравенство треугольника гласит, что для любых трёх точек A₁,A₂,A₃ выполнено: A₁A₂ + A₂A₃ ≥ A₁A₃. Докажите, что для любого n длина n-звенной ломаной не меньше длины отрезка между её концами.

5.

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

6.

Незнайке сообщили некоторое число a. Он вычислил n чисел: \[a + \frac{1}{a}, a^2 + \frac{1}{a^2}, a^3 + \frac{1}{a^3}, \ldots,a^{n-1}+\frac{1}{a^{n-1}}, a^n + \frac{1}{a^n}\mbox{,}\] и все они оказались целыми. Незнайка очень устал. Помогите ему доказать, что \(a^{n+1}+\frac{1}{a^{n+1}}\) тоже целое.

7.

Отвлекитесь от индукции — сравните площадь трёх фигурок.

Дополнительные задачи

8.

Докажите, что 4ⁿ + 15n − 1 при любом натуральном n делится на 9.

9.

На доске написаны сто цифр: нули и единицы (в произвольной комбинации). Разрешается выполнять две операции: (1) заменять первую цифру (нуль на единицу и наоборот); (2) заменять цифру, стоящую после первой единицы. Например, в последовательности 0011001... можно заменить первую цифру или четвёртую. Докажите, что с помощью нескольких таких замен можно получить любую комбинацию из ста нулей и единиц.

10.

Докажите по индукции, что произведение любых n последовательных натуральных чисел делится на n! (через n! — „n факториал” — обозначается произведение чисел от 1 до n).

11.

Чему равна сумма \(1 \cdot n + 2\cdot (n-1) + \ldots + (n-1)\cdot 2 + n\cdot 1\)?

12.

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