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

Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.