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

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

Занятие 3 (22 октября 2016 года). Метод математической индукции

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

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

Задачи:

1.

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

2.

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

3.

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

4.

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

a)

4×4;

б)

8×8

в)

2ⁿ × 2ⁿ

5.

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

6.

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

7.

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