Покори Воробьёвы горы! 2023, 9 класс, задача 2
В городе проспектов и улицы, которые образуют прямоугольную сетку: все улицы параллельны между собой и все проспекты перпендикулярны улицам (см. рис.). Точку пересечения улицы и проспекта будем называть "перекрестком". Городские власти проводят дорожные работы на некоторых участках дороги (отрезок улицы или проспекта между соседними перекрестками). Во время ремонта ездить по этому участку нельзя. Какое наибольшее количество участков можно ремонтировать одновременно, чтобы при этом из любого перекрестка можно было проехать на любой другой?
Ответ: .
Решение: В городе перекрестков. Заметим, что для того, чтобы из каждого перекрестка можно было проехать в каждый, должно остаться не менее участков дороги. Действительно, представим себе, что путешественник выезжает из какого-то перекрестка и хочет объехать их все. При этом он отмечает все участки, которые проехал и все перекрестки, которые посетил. Каждый раз, когда он приезжает в неотмеченный перекресток, он едет по неотмеченному участку. В начале у него неотмеченный перекресток (начальный перекресток не считается), значит должно быть не менее участков, по которым можно ездить.
Изначально имеется участков дороги, значит можно удалить не более участков.
Покажем, что можно удалить ровно участков. Будем ремонтировать все участки, принадлежащие улицам со по (улицу № не трогаем). Очевидно, из каждого перекрестка все еще можно проехать в каждый. На каждой из улиц (кроме -й) удалили по участков, всего участков.