?

Log in

No account? Create an account

La Cucaracha - Clittary Hilton

Jul. 23rd, 2007

12:48 pm - La Cucaracha

Previous Entry Share Next Entry

A cute little problem для неокрепшего (neocrap) ума:

Room dimensions:   (30 х 12 х 12)
Initial position:  (0, 6, 1)
Final position:    (30, 6, 11)

Find the shortest route for the cockroach!
Needless to say, the answer is shorter than 42.


Это (вверху), разумеется, не решение!
Но самое удивительное, что и это (внизу) не решение!



А вот это решение... click and enjoy!



Мораль: Не всякая прямая линия соединяющая две точки есть кратчайшее между ними расстояние!

Comments:

[User Picture]
From:yurvor
Date:July 23rd, 2007 05:40 pm (UTC)
(Link)
40. Известное дело - топать надо по диагонали (если развёртку по-другому чутка положить).
(Reply) (Thread)
(Deleted comment)
[User Picture]
From:yurvor
Date:July 23rd, 2007 06:30 pm (UTC)
(Link)
Нет, Вы неправильно понимаете источник сорока :)

Если хозяйка позволит, я напишу.
(Reply) (Parent) (Thread)
[User Picture]
From:uncle_gora
Date:July 23rd, 2007 07:20 pm (UTC)
(Link)
+1
Дело может и известное, но задачка всё-равно не плохая.
(Reply) (Parent) (Thread)
[User Picture]
From:gurzo
Date:July 23rd, 2007 06:09 pm (UTC)
(Link)
(Reply) (Thread)
(Deleted comment)
[User Picture]
From:yurvor
Date:July 23rd, 2007 06:42 pm (UTC)
(Link)
Я, честно говоря, не понимаю, что здесь написано. Что такое а и что такое б. Если Вы распишете всё подробно, то сами наверняка поймёте, где ошибаетесь. Потому что решение, будучи узнанным, без сомнения покажется Вам тривиальным ;)
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:yurvor
Date:July 23rd, 2007 07:11 pm (UTC)
(Link)
"Таким образом, весь путь определяется двумя переменными, координатами в тех местах, где таракан пересекает ребра."

Не понял. Нарисуйте на развёртке точки, обозначте буквами, тогда поговорим :)

"Итого путь таракана состоит из трех участков, длины которых описывает моя формула. "

Неправильно. путь таракана состоит _как_минимум_ из трёх участков, два из которых - торцы. Третий проходит по одной (или нескольким) стенам-потолку.

Соответственно, Ваши оценки расстояний по каждому из участков не верны.
(Reply) (Parent) (Thread)
(Deleted comment)
From:(Anonymous)
Date:July 23rd, 2007 08:08 pm (UTC)

критическая подсказка

(Link)
«Таракану нужно проползти по стене-потолку как миниум 30 единиц»

«если таракан приходит на верхнюю грань, то по оси Z он затрачивает 11 единиц.»

вы учитываете путь таракана по оси Z дважды -- в первой цитате и во второй ;)
(Reply) (Parent) (Thread)
(Deleted comment)
From:(Anonymous)
Date:July 23rd, 2007 09:41 pm (UTC)
(Link)
да, затрачивает 12 по Z. да, затрачивает 30 по X. зачем же вы их складываете-то? диагональ квадрата со стороной 1 не равна 2.
(Reply) (Parent) (Thread)
[User Picture]
From:itman
Date:July 23rd, 2007 09:53 pm (UTC)
(Link)
Ну, в общем-то, наверное, незачем. Может и правда кривая длины 40 существует, если срезать.
(Reply) (Parent) (Thread)
From:(Anonymous)
Date:July 23rd, 2007 10:27 pm (UTC)
(Link)
ну конечно существует. если нарисовать чуть-чуть другую развертку параллелограмма, ее сразу видно.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:clittary_hilton
Date:July 24th, 2007 02:48 pm (UTC)

