|
||||||||||||||||||
|
СодержаниеММ130Конкурсная задача ММ130 Комната имеет форму прямоугольного параллелепипеда шириной a, высотой b и длиной c. На стене aхb сидит таракан. Он находится на расстоянии a/2 от смежной стены и на расстоянии x от потолка, x ≤ b/2 и хочет попасть в точку, симметричную исходной относительно центра параллелепипеда. Для некоторых значений a, b, c кратчайший путь между этими точками будет проходить через одну и ту же последовательность граней при любом x, 0 ≤ x ≤ b/2. Для каждой такой последовательности граней приведите пример тройки a, b, c. Примечание: термин «кратчайший путь» означает путь, для которого нельзя найти путь, более короткий. Решение Приведём в основном решение Сергея Половинкина
Пронумеруем стороны данного прямоугольного параллелепипеда.
Рассмотрим различные маршруты между заданными точками по граням параллелепипеда. Любой маршрут начинается на
грани 1, а заканчивается - на 6.
Очевидно, что любой кратчайший путь (КП) не может включать одну и ту же грань дважды. Кроме того, понятно,
что любой КП представляет из себя отрезок прямой, соединяющий 2 заданные точки на некоей развертке
параллелепипеда.
Рассмотрим «обобщенную» развертку:
На этом рисунке при разничных значениях параметров a, b, c можно нарисовать все КП, проходящие через боковые
грани 2 и 4. Также приведено несколько прямых маршрутов, которые при соответствующих значениях a, b, c, x,
возможно, могут быть КП: 1-2-6, 1-2-3-6, 1-4-3-6. На рисунке приведены маршруты (потенциальные КП) 1-3-2-6, 1-5-2-6, 1-3-4-6, 1-5-4-6.
А на следующем рисунке можно построить все маршруты, которые теоретически могут быть КП.
Такие маршруты могут включать в себя 3, 4 или 5 граней, но не 6, все начинаются с 1 и заканчиваются в 6,
остальные грани входят не более одного раза. Всего имеем 20 таких маршрутов, ввиду симметрии, их длины равны
попарно, всего имеем 10 пар, найдем длины всех 10:
Заметим, что длины маршрутов 3 и 6 равны, также равны маршруты 4 и 5.
Получаем 5 маршрутов: Некоторые из этих маршрутов не существуют при некоторых значениях a, b, c, x, но при других значениях любой из этих 5 может оказаться самым коротким, поэтому нужно рассматривать их все. Кроме того, если маршрут не существует (для какого-либо набора значений), то это означает, что есть другой, более короткий маршрут. При сравнении длин маршрутов проще сравнивать квадраты длин, что не меняет знака отношения. Заметим, что при x= b/2, независимо от значений a, b и c, , а при x < b/2, . При этом же значении x, , а . Эти две величины не могут быть отрицательными одновременно, поэтому маршрут M3 не может быть решением задачи. Теперь, при x = b/2, , также независимо от значений a, b и c, тогда М5 тоже не решение задачи. Маршруты М1 и М2 являются решением, соответствующие значения параметров несложно подобрать. Например, при a=4, b=2, c=4, при всех 0 ≤ x ≤ 1, КП будут только М1. А при a=1, b=2.5, c=1, при любых 0 ≤ x ≤ 1.25, КП будет M2. Обсуждение Когда-то прочитал в «Кванте» задачу про насекомого, сидящего почти под потолком на торцевой стене длинного зала. Чтобы попасть в центрально-симметричную точку зала кратчайшим путём ему нужно было пройти по потолку, затем перебраться на боковую стену, затем - на пол, а уже оттуда - на противоположный торец. Придумывая задачу для Марафона, я вспомнил о ней, и сначала захотел обобщить - вывести для измерений комнаты a, b, c и координат таракана x и y правила определения длины кратчайшего пути. Затем, в процессе обкатки формулировки y превратилось в a.2, x стало принимать значения от 0 до b/2, но рассмотрение всех вариантов всё равно оставалось достаточно объёмным, и первоначальный интерес от поиска маршрутов сменился скукой рутинных вычислений. Последовала очередная переформулировка: меня заинтересовало, а найдутся ли такие комнаты, для которых кратчайший маршрут будет проходить всегда черед один и тот же набор граней? В таком виде процесс отсечения неподходящих вариантов необременителен, и задача была включена в Марафон. Вот только в своём решении я отсекал маршрут просто на том основании, что существует маршрут равной длины, симметричный ему относительно вертикальной плоскости, проходящей через исходную точку, и, таким образом, не будет кратчайшим маршрутом в понимании «имеющий длину меньшую, нежели какой-либо другой». Но Алексей Волошин и Анатолий Казмерчук справедливо указали в уточняющих условие письмах, что для любого маршрута найдётся равный ему симметричный относительно центра параллелепипеда. Таким образом, в формулировку внесено уточнение, а Алексей Волошин и Анатолий Казмерчук получают +1 балл. Решением задачи в её марафонной постановке являются 2 различных параллелепипеда, представляющие 2 наиболее очевидных маршрута: через потолок и через боковую стену. Это, в общем-то, несколько скучно. Жаль, что я не установил ограничения для x, к примеру, 0 ≤ x ≤ b/4 - в этом случае среди решений был бы параллелепипед, кратчайший маршрут в котором проходил бы через 5 граней (возможность того, что такой вариант может быть кратчайшим даже не рассматривалась некоторыми участниками). Вот зависимость длины маршрутов для случая a=2, b=2, c=40, найденного Сергеем Половинкиным в развитие темы. Полагаю, это можно отметить дополнительным баллом. Награды За правильное решение задачи Сергей Половинкин и Алексей Волошин получают 6+1=7 баллов, Анатолий Казмерчук получает 5+1=6 баллов, Николай Дерюгин и Евгений Гужавин получают по 3 балла. Эстетическая оценка задачи 4.3 балла Разбор задачи ММ130 подготовил Алексей Извалов.
|
|||||||||||||||||
|
||||||||||||||||||
|