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

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

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

Пусть доминошки выставлены на ребро друг за другом. Нам необходимо доказать следующий факт: „Если толкнуть 1-ю доминошку, то для любого сколь угодно большого N доминошка с номером N когда-нибудь упадёт”.

Для доказательства понадобится установить верность 2-х утверждений:
1) База: мы можем толкнуть первую доминошку и она упадёт.
2) Переход: если падает доминошка с номером k, то она толкает доминошку с номером (k + 1).

Вводные задачи

1.

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

2.

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

1 + 2 + … + n ≤ n².

Основные задачи:

1.

Задача про Ханойские башни: есть три стержня и несколько колец разного размера (изначально все кольца на одном стержне). Класть можно только кольцо меньшего размера на кольцо большего размера. Можно ли переместить всю башню с одного стержня на другой, если колец всего а) 2 кольца, б) 3 кольца, в) 5 колец, г) n колец?

2.

Рассмотрим уголок из трёх клеток. Можно ли разрезать на такие уголки квадрат следующих размеров без одной клетки (вырезана может быть любая клетка квадрата, даже откуда-то из середины)?

a)

4×4;

б)

8×8;

в)

2ⁿ × 2ⁿ.

3.

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

4.

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

5.

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

6.

На какую максимальную степень тройки делится число, десятичная запись которого состоит из 3ⁿ единиц?

7.

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