Выбрана 1 задача 
Убрать все задачи
В городе Никитовка двустороннее движение. В течение двух лет в городе проходил ремонт всех дорог. Вследствие этого в первый год на некоторых дорогах было введено одностороннее движение. На следующий год на этих дорогах было восстановлено двустороннее движение, а на остальных дорогах введено одностороннее движение. Известно, что в каждый момент ремонта можно было проехать из любой точки города в любую другую. Доказать, что в Никитовке можно ввести одностороннее движение так, что из каждой точки города удастся проехать в любую другую точку.
Решение
|
|
 |
Условие
Внутри прямоугольного листа бумаги вырезали n прямоугольных дыр со сторонами, параллельными краям листа. На какое наименьшее число прямоугольных частей можно гарантированно разрезать этот дырявый лист? (Дыры не перекрываются и не соприкасаются.)
Решение
Оценка. Будем считать, что одна из сторон листа вертикальна. Вдоль каждой вертикальной "стороны" одной из дырок проведём вертикальный разрез до "упора" в горизонтальную сторону соседней дырки или в край листа. Повторим эту процедуру для всех дырок (рис. слева). После этого лист "распадётся" на некоторое количество m прямоугольников (действительно, у полученных частей все углы прямые).
У каждого прямоугольника четыре угла, значит, общее число углов всех прямоугольников равно 4m. С другой стороны, к четырём углам исходного листа каждый из 2n разрезов добавляет не более шести прямых углов (см. рис. слева, некоторые углы, образованные каким-то разрезом, могут совпадать с углами, образованными другими разрезами), поэтому число углов не превосходит 12n + 4.
Таким образом, 4m ≤ 12n + 4, то есть m ≤ 3n + 1.
Ответ
На 3n + 1 часть.
Замечания
9 баллов
