Олимпиадная задача: Связные части диагоналей в квадрате 8×8 — теория графов, 6-8 класс
Задача
В каждой клетке квадрата 8×8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть
а) больше 15?
б) больше 20?
Решение
б) На рисунке приведён пример, где число частей равно 21. Одна из них – многосвязная "оконная рама", в ячейках которой помещаются одиночные диагонали.
Ответ
Может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет