4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 18.03.03 08:40
Оценка: 31 (4)
По периметрам граней правильного тетраэдра ездят 4 машины.
Причём все по часовой стрелке (если смотреть на грань).
Все машины едут всё время с одинаковой скоростью.
Но каждая может в начале выбрать эту скорость и точку старта.
Неминуема ли катастрофа?

Re: 4 машинки
От: MichaelP  
Дата: 18.03.03 11:35
Оценка: 11 (1)
Здравствуйте, Pushkin, Вы писали:

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

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

Может не самое красивое решение, но, зато, похоже обошелся без постоянства скорости (лишь бы не существовало предела по растоянию):

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

При данных условиях возм три кофигурации
1. Три машины съезжаются к общей вершине. Очевидно, что какая бы не достигла вершины первой, она будет вынуждена поехать навстречу одной из оставшихся.
2. Машины попарно съезжаются к двум вершинам соединеным общим ребром (как на рисунке). Если проанализирвать этот случай, то видно что:
а) либо две машины сталкиваются в вершине, либо (т.к. какая-нибудь обязательно достигнет вершины первой)
б) две машины идут навстречу друг-другу по одному ребру,
в) приходим к случаю 1.
3.Три машины расодятся из общей вершины, оставшаяся ездит по противоположной от вершины грани.
Тогда из симметрии сутуации можно "зафиксировать" четвертую машину.
Тщательный анализ этой ситуации показывает, что мы никогда не получим из него вариант 3. Т.е. как уже доказано, неизбежно приходим к столкновению.
Re[5]: 4 машинки
От: MichaelP  
Дата: 18.03.03 15:34
Оценка: 11 (1)
Здравствуйте, mogadanez, Вы писали:

M>вижу закономерность, граней — 6

M>чтобы разъехлись, нужно каждой машинке 2 грани.

Если грани заменить на ребра , то может и есть.

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

А как на кубе? Машинок — 6, ребер — 12.
Re[3]: Вторая попытка
От: MichaelP  
Дата: 04.04.03 06:10
Оценка: -1
Здравствуйте, Les, Вы писали:

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



Les>
Les>    |               |y
Les>    |               *
Les>    |              / \
Les>    |           u /   \   x
Les>----*----  =>  --*     *--
Les>    |             \   /
Les>    |              \ /
Les>    |               *
Les>    |               |v

Les>    в1              в2
Les>


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


Les>Попробую доказать, что невозможность разъехаться сохраняется и в случае (в).


Les>Смотрим на (в1), (в2). Столкновению должна предшествовать ситуация, когда по всем ребрам извне едут машинки (они управляемы и разбиваться не хотят), иначе они смогут разъехаться, по крайней мере, в случае (в1).

Les>Покажем, что в случае фатальной для (в1) ситуации, столкновение будет и в (в2)
Les>Пусть х — первая из машинок, которая первой въедет в центр. Чтобы машинка, едущая по ребру х выехала "наружу", надо, чтобы машинка, едущая по ребру у, въехала внутрь. Машинка, ездящая внутри, не должна занимать ни ребро, по которому едет х, ни ребро, по которому едет у.
Les>Чтобы машинка, едущая по ребру у выехала "наружу", надо, чтобы машинка, едущая по следующему против часовой стрелки ребру, въехала внутрь... и т.д.
Les>Таким образом мы наращиваем список ребер, запрещенных для внутренней машинки, причем въехать на хвост она не может по причине ориентации по часовой стрелке.

Думал я в этом направлении, правда в обратную сторону. Т.е. я пытался доказать, что если существует решение, то оно будет существовать и на грани со "схлопнутой" вершиной.
А теперь опровержение :
Предположим, что к грани подъехали машинки x, u, при этом машинки y,w находятся где-то далеко на своих гранях и не мешают проехать x, u. Затем аналогично проезжают y, w.
Re: 4 машинки
От: MichaelP  
Дата: 18.03.03 10:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

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

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

P>


Начальная ориентация и распределение по ребрам машин произвольны?

Если начальная ориентация и расположение машин такие как на рисунке, то для катастрофы, имхо, даже постоянства скорости не надо, лишь бы она нулю не была равна.

А если нет, то серьезнее думать надо...
Re: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 10:12
Оценка:
Здравствуйте, Pushkin, Вы писали:

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

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

P>


часть 1.

рассмотрим какие либо 2 машинки. например желтую(обазначим ее 1) и зеленую (2)
чтобы они ехали бесконечно долго бес столкновений, нужно выбрать скорость машинок равной.
иначе получаем при :
1. V1*3>V2 crush на первом же круге, 1 машина проедет круг пока вторая будет телепаться по общей грани.
2. при V1*k>V2, где k<3 V2, будет каждый круг проезжать на K граней больше и при накоплении этой разницы до 3 — crush, например если V2>V1 в 1.5 раза, краш будет макс через 2 круга.
3. аналогично при разниццах в пользу 2 машины.

Часть 2. теперь мы знаем приемлимые скорости машинок, и можем попробовать их раставить, но эт после рекламы, много работы...
... << RSDN@Home 1.0 beta 6a >>
Re[2]: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 10:15
Оценка:
MP>Начальная ориентация и распределение по ребрам машин произвольны?
см условие:

все по часовой стрелке (если смотреть на грань).


Но каждая может в начале выбрать эту скорость и точку старта.

... << RSDN@Home 1.0 beta 6a >>
Re[3]: 4 машинки
От: MichaelP  
Дата: 18.03.03 10:18
Оценка:
Здравствуйте, mogadanez, Вы писали:



MP>>Начальная ориентация и распределение по ребрам машин произвольны?

M>см условие:
M>

M>все по часовой стрелке (если смотреть на грань).


M>

M>Но каждая может в начале выбрать эту скорость и точку старта.


Тогда поставлю и всех на одну грань — и пусть по кругу с одной скоростью ездят!
Re[4]: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 10:21
Оценка:
Здравствуйте, MichaelP, Вы писали:

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


MP>


MP>>>Начальная ориентация и распределение по ребрам машин произвольны?

M>>см условие:
M>>

M>>все по часовой стрелке (если смотреть на грань).


M>>

M>>Но каждая может в начале выбрать эту скорость и точку старта.


MP>Тогда поставлю и всех на одну грань — и пусть по кругу с одной скоростью ездят!

брррр... каждая выбирает точку на своем периметре как я понял! на рисунке цветом обозначено.
... << RSDN@Home 1.0 beta 6a >>
Re[5]: 4 машинки
От: MichaelP  
Дата: 18.03.03 10:24
Оценка:
Здравствуйте, mogadanez, Вы писали:

MP>>Тогда поставлю и всех на одну грань — и пусть по кругу с одной скоростью ездят!

M>брррр... каждая выбирает точку на своем периметре как я понял! на рисунке цветом обозначено.

Вот поэтому я уточнения и прошу!
Т.к. если каждая выбирает на своем ребре, то могу доказать неизбежность катастрофы даже без постянства скоростей.
Re[6]: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 10:32
Оценка:
Здравствуйте, MichaelP, Вы писали:

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


MP>>>Тогда поставлю и всех на одну грань — и пусть по кругу с одной скоростью ездят!

M>>брррр... каждая выбирает точку на своем периметре как я понял! на рисунке цветом обозначено.

MP>Вот поэтому я уточнения и прошу!

MP>Т.к. если каждая выбирает на своем ребре, то могу доказать неизбежность катастрофы даже без постянства скоростей.

имхо даже если оставить 2 машины с разными скоростями они столкнутся через 3/M кругов более медленной машины, где М — дробное кол-во граней на которые быстрая машина обгоняет медленную.
... << RSDN@Home 1.0 beta 6a >>
Re[6]: 4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 18.03.03 10:41
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Вот поэтому я уточнения и прошу!


