|
|
 |
Условие
На листе бумаги проведено 11 горизонтальных и 11 вертикальных прямых, точки пересечения которых называются узлами, звеном" мы будем называть отрезок прямой, соединяющий два соседних узла одной прямой. Какое наименьшее число звеньев надо стереть, чтобы после этого в каждом узле сходилось не более трёх звеньев?
Решение
Оценка. Назовём узел внутренним, если изначально он принадлежит четырём звеньям. Внутренние звенья образуют квадрат 9×9, поэтому их количество равно 81. Для каждого внутреннего узла мы должны стереть хотя бы одно содержащее его звено, при этом каждое из таких звеньев мы посчитаем
не более двух раз. Следовательно, количество стёртых звеньев не менее 41.
Пример: сотрём все звенья на горизонтальных прямых с 2-й по 10-ю, расположенные между вертикальными прямыми с номерами 2 и 3, 4 и 5, 6 и 7, 8 и 9, а также все звенья на 10-й вертикальной прямой, расположенные между горизонтальными прямыми с номерами 2 и 3, 4 и 5, 6 и 7, 8 и 9, 9 и 10. Итого, стёрто 41 звено.
