Таблицы Брадиса

База утверждение для треугольника очевидна.

База утверждение для треугольника очевидна.

Элементы математики в задачах - Г. А. Мерзон

в)  п! > 2п, п + 1 > 2^ (п +1)! > 2п+1.

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

Решение. База — утверждение для треугольника — очевидна.

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

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

116                      Метод математической индукции

Обобщенный принцип математической индукции. Пусть задана последовательность утверждений А1, А2,..., Ак,... Известно, что:

1)  (база индукции) первое утверждение истинно,

2)   (шаг индукции) из истинности утверждений А1, А2,..., Ап сле­дует истинность утверждения Ап+1.

Тогда все утверждения истинны.

Задача 13*. Докажите обобщенный принцип математической индук­ции.

Решение. Достаточно заметить, что обобщенный принцип математи­ческой индукции для последовательности утверждений Ак в точности совпадает с принципом математической индукции для последова­тельности утверждений Вк: «утверждения Аг, ..., Ак верны».