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 подготовил Алексей Извалов
0 comments
Labels: , , ,

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

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

ММ129

Будем заполнять бесконечный клетчатый лист бумаги натуральными числами по спирали (каждый следующий виток начинается на вертикали, в которой стоит единица):

Изображение

Для каждого числа найдём восемь модулей разности его с соседями (по вертикали, горизонтали и диагонали). Количество простых чисел среди этих восьми назовем индексом простоты окружения исходного сила.
Какое наибольшее значение может принимать индекс простоты окружения?
Для скольких чисел достигается это значение?

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

Решение.

Для числа 2 имеем индекс простоты, равный 5. Докажем, что больше чисел с таким индексом быть не может. Для соседей единицы их индексы простоты проверяются непосредственно, а для остальных чисел справедливы следующие рассуждения.

Поскольку от витка к витку количество цифр увеличивается на 4, то т.к. четные/нечётные числа стоят столбцами. Значит, у каждого числа среди восьми разностей шесть будут нечётными.

Поскольку при данном способе заполнения в соседних клетках не будут стоять чисел, различающихся на 2, то и простых разностей не будет больше 6.
Но по правилу построения для большинства чисел две из нечётных разностей будут единицами. Ровно одна разность будет равняться одному для чисел в двух столбцах: идущем вверх от единицы и смежном с ним слева.

Рассмотрим число, стоящее в столбце, идущем вверх от единицы.
Общий вид такого числа $a_n=2n^2+2n+2$ (если начинать индекс n с нуля).
Соседями его будут:
$(a_{n+3}-1),~(a_{n+1}),~(a_{n+2}+1)$
$(a_{n+2}-1),~(a_{n}),~(a_{n+1}+1)$
$(a_{n+1}-1),~(a_{n-1}),~(a_{n}+1)$

Разностями - кандидатами в простые будут:
Северо-запад: $12n+23$
Запад: $8n+11$
Юго-запад: $4n+3$
Северо-восток: $8n+13$
Восток: $4n+5$

Но, перебирая возможные остатки от деления n на 3, увидим, что среди этих чисел хотя бы одно будет делиться на 3. Т.к. ровно трём разность не может равняться, то среди разностей будет не более четырёх простых.

Теперь рассматриваем смежный слева столбец. Числа этого столбца, смежные с $a_{n}$, будут иметь вид $(a_{n+2}-1)$ Соседями их будут:
$(a_{n+4}-2),~(a_{n+3}-1),~(a_{n+1})$
$(a_{n+3}-2),~(a_{n+2}-1),~(a_{n})$
$(a_{n+2}-2),~(a_{n+1}-1),~(a_{n-1})$

Северо-запад: $8n+27$
Запад: $4n+11$
Северо-восток: $4n+7$
Восток: $8n+11$
Юго-восток: $12n+11$

И, опять-таки, не больше четырёх из этих разностей будут простыми.

Обсуждение

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

Награды

За правильное решение задачи Виктор Филимоненков, Алексей Волошин, Анатолий Казмерчук, Сергей Половинкин и Пашуткин Дмитрий получают по 5 баллов.

Эстетическая оценка задачи 5

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

Разбор задачи ММ129 подготовил Алексей Извалов
0 comments
Labels: , , ,
Подписаться на: Сообщения (Atom)