17 октября 2010

Разбор задачи ММ130 математического марафона

====================================

ММ130

Комната имеет форму прямоугольного параллелепипеда шириной a, высотой b и длиной c. На стене a \times b сидит таракан. Он находится на расстоянии $\frac a2$ от смежной стены и на расстоянии x от потолка, x\le \frac b2 и хочет попасть в точку, симметричную исходной относительно центра параллелепипеда.

Для некоторых значений a, \ b, \ c кратчайший путь между этими точками будет проходить через одну и ту же последовательность граней при любом x, 0\le x\le \frac b2. Для каждой такой последовательности граней приведите пример тройки 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 {(\frac a2 +b -x)^2 + (\frac a2 +c + x)^2 }$
4. $1-2-5-6$ и $1-4-5-6$, длина $d= \sqrt {(\frac a2 +b+c -x)^2 + (\frac a2 + x)^2 }$
5. $1-3-2-6$ и $1-3-4-6$, длина $d= \sqrt {(\frac a2 +b+c -x)^2 + (\frac a2 + x)^2 }$
6. $1-5-2-6$ и $1-5-4-6$, длина $d= \sqrt {(\frac a2 +b -x)^2 + (\frac a2 +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 {(\frac a2 +b -x)^2 + (\frac a2 +c + x)^2 }$
M4: $1-2-5-6$, $1-4-5-6$, $1-3-2-6$ и $1-3-4-6$, длина $d(M_4)= \sqrt {(\frac a2 +b+c -x)^2 + (\frac a2 + 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= \frac b2$, независимо от значений a, b и c, $d(M_3)= \sqrt {(\frac a2 + \frac b2)^2 + (\frac a2 + \frac b2 +c )^2 }= d(M_4) $, а при $x < \frac b2$, $d(M_3) < d(M_4) $.

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

Теперь, при $x= \frac b2$, $d(M_1) < d(M_5) $, также независимо от значений a, b и c, тогда М5 тоже не решение задачи.
Маршруты М1 и М2 являются решением, соответствующие значения параметров несложно подобрать.

Например, при $a=4$, $b=2$, $c=4$, при всех $0 \le x \le 1$, КП будут только М1.

А при $a=1$, $b=2.5$, $c=1$, при любых $0 \le x \le 1.25$, КП будет M2.

Обсуждение
Когда-то прочитал в "Кванте" задачу про насекомого, сидящего почти под потолком на торцевой стене длинного зала. Чтобы попасть в центрально-симметричную точку зала кратчайшим путём ему нужно было пройти по потолку, затем перебраться на боковую стену, затем - на пол, а уже оттуда - на противоположный торец. Придумывая задачу для Марафона я вспомнил о ней, и сначала захотел обобщить - вывести для измерений комнаты a, b, c и координат таракана x и y правила определения длины кратчайшего пути. Затем, в процессе обкатки формулировки y превратилось в $\frac{a}{2}$, x стало принимать значения от 0 до $\frac{b}{2}$, но рассмотрение всех вариантов всё равно оставалось достаточно объёмным, и первоначальный интерес от поиска маршрутов сменился скукой рутинных вычислений.

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

Вот только в своём решении я отсекал маршрут $M_3$ просто на том основании, что существует маршрут равной длины, симметричный ему относительно вертикальной плоскости, проходящей через исходную точку, и, таким образом, $M_3$ не будет кратчайшим маршрутом в понимании "имеющий длину меньшую, нежели какой-либо другой". Но Алексей Волошин и Анатолий Казмерчук справедливо указали в уточняющих условие письмах, что для любого маршрута найдётся равный ему симметричный относительно центра параллелепипеда. Таким образом в формулировку внесено уточнение, а Алексей Волошин и Анатолий Казмерчук получают +1 балл.

Решением задачи в её марафонной постановке являются 2 различных параллелепипеда, представляющие 2 наиболее очевидных маршрута: через потолок и через боковую стену. Это, в общем-то, несколько скучно. Жаль, что я не установил ограничения для x, к примеру, $0 \le x \le \frac{b}{4}$ - в этом случае среди решений был бы параллелепипед, кратчайший маршрут в котором проходил бы через 5 граней (возможность того, что такой вариант может быть кратчайшим даже не рассматривалась некоторыми участниками).

Вот зависимость длины маршрутов для случая $a=2$, $b=2$, $c=40$, найденного Сергеем Половинкиным в развитие темы.

Изображение

Полагаю, это можно отметить дополнительным баллом.

Награды

За правильное решение задачи Сергей Половинкин и Алексей Волошин получают 6+1=7 баллов, Анатолий Казмерчук получает 5+1=6 баллов, Николай Дерюгин и Евгений Гужавин получают по 3 балла.

Эстетическая оценка задачи 4.3 балла

====================================

Разбор задачи ММ130 подготовил Алексей Извалов
Labels: , , ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)