marathon:problem

Содержание

ММ130

ММ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, боковую грань слева от 1-ой (стена) - грань 2, снизу (пол комнаты) - грань 3, правая боковая стена - грань 4, сверху (потолок комнаты) - грань 5, задняя стенка, та, куда держит путь таракан, грань 6. Обозначим каждую грань соответствующим цветом:
1. сиреневый
2. розовый
3. голубой
4. зеленый
5. желтый
6. бирюзовый

Рассмотрим различные маршруты между заданными точками по граням параллелепипеда. Любой маршрут начинается на грани 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:
1. 1-2-6 и 1-4-6, длина $d = sqrt{(a+c)^2 + (b-2x)^2}$
2. 1-3-6 и 1-5-6, длина d = b+c
3. 1-2-3-6 и 1-4-3-6, длина $d = sqrt{(a/2 +b -x)^2 + (a/2 +c + x)^2}$
4. 1-2-5-6 и 1-4-5-6, длина $d = sqrt{(a/2 +b+c -x)^2 + (a/2 + x)^2}$
5. 1-3-2-6 и 1-3-4-6, длина $d = sqrt{(a/2 +b+c -x)^2 + (a/2 + x)^2}$
6. 1-5-2-6 и 1-5-4-6, длина $d = \sqrt{(a/2 +b -x)^2 + (a/2 +c + x)^2}$
7. 1-2-3-4-6 и 1-4-3-2-6, длина $d = sqrt{(a +b)^2 + (a +c)^2}$
8. 1-2-5-4-6 и 1-4-5-2-6, длина $d = sqrt{(a +b)^2 + (a +c)^2}$
9. 1-3-2-5-6 и 1-3-4-5-6, длина $d = sqrt {(a +b)^2 + (c+2(b-x))^2}$
10. 1-5-2-3-6 и 1-5-4-3-6, длина $d = sqrt{(a +b)^2 + (c+2x)^2}$

Заметим, что длины маршрутов 3 и 6 равны, также равны маршруты 4 и 5.
Для любого набора параметров a, b, c и при любом допустимом значении x длины маршрутов 7 и 8 больше длины маршрута 1, а маршрута 9 - больше длины маршрута 2.

Получаем 5 маршрутов:
M1: 1-3-6 и 1-5-6, длина d(M_1) = b+c
M2: 1-2-6 и 1-4-6, длина $d(M_2) = sqrt{(a+c)^2 + (b-2x)^2}$
M3: 1-2-3-6, 1-4-3-6, 1-5-2-6 и 1-5-4-6, длина $d(M_3) = sqrt{(a/2+b-x)^2 + (a/2+c+x)^2}$
M4: 1-2-5-6, 1-4-5-6, 1-3-2-6 и 1-3-4-6, длина $d(M_4) = sqrt{(a/2+b+c-x)^2 + (a/2+x)^2}$
M5: 1-5-2-3-6 и 1-5-4-3-6, длина $d(M_5) = sqrt{(a +b)^2 + (c+2x)^2}$

Некоторые из этих маршрутов не существуют при некоторых значениях a, b, c, x, но при других значениях любой из этих 5 может оказаться самым коротким, поэтому нужно рассматривать их все. Кроме того, если маршрут не существует (для какого-либо набора значений), то это означает, что есть другой, более короткий маршрут. При сравнении длин маршрутов проще сравнивать квадраты длин, что не меняет знака отношения. Заметим, что при x= b/2, независимо от значений a, b и c, $d(M_3)= sqrt{(a/2 + b/2)^2 + (a/2 + b/2 +c)^2} = d(M_4)$ , а при x < b/2, d(M_3) < d(M_4) .

При этом же значении x, $d^2(M_3)-d^2(M_1) = {a^2}/2+ab-{b^2}/2+ac-bc$ , а $d^2(M_3)-d^2(M_2) = -{a^2}/2+ab+{b^2}/2-ac+bc$ . Эти две величины не могут быть отрицательными одновременно, поэтому маршрут M3 не может быть решением задачи.

Теперь, при x = b/2, d(M_1) < d(M_5) , также независимо от значений 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, но рассмотрение всех вариантов всё равно оставалось достаточно объёмным, и первоначальный интерес от поиска маршрутов сменился скукой рутинных вычислений.

Последовала очередная переформулировка: меня заинтересовало, а найдутся ли такие комнаты, для которых кратчайший маршрут будет проходить всегда черед один и тот же набор граней? В таком виде процесс отсечения неподходящих вариантов необременителен, и задача была включена в Марафон.

Вот только в своём решении я отсекал маршрут M_3 просто на том основании, что существует маршрут равной длины, симметричный ему относительно вертикальной плоскости, проходящей через исходную точку, и, таким образом, M_3 не будет кратчайшим маршрутом в понимании «имеющий длину меньшую, нежели какой-либо другой». Но Алексей Волошин и Анатолий Казмерчук справедливо указали в уточняющих условие письмах, что для любого маршрута найдётся равный ему симметричный относительно центра параллелепипеда. Таким образом, в формулировку внесено уточнение, а Алексей Волошин и Анатолий Казмерчук получают +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 подготовил Алексей Извалов.