ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98618
Темы:    [ Разрезания (прочее) ]
[ Планарные графы. Формула Эйлера ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

Какое наибольшее число клеток доски 9×9 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?


Решение

  Пусть разрезано k клеток. Рассмотрим граф, рёбрами которого являются половинки проведённых диагоналей, а вершинами – вершины и центры разрезанных клеток.
  Поскольку граничные клетки доски, очевидно, разрезать нельзя, то в полученном графе не более  64 + k  вершин и 4k рёбер. Согласно формуле Эйлера (см. задачу 30759)  (64 + k) – 4k + 1 ≥ 2,  то есть  k ≤ 21.
  Пример с 21 разрезанной клеткой см. на рисунке.


Ответ

21 клетку.

Замечания

7 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант весенний тур, основной вариант, 8-9 класс
Задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .