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

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

Руководители А. С. Воропаев, П. С. Дергач, Ф. И. Мамедова и Ю. А. Цимбалов
2011/2012 учебный год

Индукция 2

Теорию смотри в предыдущем листке. А теперь можно порешать задачи:

Докажите, что сумма кубов трёх последовательных натуральных чисел кратна \(9\).

Докажите, что произведение всех чисел от \(n+1\) до \(2n\) делится на \(2^n\), но не делится на \(2^{n + 1}\).

Ханойская башня.

а): Есть три жерди — две пустые, а на третей пирамидка из дисков. В пирамидке на каждом диск лежит диск меньшего размера. Разрешается перекладывать по одному диску с одной жерди на другую при условии, что диск кладут или на больший диск, или на пол. Докажите, что можно перетащить все диски с третьей жерди на первую.
б): Как сделать это за \(2^n-1\) перекладываний (n — количество дисков)?

Докажите, что в предыдущей задаче не справиться быстрее, чем за \(2^n-1\) перекладываний.

Известно, что число \(x+1/x\) — целое. Докажите, что и число \(x^n+1/x^n\) тоже целое.

В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает ее вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.

Петя умеет на любом отрезке отмечать точки, которые делят этот отрезок пополам или в отношении \(n:(n + 1)\), где \(n\) — любое натуральное число. Петя утверждает, что этого достаточно, чтобы на любом отрезке отметить точку, которая делит его в любом заданном рациональном отношении. Прав ли он?

Придумайте, как упростить выражение \(\frac{1}{1 \cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3 \cdot 4} + ... + \frac{1}{(n - 1)n}\).

Найдите ошибку в доказательстве:

Утверждение. У всех людей глаза одинакового цвета.

Доказательство. Докажем, что в компании из \(n\) людей у всех глаза одинакового цвета. При \(n = 1\) утверждение очевидно.

Предположим, что оно верно при \(n = k\). Докажем, что тогда оно верно и для \(n = k + 1\). Итак, пусть перед нами \(k + 1\) человек. Перенумеруем их: первый, второй, третий, …, \(k\)-й, \((k + 1)\)-й. По предположению, у любых \(k\) из этих людей глаза одинакового цвета. Значит, у первого, второго, …, \(k\)-го — глаза одинакового цвета.

Возьмём теперь другую группу из \(k\) человек: второй, третий, …, \(k\)-й, \((k + 1)\)-й. У них тоже глаза одинакового цвета. В обеих группах присутствовал второй человек. Значит у всех глаза того же цвета, что и у второго, то есть у всех одинаковые.

10.

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

11*.

а): Разобьём отрезок длиной \(3^n\) на три равные части. Первую и третью из них назовём отмеченными. Каждый из отмеченных отрезков разобьём на три части, из которых первая и третья снова назовём отмеченными и т.д. до тех пор, пока не получатся отрезки длиной 1. Концы всех отмеченных отрезков называются отмеченными точками. Доказать, что для любого целого \(k\) (\(1\leq k \leq3^n\)) можно найти две отмеченные точки, расстояние между которыми равно \(k\).
б): Докажите это же для любых \(k\) от 1 до \(3^n\), не обязательно целых.

12*.

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

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!