Ну прекрати , каких ещё тебе уточнений надо? Всё же ясно. Машинки "привязаны" каждая к своей грани. Но выбирают свою скорость (которую потом поддерживают постоянной) и точку старта (на периметре своей грани) произвольно в начале катания. Все крутятся в одну сторону, если глядеть из центра их граней в сторону центра. И, конечно, остроумное решение, когда все скорости нулевые идёт вне конкурса
Re: 4 машинки
От: UgN  
Дата: 18.03.03 10:48
Оценка:
Здравствуйте, Pushkin, Вы писали:

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

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

P>



Неминуема.
Для наглядной иллюстрации надо сделать развертку тетраэдра.
Тогда будет видно, что нельзя разместить машинки так, чтобы они не столкнулись.
Я пронумеровал ребра (стороны треугольников) в порядке прохождения их машинками -- всегда есть ребро с совпадающим номером
Т.е., такое, по которому движутся сразу две машинки в противоположных направлениях.
Re[2]: Рис
От: UgN  
Дата: 18.03.03 11:00
Оценка:
UgN>Неминуема.
UgN>Для наглядной иллюстрации надо сделать развертку тетраэдра.
UgN>Тогда будет видно, что нельзя разместить машинки так, чтобы они не столкнулись.
UgN>Я пронумеровал ребра (стороны треугольников) в порядке прохождения их машинками -- всегда есть ребро с совпадающим номером
UgN>Т.е., такое, по которому движутся сразу две машинки в противоположных направлениях.

Извиняюсь за рисунок -- нет времени разрисовывать.
Это один из случаев расстановки.


A, B, C, D — машинки. индексы при буквах — порядок проезда ребра.
Т.е. машинка A начинает движение по ребру A1, а заканчивает на ребре A3
Красным цветом -- коллизия.
Re[2]: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 11:05
Оценка:
M>Часть 2. теперь мы знаем приемлимые скорости машинок, и можем попробовать их раставить, но эт после рекламы, много работы...

продолжим.

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

       1

       4
   2       3


будем обозначать растояние машинок до вершин так Rж2 растояние желтой машинки до вершины 2.
тогда
получаем что начальное расположение машинок должно удовлетворять условиям:
Rж2< Rз2
Rp1<Rж1
Rk3<Rж3
Rж2<Rк2
...//полный список приводить не буду надеюсь понятен ход мыслей, отсюда можем легко вывести противоречие
+
любое растояние <=3*L , L- длиннна грани
... << RSDN@Home 1.0 beta 6a >>
Re[2]: 4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 18.03.03 11:46
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Может не самое красивое решение, но, зато, похоже обошелся без постоянства скорости



Действительно. Я намеренно поставил задачу именно в том виде, каком её встретил.
Хотя она совершенно очевидно "пережата" — они СЛИШКОМ ТОЧНО столкнутся.

Я вижу 2 альтернативных пути ослабления
1) Пусть машинки могут менять скорость как угодно, лишь бы все ехали только вперёд и все проехали по несколько кругов.
2) Пусть скорость каждой постоянная, но тогда достаточно 3-х машинок!

MP>При данных условиях возм три кофигурации


Очень близко к моему решению, но имхо у меня всё-таки существенно прозрачнее.
Нету никаких "и так далее", "тщательный анализ показывает" и.т.д.
Re[3]: 4 машинки
От: MichaelP  
Дата: 18.03.03 11:53
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Очень близко к моему решению, но имхо у меня всё-таки существенно прозрачнее.

P>Нету никаких "и так далее", "тщательный анализ показывает" и.т.д.

Извиняюсь . Рука бойцов писАть устала ...
Re: 4 машинки
От: Les Россия  
Дата: 18.03.03 13:48
Оценка:
Здравствуйте, Pushkin, Вы писали:

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

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

Интересно, что если машинки могут сосуществовать в вершинах, то решение возможно.
Re[3]: 4 машинки
От: MichaelP  
Дата: 18.03.03 15:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>2) Пусть скорость каждой постоянная, но тогда достаточно 3-х машинок!


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

Рассмотрим случай:
Все машинки стартуют из произвольных точек ребер исходящих из одной вершины и едут с одинаковой скоростью.

ИМХО, они никогда не столкнутся
Re[4]: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 15:29
Оценка:
Здравствуйте, MichaelP, Вы писали:

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


P>>2) Пусть скорость каждой постоянная, но тогда достаточно 3-х машинок!


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


MP>Рассмотрим случай:

MP>Все машинки стартуют из произвольных точек ребер исходящих из одной вершины и едут с одинаковой скоростью.

MP>ИМХО, они никогда не столкнутся



вижу закономерность, граней — 6
чтобы разъехлись, нужно каждой машинке 2 грани.
... << RSDN@Home 1.0 beta 6a >>
Re[6]: 4 машинки
От: mogadanez Чехия  
Дата: 18.03.03 15:46
Оценка:
MP>Если грани заменить на ребра , то может и есть.
ну да конечно, вроде и не пятница еще....

а на счет куба, мне кажется что там соотношение будет другое, т.к. на одно совместное ребро приходится 3 свободных,
наверное 1 к 3, т.е. 4 машинки смогут на кубе кататься
... << RSDN@Home 1.0 beta 6a >>
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>


Как я уже писал, условия задачи явно пережаты, их можно ослабить в 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 ребра.

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

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


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

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



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

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


ну как так убедительно?
... << 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>Оно может увеличиваться поначалу, но двигается только к одному полюсу


Предположим, что одна машинка перешла на новое ребро и сдвинула кольцо к одному полюсу. Что мешает машинке на другом краю кольца, затем сдвинуть его к другому полюсу? Т.е. почему невозможно "вращение" кольца.
Re[3]: Кажется получилось...
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 06:25
Оценка:
Здравствуйте, Les, Вы писали:

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

Les>Не судите строго, тут есть пробелы, но идея ИМХО верная.

Идея имхо интересная, но я пока к сожалению не вижу, как получить из этого что-нибудь определённое...
Re[4]: Кажется получилось...
От: MichaelP  
Дата: 21.03.03 06:44
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Идея имхо интересная, но я пока к сожалению не вижу, как получить из этого что-нибудь определённое...


Интересно, что когда "опровергал" эту идею придумал решение, когда машинки разъезжаются, для многогранника с дыркой (т.е. топологически эквивалентным тору):

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

Т.ч. топология, похоже, существенна.
Re[2]: 4 машинки
От: mogadanez Чехия  
Дата: 21.03.03 06:49
Оценка:
M>ну как так убедительно?

видимо не убедительно
... << RSDN@Home 1.0 beta 6a >>
Re[3]: 4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 06:56
Оценка:
Здравствуйте, mogadanez, Вы писали:

M>>ну как так убедительно?

M>видимо не убедительно

Ну ты же понимаешь, каждого своё решение
Автор: Pushkin
Дата: 20.03.03
убеждает больше

На самом деле, мне кажется, у меня то же самое, но только машинка, от которой стартуют рассуждения, помещена не в центр ребра, а в вершину. Что позволило отлынить от рисования дополнительных картинок
Re[4]: 4 машинки
От: mogadanez Чехия  
Дата: 21.03.03 07:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


M>>>ну как так убедительно?

M>>видимо не убедительно

P>Ну ты же понимаешь, каждого своё решение
Автор: Pushkin
Дата: 20.03.03
убеждает больше


P>На самом деле, мне кажется, у меня то же самое, но только машинка, от которой стартуют рассуждения, помещена не в центр ребра, а в вершину. Что позволило отлынить от рисования дополнительных картинок


а не важно, можно и в вершину, если мы на рисунке будем двигать желтую точку вперед по ходу движения, все нарисованые участки будут сдвигаться ровно настолько же...
просто мне показалось, что графически это должно быть нагляднее... ну да ладно.... к вечеру сформулирую что придумал поповоду N угольника.
... << RSDN@Home 1.0 beta 6a >>
Re[5]: Кажется ... да :)
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 08:52
Оценка:


Вот, о чём говорил Les:
Если взять какой-то момент времени и начать приклеивать дкруг г другу грани, смежные по ребру с машинкой, то рано или поздно мы придём к кольцу.

Причём все машинки едут внутрь кольца.
Специально для MichalP уточнение: могут и наружу, но тоже все. В этом случае надо просто иначе развернуть сферу — проколоть в другой точке, и все поедут внутрь (ну или время назад пустить, кому как нравится)

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

Всё. Математических строгостей каждый может навесить столько, сколько требует его математическая совесть А моя, пожалуй, успокоилась.

PS
Оставляю MichaelP удовольствие поразвёртывать на плоскость тор и разобраться с "дырявыми" многогранниками
Re[6]: Кажется ... да :)
От: MichaelP  
Дата: 21.03.03 09:31
Оценка:
Здравствуйте, Pushkin, Вы писали:


Рассмотрим мой "любимый" случай двух состыкованных оснрваниями призм, на боковых ребрах которых стоят машинки.
Возьмем одну из призм — на ней существует кольцо из машинок. Теперь одна из машинок выехала на основание призмы. Что же произошло с кольцом? Оно разрушилось и превратильсь в цепочку упирающуюся в кольцо на другой призме!
Re[7]: Кажется ... да :)
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 09:35
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Рассмотрим мой "любимый" случай двух состыкованных оснрваниями призм, на боковых ребрах которых стоят машинки.

MP>Возьмем одну из призм — на ней существует кольцо из машинок. Теперь одна из машинок выехала на основание призмы. Что же произошло с кольцом? Оно разрушилось и превратильсь в цепочку упирающуюся в кольцо на другой призме!

Прости, не пойму. Может нарисуешь наиболее упрощённо момент перехода кольца в цепочку?
Если это топологически сфера, то всегда можно её проколоть и нарисовать на плоскости...
Re[7]: Кажется ... да :)
От: MichaelP  
Дата: 21.03.03 09:36
Оценка:
MP>
MP>Рассмотрим мой "любимый" случай двух состыкованных оснрваниями призм, на боковых ребрах которых стоят машинки.
MP>Возьмем одну из призм — на ней существует кольцо из машинок. Теперь одна из машинок выехала на основание призмы. Что же произошло с кольцом? Оно разрушилось и превратильсь в цепочку упирающуюся в кольцо на другой призме!

Извиняюсь за "underquoting" в предыдущем сообщении. И, заодно, хочу добавить, что именно этот пример разрушения кольца и привел меня к решению на торе.
Re[8]: Кажется ... да :)
От: MichaelP  
Дата: 21.03.03 09:47
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Прости, не пойму. Может нарисуешь наиболее упрощённо момент перехода кольца в цепочку?

P>Если это топологически сфера, то всегда можно её проколоть и нарисовать на плоскости...

Я еще не встречал человека, который рисовал бы хуже чем я! Но, если подождешь, попробую. А пока постарайся сам представить.
Re[8]: Кажется ... да :)
От: MichaelP  
Дата: 21.03.03 10:27
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Прости, не пойму. Может нарисуешь наиболее упрощённо момент перехода кольца в цепочку?

P>Если это топологически сфера, то всегда можно её проколоть и нарисовать на плоскости...


Прошу прощения за качество .
Re[9]: Кажется ... да :)
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 11:40
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Прошу прощения за качество .


Малевич! Теперь я понял, о чём ты говоришь.

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

И так и должно было быть. Либо расширяющееся кольцо может и дальше расширяться, либо рушится вся логика. Мы же строили кольцо ДЛЯ ЛЮБОГО момента времени. И вроде все согласились, что оно обязано замкнуться.

Цепочек не бывает. Мы вошли на грань через ребро. По грани ездит машинка. Она на другом ребре (не на том, через которое вошли). Можно идти дальше. Так всегда, пока не придём на ту грань, где уже были. В этот момент кольцо замкнётся. Голову, если надо выбросим, чтобы осталось чистое кольцо. Если оно едет наружу, проколем в центре дырку и перерисуем наоборот — поедут внутрь как миленькие. Прекрати нас пугать расходящимися кольцами — смотрим только на одно конкретное, всегда существующее сходящееся. С каждым достижением машинкой вершины оно сходится ещё больше! Вершин в нём становится всё меньше, и рано или поздно их не хватит для размещения машин реже чем по три на каждую.
Re[10]: Кажется ... да :)
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 11:47
Оценка:
Здравствуйте, Pushkin, Вы писали:


P>(три машины катят в в верхнюю внутреннюю вершину).


Здесь я похоже соврал Там же 4 дороги выходят...
Но пафос не отменяется — рассматриваем только одно сходящееся кольцо.
Re[10]: Кажется ... да :)
От: MichaelP  
Дата: 21.03.03 12:27
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Малевич! Теперь я понял, о чём ты говоришь.


Это, когда я говорил, что не встречал людей, которые рисуют хуже меня?

P>Цепочек не бывает. Мы вошли на грань через ребро. По грани ездит машинка. Она на другом ребре (не на том, через которое вошли). Можно идти дальше. Так всегда, пока не придём на ту грань, где уже были. В этот момент кольцо замкнётся. Голову, если надо выбросим, чтобы осталось чистое кольцо. Если оно едет наружу, проколем в центре дырку и перерисуем наоборот — поедут внутрь как миленькие. Прекрати нас пугать расходящимися кольцами — смотрим только на одно конкретное, всегда существующее сходящееся. С каждым достижением машинкой вершины оно сходится ещё больше! Вершин в нём становится всё меньше, и рано или поздно их не хватит для размещения машин реже чем по три на каждую.


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

Одним словом, кольца могут претерпевать разнообразные сложные изменения.
Re[9]: Кажется, увы... :(
От: Les Россия  
Дата: 24.03.03 12:48
Оценка:
Здравствуйте, MichaelP, Вы писали:

P>>Прости, не пойму. Может нарисуешь наиболее упрощённо момент перехода кольца в цепочку?

P>>Если это топологически сфера, то всегда можно её проколоть и нарисовать на плоскости...

MP>

MP>Прошу прощения за качество .
MP> ЗДЕСЬ БЫЛ РИСУНОК. (Кстати имело смысл выбрасывать? Поймет ли браузер что надо брать из кеша?)

Действительно, облом. (Вот только стрелочки-машинки нужно было рисовать на соответствующих плоскостях.) Пусть вначале активно "оранжевое" кольцо. На следующем рисунке активным становится красное. Затем оранжевое, будучи неактивным "восстанавливает конфигурацию", а потом идет переключение с красного на оранжевое. Тем не менее, это не опровержение гипотезы Александра Сергеевича. Но надо уточнить, что ни для какой машинки скорость не должна стремиться к нулю.

А то, что для тора не выполняется, это понятно. Достаточно порубить плоскость в клетку, и в каждой пустить машинку, с одинаковыми скоростями и одним стартовым углом.
Re[10]: Упорствую в оптимизме.
От: Pushkin Россия www.linkbit.com
Дата: 24.03.03 13:20
Оценка:
Здравствуйте, Les, Вы писали:

Les>Действительно, облом.


Давай ещё раз, я по пунктом пройдусь, а кто хочет — пусть вставит "упс".

1) Любой многогранник без дырок можно проколоть в одной из граней и нарисовать на плоскости.

2) Стартовав с любой грани, последовательно ведём цепочку, которая из-за конечного количества граней самопересечётся. Отбросим голову, имеем кольцо.

3) Если машинки кольца едут наружу, проколем его в центре и перерисуем иначе. Т.е. утверждение: всегда найдётся кольцо, едущее на плоскости "все внутрь". Далее рассматриваем только его. (Мне кажется, что все возражения Михаила о рвущихся цепочках базируются на расходящихся кольцах,я предлагаю их забыть)

4) Первая машина в нём, достигшая своей вершины, ломает кольцо. Но

а) оно ломается "внутрь", т.е. не может захватить граней извне (т.к. все ехали внутрь, через сломанный полигон наружу нельзя, остальные тоже не выпустят)

б) кольцо не может разорваться — по построению — от каждой грани есть путь к следующей.

в) кольцо может потерять некий хвост в виде цепочки, но тем быстрее мы придём к цели.

5) Таким образом кольцо уменьшается. Т.е. уменьшается суммарное число граней, входящих в кольцо и охваченных им. При этом по-прежнему все машинки едут внутрь.

6) Рано или поздно мы придём к ситуации, когда кольцо есть просто несколько граней, примыкающих к одной вершине — это кирдык.
Re[11]: Упорствую в оптимизме.
От: Les Россия  
Дата: 24.03.03 15:12
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


Les>>Действительно, облом.


P>Давай ещё раз, я по пунктом пройдусь, а кто хочет — пусть вставит "упс".


P>1) Любой многогранник без дырок можно проколоть в одной из граней и нарисовать на плоскости.


P>2) Стартовав с любой грани, последовательно ведём цепочку, которая из-за конечного количества граней самопересечётся. Отбросим голову, имеем кольцо.


P>3) Если машинки кольца едут наружу, проколем его в центре и перерисуем иначе. Т.е. утверждение: всегда найдётся кольцо, едущее на плоскости "все внутрь". Далее рассматриваем только его. (Мне кажется, что все возражения Михаила о рвущихся цепочках базируются на расходящихся кольцах,я предлагаю их забыть)


P>4) Первая машина в нём, достигшая своей вершины, ломает кольцо. Но


P>а) оно ломается "внутрь", т.е. не может захватить граней извне (т.к. все ехали внутрь, через сломанный полигон наружу нельзя, остальные тоже не выпустят)


P>б) кольцо не может разорваться — по построению — от каждой грани есть путь к следующей.


P>в) кольцо может потерять некий хвост в виде цепочки, но тем быстрее мы придём к цели.


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


P>При этом по-прежнему все машинки едут внутрь.

Упс.

Еще раз рассмотрим пример Михаила. Изначально рассматриваем внешнее кольцо. Все машинки этого кольца дружно делают круг, в процессе этого движения происходит переключение на внутреннее кольцо, внешнее же возвращается в исходную позицию. Делаем то же самое для внутреннего кольца.

Тем не менее, я думаю что это доказательство можно оживить. Внушает оптимизм, что для того чтобы сделать круг, машинкам кольца нужно, чтобы внутренний (или внешний) периметр был свободен, это сильное ограничение. Так что закон явно имеет место быть, надо искать доказательсьво.
Re[12]: Обломали :(
От: Pushkin Россия www.linkbit.com
Дата: 25.03.03 06:20
Оценка:
Здравствуйте, Les, Вы писали:

P>>При этом по-прежнему все машинки едут внутрь.

Les>Упс.
Les>Еще раз рассмотрим пример Михаила.

Да, порисовал дома карандашиком, пожалуй не всё так просто, как я думал...
Re[2]: Вторая попытка
От: Les Россия  
Дата: 03.04.03 17:04
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


Попробуем так: переберем по индукции все плоские графы.
База: граф, состоящий из единственной вершины и петли. Невозможность разъехаться очевидна
Шаг:
а) Разрыв ребра вершиной. Невозможность разъехаться сохраняется
б) Добавление к графу петли. Невозможность разъехаться сохраняется, поскольку рано или поздно кто-нибудь въедет на "внешнюю" сторону петли и столкнется с машинкой, крутящейся в петле
в) "Растягивание" вершины в гранью. О сохранении ниже по тексту. Вот пример:

    |               |y
    |               *
    |              / \
    |             /   \   x
----*----  =>  --*     *--
    |             \   /
    |              \ /
    |               *
    |               |

    в1              в2


Этого достаточно для порождения любого плоского графа, посколько любой плоский граф можно привести к базе обратными операциями

Попробую доказать, что невозможность разъехаться сохраняется и в случае (в).

Смотрим на (в1), (в2). Столкновению должна предшествовать ситуация, когда по всем ребрам извне едут машинки (они управляемы и разбиваться не хотят), иначе они смогут разъехаться, по крайней мере, в случае (в1).
Покажем, что в случае фатальной для (в1) ситуации, столкновение будет и в (в2)
Пусть х — первая из машинок, которая первой въедет в центр. Чтобы машинка, едущая по ребру х выехала "наружу", надо, чтобы машинка, едущая по ребру у, въехала внутрь. Машинка, ездящая внутри, не должна занимать ни ребро, по которому едет х, ни ребро, по которому едет у.
Чтобы машинка, едущая по ребру у выехала "наружу", надо, чтобы машинка, едущая по следующему против часовой стрелки ребру, въехала внутрь... и т.д.
Таким образом мы наращиваем список ребер, запрещенных для внутренней машинки, причем въехать на хвост она не может по причине ориентации по часовой стрелке.
Re: 4 машинки
От: nikholas Россия  
Дата: 04.04.03 08:19
Оценка:
Здравствуйте, Pushkin, Вы писали:

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

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

Я прочитал все доказательства невозможности и не понял ни одного.
Более того, решение существует! Достаточно правильно расставить направления движения машинок.





Прошу прощения за рисунок
Стрелками отмечены начальные положения машинок

ЗЫ очевидно что скорости одинаковые
Re[2]: 4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 04.04.03 08:25
Оценка:
Здравствуйте, nikholas, Вы писали:

N>Я прочитал все доказательства невозможности и не понял ни одного.


Жаль.

N>Более того, решение существует! Достаточно правильно расставить направления движения машинок.


Помимо двух вариантов доказательства невозмости здесь
Автор: Pushkin
Дата: 20.03.03
(пункт 3) приведено и твоё решение. Дело в том, что в исходной задаче требуется, чтобы все ехали по часовой стрелке.
Re[3]: 4 машинки
От: nikholas Россия  
Дата: 04.04.03 08:27
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


N>>Я прочитал все доказательства невозможности и не понял ни одного.


P>Жаль.


N>>Более того, решение существует! Достаточно правильно расставить направления движения машинок.


P>Помимо двух вариантов доказательства невозмости здесь
Автор: Pushkin
Дата: 20.03.03
(пункт 3) приведено и твоё решение. Дело в том, что в исходной задаче требуется, чтобы все ехали по часовой стрелке.


Ну ступил, бывает
Re[4]: 4 машинки
От: Pushkin Россия www.linkbit.com
Дата: 04.04.03 08:39
Оценка:
Здравствуйте, nikholas, Вы писали:

N>Ну ступил, бывает


"Ууупс" — нормальный технический термин
Re[4]: Вторая попытка
От: Les Россия  
Дата: 07.04.03 12:31
Оценка:
Здравствуйте, MichaelP, Вы писали:

...

MP>Думал я в этом направлении, правда в обратную сторону. Т.е. я пытался доказать, что если существует решение, то оно будет существовать и на грани со "схлопнутой" вершиной.

MP>А теперь опровержение :
MP>Предположим, что к грани подъехали машинки x, u, при этом машинки y,w находятся где-то далеко на своих гранях и не мешают проехать x, u. Затем аналогично проезжают y, w.

А я не утверждаю, что машинки столкнуться на некоей данной грани. Я утверждаю, что _найдется_ такая вершина, что.. . И доказываю так: если таковая находилась раньше, то найдется и после.

Да, еще у меня был маленький ошибка: не рассмотрел случая кратных ребер. Решается так — считать пространство между кратными ребрами гранью (вырожденной). Да и петли можно считать таковыми.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.