Игра с «доминошками». Дана клетчатая доска 10×10. За ход разрешается покрыть любые две соседние клетки доминошкой (прямоугольником размером 1×2) так, чтобы доминошки не перекрывались. Проигрывает тот, кто не может сделать ход.

   Решение

Тема:    [ Невыпуклые многоугольники ]

Сложность: 5 Классы: 9,10

Прислать комментарий

Условие

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

Решение

Докажем это утверждение индукцией по n. При n = 3 оно очевидно. Предположим, что утверждение доказано для всех k-угольников, где k < n, и докажем его для любого n-угольника. Любой n-угольник можно разрезать диагональю на два многоугольника (см. задачу 22.20, а)), причем число вершин у каждого из них строго меньше n, т. е. их можно разрезать на треугольники по предположению индукции.

Источники и прецеденты использования