Re: критическая подсказка

(Link)
вооруженный зреньем узких ос,
ось Z сосущих дважды, сущих дважды...
(Reply) (Parent) (Thread)
[User Picture]
From:yurvor
Date:July 23rd, 2007 08:09 pm (UTC)
(Link)
"Таракану нужно проползти по стене-потолку как миниум 30 единиц. Обозначим для удобства ее как координату X. "

Кого - её? 30 - это длина, вообще-то. Как она может быть координатой? Что-то у Вас не в порядке с обозначениями...

Да и с логикой тоже - с чего Вы взяли, что "если таракан приходит на верхнюю грань, то по оси Z он затрачивает 11 единиц. Чтобы попасть в финальную точку, ему нужно будет потом спуститься еще минимум на 1 единицу. Аналогично, если он приходит сначала на нижнюю грань, затрачивая 1 единицу пути, то ему нужно будет потом подняться на 11 единиц. Не важно каким зюгзагом он это будет делать."

Вы тут неявно предполагаете, что таракан по ходу дела не меняет стену на потолок и/или пол. Что не факт (и это - подсказка :))
(Reply) (Parent) (Thread)
(Deleted comment)
From:(Anonymous)
Date:July 23rd, 2007 09:51 pm (UTC)
(Link)
омг, фрикцию. удивительно. погуглите "spider and fly problem", что ли, а?
(Reply) (Parent) (Thread)
[User Picture]
From:uncle_gora
Date:July 23rd, 2007 07:17 pm (UTC)
(Link)
В общем идейка-то в том что думать об ентой задачке надо не зацикливаясь на рёбрах. Прям таки Think outside the box. Ответ, действительно 40, как и предлагали выше.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:uncle_gora
Date:July 23rd, 2007 10:07 pm (UTC)
(Link)
Собствено, точка находится на некотором расстоянии от края, по-этому там не обязательно двигаться 12 единиц. А потом, Вам уже дали ответ: http://clittary-hilton.livejournal.com/46533.html?thread=829893#t829893
(Reply) (Parent) (Thread)
[User Picture]
From:wisselwachter
Date:July 24th, 2007 08:43 am (UTC)

откладывая линейку в сторону

(Link)
Действительно, третий вариант правильный.
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:July 24th, 2007 02:36 pm (UTC)

Re: откладывая линейку в сторону

(Link)
что, однако, не так просто доказать!
(Reply) (Parent) (Thread)
[User Picture]
From:nowhere_person
Date:July 24th, 2007 09:09 am (UTC)
(Link)
Тараканы умеют летать. По прямой.
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:July 24th, 2007 02:40 pm (UTC)
(Link)
летят по небу тараканы
                                облаками
а я израненный лежу...

(Reply) (Parent) (Thread)
[User Picture]
From:dolgushin
Date:July 25th, 2007 11:06 am (UTC)
(Link)
умница
(Reply) (Parent) (Thread)
[User Picture]
From:physicist1
Date:July 8th, 2010 03:17 pm (UTC)
(Link)
Аналогичная задача:
Параллепипед с неравными сторонами а,в,с.
В вершине сидит таракан.
Найти самую далёкую от таракана точку на поверхности.
Противоположная вершина параллепипеда - явно не решение.

По крайней мере, для решения здесь недостаточно проводить прямые на развёртке, так как точку ещё надо найти.
(Reply) (Parent) (Thread)
[User Picture]
From:clittary_hilton
Date:July 8th, 2010 03:52 pm (UTC)
(Link)
This is a rather messy problem (Kotani Problem). A still another puzzle on an uneven cuboid is the Knuth problem, find a pair of points (not necessarily one being a corner) with the greatest surface distance between them.
(Reply) (Parent) (Thread)
From:(Anonymous)
Date:July 8th, 2010 08:40 pm (UTC)
(Link)
Messy problem.
(Reply) (Parent) (Thread)