Олимпиадная задача по комбинаторной геометрии и теории графов для 8-9 классов от Акулича И. Ф.
Задача
Какое наибольшее число клеток доски 9×9 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?
Решение
Пусть разрезано k клеток. Рассмотрим граф, рёбрами которого являются половинки проведённых диагоналей, а вершинами – вершины и центры разрезанных клеток.
Поскольку граничные клетки доски, очевидно, разрезать нельзя, то в полученном графе не более 64 + k вершин и 4k рёбер. Согласно формуле Эйлера (см. задачу 130759) (64 + k) – 4k + 1 ≥ 2, то есть k ≤ 21.
Пример с 21 разрезанной клеткой см. на рисунке.
Ответ
21 клетку.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет