Re[4]: 4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 18.03.03 16:19
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Что-то я с тремя машинками не понял

MP>Рассмотрим случай:
MP>Все машинки стартуют из произвольных точек ребер исходящих из одной вершины и едут с одинаковой скоростью.
MP>ИМХО, они никогда не столкнутся

Все в сторону "от" или "к" этой вершине?
Re[5]: 4 машинки
От: MichaelP  
Дата: 19.03.03 06:22
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Все в сторону "от" или "к" этой вершине?


Был неправ . Сглупил под вечер .

Конечно, рано или поздно они все вместе будут ехать к вершине!
Re[6]: На любом
От: Pushkin Россия www.linkbit.com
Дата: 19.03.03 07:22
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Всвязи с этим, возникает интересный вопрос:

MP>А как на кубе? Машинок — 6, ребер — 12.

Вопрос замечательный.
Представляешь, как будет забавно, если они не разъедутся на любом многограннике?
Re[7]: На любом
От: mogadanez Чехия  
Дата: 19.03.03 07:46
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, MichaelP, Вы писали:


MP>>Всвязи с этим, возникает интересный вопрос:

MP>>А как на кубе? Машинок — 6, ребер — 12.

P>Вопрос замечательный.

P>Представляешь, как будет забавно, если они не разъедутся на любом многограннике?
на кубе даже 5 не разъедутся
... << RSDN@Home 1.0 beta 6a >>
Re: Два варианта решения на выбор
От: Pushkin Россия www.linkbit.com
Дата: 20.03.03 07:22
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>По периметрам граней правильного тетраэдра ездят 4 машины.

P>Причём все по часовой стрелке (если смотреть на грань).
P>Все машины едут всё время с одинаковой скоростью.
P>Но каждая может в начале выбрать эту скорость и точку старта.
P>Неминуема ли катастрофа?

P>http://www.rsdn.org/File/13542/Cars.jpg


Как я уже писал, условия задачи явно пережаты, их можно ослабить в 2 стороны на выбор.

1) Всего 3 машинки, скорость каждой постоянна.

Мы не будем заранее утверждать, что скорости равны (хотя это и кажется почти очевидным)
Пусть нижняя (красная) машина самая медленная (не быстрее любой другой)
И пусть она сейчас находиться в центре.
Левая (синяя) машина очевидно не может находиться на наклонном ребре в центр — столкнётся.
Но так как она едет не медленнее красной, она не может находиться и на внешнем ребре.
Поэтому она на вертикальном ребре.

Аналогично с левой (зелёной) машиной, только время развернулось.
Она не может быль на наклонном ребре из центра — должна была уже столкнуться
Она не может быть на внешнем ребре — она едет не медленнее красной и тоже должна была столкнуться на наклонном.
Значит она на вертикальном.

Всё, приехали, две машины на одном ребре. Это значит, что либо столкнутся либо должны были столкнуться.

2) 4 машинки, скорость меняют как хотят, лишь бы не назад ехали и каждая проехала несколько кругов.

Сначала 2 очевидных утверждения.
а) 2 машины на одном ребре это кирдык
б) 3 машины, едущие в одну вершину это кирдык
в) 3 машины, едущие из одной вершины тоже кирдык

Пусть нижняя (красная) машинка на наклонном ребре из центра. (как на рисунке)
Правая (синяя) может быть на любом из двух рёбер. Пусть на внешнем.
Дальше никакого произвола.
Внешней (жёлтой) приходится быть на левом ребре (если на нижнем, имеем б))
Левой (зелёной) тоже не осталось выбора — чтобы избежать а ) ей нельзя быть на внешнем ребре, чтобы в) — на вертикальном в центр.

Итак имеем точно ситуацию как на рисунке. Причём вполне жёстко и безальтернативно. Единственная свобода была в начале (с синей), но этот второй случай можно нарисовать и получить ровно то же самое, только иначе развёрнутое.

А теперь смотрим на рисунок. Кто первым достигнет ближайшей своей вершины?
Если зелёная или синяя, то кирдык по сценарию а)
А если жёлтая или красная, то по сценарию б)

3) Так что же делать бедным машинкам?
Ну это совсем просто, я лишь для полноты это скажу.
Надо пустить машинки попарно — две по часовой стрелке, две против.
Тогда имеем две независимые конфликтующие лишь внутри себя пары.
Их легко развести при постоянной единой скорости всех машинок.

4) И последнее. Мне по-прежнему кажется очень забавным исследовать любой многогранник (даже не обязательно правильный). Не может ли быть верным следующее топологическое утверждение: если на каждой грани ездит машинка, и все по часовой стрелке, то катастрофы не миновать. Может кто-нить хотя бы контрпример придумает, чтоб я успокоился?
Re[2]: Два варианта решения на выбор
От: mogadanez Чехия  
Дата: 20.03.03 07:37
Оценка:
P>4) И последнее. Мне по-прежнему кажется очень забавным исследовать любой многогранник (даже не обязательно правильный). Не может ли быть верным следующее топологическое утверждение: если на каждой грани ездит машинка, и все по часовой стрелке, то катастрофы не миновать. Может кто-нить хотя бы контрпример придумает, чтоб я успокоился?

на кубе 4 машинки разъедуться, 5 — 100% столкновение
... << RSDN@Home 1.0 beta 6a >>
Re[2]: Два варианта решения на выбор
От: MichaelP  
Дата: 20.03.03 07:43
Оценка:
Здравствуйте, Pushkin, Вы писали:


P>Сначала 2 очевидных утверждения.

P>а) 2 машины на одном ребре это кирдык
P>б) 3 машины, едущие в одну вершину это кирдык
P>в) 3 машины, едущие из одной вершины тоже кирдык

Я бы поспорил с очевидностью пункта в). Так как в нем возможны варианты перехода в тот случай, который ты позже подробно разбираешь.
Re[3]: Два варианта решения на выбор
От: Pushkin Россия www.linkbit.com
Дата: 20.03.03 07:52
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Я бы поспорил с очевидностью пункта в).


А пункт б) тебя значит не смущает? Пожалуйста, точное перефразирование твоего доказательства пункта б) в обратную сторону по времени.

Если 3 машины едут из одной вершины, то значит какая-то из них выехала из неё последней. Это означает, что непосредственно перед моментом её выезда она ехала по одному из двух других рёбер. Но на каждом из них уже ехала к этому моменту своя машина. Имеем пункт а)
Re[4]: Два варианта решения на выбор
От: MichaelP  
Дата: 20.03.03 08:01
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>А пункт б) тебя значит не смущает? Пожалуйста, точное перефразирование твоего доказательства пункта б) в обратную сторону по времени.


P>Если 3 машины едут из одной вершины, то значит какая-то из них выехала из неё последней. Это означает, что непосредственно перед моментом её выезда она ехала по одному из двух других рёбер. Но на каждом из них уже ехала к этому моменту своя машина. Имеем пункт а)


Это ничего не доказывает. В будущем они могут никогда не перейти в ситуацию в).
Т.е. возвращаемся к моему доказательству.

Забавно, что если потребовать, чтобы хотя бы одна машинка проехала несколько кругов. То решение возможно только в ситуации в).
Re[5]: Два варианта решения на выбор
От: Pushkin Россия www.linkbit.com
Дата: 20.03.03 08:51
Оценка:
Здравствуйте, MichaelP, Вы писали:

P>>Если 3 машины едут из одной вершины, то значит какая-то из них выехала из неё последней. Это означает, что непосредственно перед моментом её выезда она ехала по одному из двух других рёбер. Но на каждом из них уже ехала к этому моменту своя машина. Имеем пункт а)


MP>Это ничего не доказывает. В будущем они могут никогда не перейти в ситуацию в).

MP>Т.е. возвращаемся к моему доказательству.
MP>Забавно, что если потребовать, чтобы хотя бы одна машинка проехала несколько кругов. То решение возможно только в ситуации в).

Нет, подожди, я же требовал, чтобы ВСЕ машинки проехали несколько кругов.
Ты согласен, что ситуация в) если и возможна, то только в самом начале?
Т.е. после того, как каждая из 4-х машинок проехала хотя бы по одному кругу,
ситуация в) становится совершенно точным индикатором катастрофы.
Re[3]: Два варианта решения на выбор
От: Pushkin Россия www.linkbit.com
Дата: 20.03.03 09:15
Оценка:
Здравствуйте, mogadanez, Вы писали:

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


M>на кубе 4 машинки разъедуться, 5 — 100% столкновение


Ну дык флаг те в руки
Докажи, что на N-граннике произвольно меняя скорости не разъедутся N-1 машина
Вот токо для N=4 это несправедливо, так что надо думать другую формулу
Re[4]: Два варианта решения на выбор
От: mogadanez Чехия  
Дата: 20.03.03 09:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, mogadanez, Вы писали:


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


M>>на кубе 4 машинки разъедуться, 5 — 100% столкновение


P>Ну дык флаг те в руки

P>Докажи, что на N-граннике произвольно меняя скорости не разъедутся N-1 машина
P>Вот токо для N=4 это несправедливо, так что надо думать другую формулу

как это сами же сказали, что на 4х граннике (как в изначальном условии) 3 не разъедуться...
а 2 легко..
получается что максимум N-2 могут разъехаться....
... << RSDN@Home 1.0 beta 6a >>
Re[5]: Два варианта решения на выбор
От: Pushkin Россия www.linkbit.com
Дата: 20.03.03 09:32
Оценка:
Здравствуйте, mogadanez, Вы писали:

P>>Докажи, что на N-граннике произвольно меняя скорости не разъедутся N-1 машина

P>>Вот токо для N=4 это несправедливо, так что надо думать другую формулу

M>как это сами же сказали, что на 4х граннике (как в изначальном условии) 3 не разъедуться...

M>а 2 легко..
M>получается что максимум N-2 могут разъехаться....

С условием постоянства скорости каждой на 4-граннике разъедутся лишь 2.
Без этого условия 3.
Т.е. похоже это разные задачи, не знаю насколько сильно, но разные.
У тебя кстати в кубе как машинки ездят? Равномерно?
Re[6]: Два варианта решения на выбор
От: mogadanez Чехия  
Дата: 20.03.03 09:46
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, mogadanez, Вы писали:


P>>>Докажи, что на N-граннике произвольно меняя скорости не разъедутся N-1 машина

P>>>Вот токо для N=4 это несправедливо, так что надо думать другую формулу

M>>как это сами же сказали, что на 4х граннике (как в изначальном условии) 3 не разъедуться...

M>>а 2 легко..
M>>получается что максимум N-2 могут разъехаться....

P>С условием постоянства скорости каждой на 4-граннике разъедутся лишь 2.

P>Без этого условия 3.
P>Т.е. похоже это разные задачи, не знаю насколько сильно, но разные.
P>У тебя кстати в кубе как машинки ездят? Равномерно?

да равномерно, постараюсь щас картинку нарисовать...
если с переменной скоростью, то можно и 5 я думаю
... << RSDN@Home 1.0 beta 6a >>
Re[7]: Два варианта решения на выбор
От: mogadanez Чехия  
Дата: 20.03.03 10:24
Оценка:
P>>С условием постоянства скорости каждой на 4-граннике разъедутся лишь 2.
P>>Без этого условия 3.
P>>Т.е. похоже это разные задачи, не знаю насколько сильно, но разные.
P>>У тебя кстати в кубе как машинки ездят? Равномерно?

пилат... а на кубе 5 машинок разместилось... =(
... << RSDN@Home 1.0 beta 6a >>
Re: 4 машинки
От: mogadanez Чехия  
Дата: 20.03.03 14:53
Оценка:
Здравствуйте, Pushkin, Вы писали:

учитывая что осталось всего три машины =))) продолжу свои прошлые рассуждения, убрав зеленую машину.
чкорость машин считаем неизменной(как в начальном условии), иначе задача черезвычайно запутывается, и имхо 3 машины могут разъехаться, получается типа светофора, главное установить приоритеты проезда перекрестков.

как я уже писал здесь
Автор: mogadanez
Дата: 18.03.03


Обзначим вершины так

       1

       4
   2       3


будем обозначать растояние машинок до вершин так ж2 растояние желтой машинки до вершины 2.

1.
рассмотрим для начала 2 машинки желтую и красную

расположим желтую машину произвольным образом.
рассмотрим желтую машину, очевидно что одна из точек 2 или 3 будет к ней ближе( растояние меряется только по ходу движения)
   a) ближе к точке 2
      тогда есть два условия при которых машины разъедутся:
        a-a)к ближе к т.2 чем ж к т.2  к2 < ж2
        a-б)к дальше до т.2 более чем на  2 длинны  ребра. 
   б) аналогично для этого случая также получаем коридор длинной в 1 ребро(не включая конечные точки) на котором может находится красная  
      машина( не знаю заччем я рассмотрел этот случай, фактически они идентичны).


2.
теперь по анологии рассмотрим пару машин желтая и синия и найдем коридор для синей машины, тоже равный длинне 1 ребра.

т.к. какое-бы другое положение желтой машины мы не выбрали, она приедет в выбранную нами первоначально точку.

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

http://poigraem.ru/cars.gif
пояснение:
— желтая машина посередине ребра
— красный и синий отрезки показывают допустимые расположения соотв. машинок, проведены от центров ребер, не включая сами точки центра.

дальше — проще
для каждой точки из допустимого диапазона красной машины, находим допустимые диапазоны положения синей машинки, если он совпадут, то могут разъехаться, но как вы уже наверное догадались.... =))

http://poigraem.ru/cars1.gif

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

НЕ МОГУТ РАЗЪЕХАТЬСЯ!


ну как так убедительно?
... << RSDN@Home 1.0 beta 6a >>
Re[2]: Кажется получилось...
От: Les Россия  
Дата: 20.03.03 16:00
Оценка:
Здравствуйте, Pushkin, Вы писали:

...

P>4) И последнее. Мне по-прежнему кажется очень забавным исследовать любой многогранник (даже не обязательно правильный). Не может ли быть верным следующее топологическое утверждение: если на каждой грани ездит машинка, и все по часовой стрелке, то катастрофы не миновать. Может кто-нить хотя бы контрпример придумает, чтоб я успокоился?


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

Рассматриваем систему в нулевой момент времени
1)Выбираем грань.
2)Добавляем ID грани в список
3)Смотрим, на каком ребре соответствующая машинка.
4)Прыгаем на грань, смежную с текущей по данному ребру.
5)Если ID новой грани нет в списке, goto 2
6)Выкидываем из списка все ID граней до "новой".
Оставшиеся в списке грани образуют цикл,

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

Запускаем время.

Легко видеть, что кольцо начнет двигаться в одну сторону, пока не сожмется вокруг одной точки — это когда несколько машинок едут к одной вершине по разным ребрам (например).

Не судите строго, тут есть пробелы, но идея ИМХО верная.
Re[3]: Кажется получилось...
От: MichaelP  
Дата: 20.03.03 16:49
Оценка:
Здравствуйте, Les, Вы писали:


Les>Рассматриваем систему в нулевой момент времени

Les>1)Выбираем грань.
Les>2)Добавляем ID грани в список
Les>3)Смотрим, на каком ребре соответствующая машинка.
Les>4)Прыгаем на грань, смежную с текущей по данному ребру.
Les>5)Если ID новой грани нет в списке, goto 2
Les>6)Выкидываем из списка все ID граней до "новой".
Les>Оставшиеся в списке грани образуют цикл,

Les>Будем говорить, что грань "указывает" на другую грань, если стрелка, проведенная из центра грани к машинке указывает на эту самую другую грань

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

Les>Запускаем время.


Les>Легко видеть, что кольцо начнет двигаться в одну сторону, пока не сожмется вокруг одной точки — это когда несколько машинок едут к одной вершине по разным ребрам (например).



Рассмотри модельный случай (тетраэдр).

Три машинки выезжают из одной вершины — кольцо состоит из трех граней.

Одна из двух машинок (за исключением той, что поедет навстречу четвертой) перешла на другое ребро — кольцо состоит из четырех граней.

Т.е. кольцо может увеличиваться!
Re[4]: Кажется получилось...
От: Les Россия  
Дата: 20.03.03 17:08
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Здравствуйте, Les, Вы писали:


MP>

Les>>Рассматриваем систему в нулевой момент времени
Les>>1)Выбираем грань.
Les>>2)Добавляем ID грани в список
Les>>3)Смотрим, на каком ребре соответствующая машинка.
Les>>4)Прыгаем на грань, смежную с текущей по данному ребру.
Les>>5)Если ID новой грани нет в списке, goto 2
Les>>6)Выкидываем из списка все ID граней до "новой".
Les>>Оставшиеся в списке грани образуют цикл,

Les>>Будем говорить, что грань "указывает" на другую грань, если стрелка, проведенная из центра грани к машинке указывает на эту самую другую грань

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

Les>>Запускаем время.


Les>>Легко видеть, что кольцо начнет двигаться в одну сторону, пока не сожмется вокруг одной точки — это когда несколько машинок едут к одной вершине по разным ребрам (например).


MP>

MP>Рассмотри модельный случай (тетраэдр).

MP>Три машинки выезжают из одной вершины — кольцо состоит из трех граней.


MP>Одна из двух машинок (за исключением той, что поедет навстречу четвертой) перешла на другое ребро — кольцо состоит из четырех граней.


MP>Т.е. кольцо может увеличиваться!


Оно может увеличиваться поначалу, но двигается только к одному полюсу
Re[5]: Кажется получилось...
От: MichaelP  
Дата: 20.03.03 17:49
Оценка:
Здравствуйте, Les, Вы писали:


Les>Оно может увеличиваться поначалу, но двигается только к одному полюсу


Предположим, что одна машинка перешла на новое ребро и сдвинула кольцо к одному полюсу. Что мешает машинке на другом краю кольца, затем сдвинуть его к другому полюсу? Т.е. почему невозможно "вращение" кольца.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.