Задача: расстояния между точками на прямой

Артёмка, 597 просмотров

Пусть у нас есть на прямой несколько точек и мы нашли между ними все расстояния. Можно ли передвинуть эти точки на прямой так, чтобы между точками с максимальным расстоянием расстояние стало минимальным, между точками со вторым по величине расстоянием стало предпоследним по величине и т.д., между точками с минимальным расстоянием расстояние стало максимальным (что-то вроде обратной сортировки расстояний). Если можно, то как это сделать алгоритмически?

Более строго:
Допустим, у нас есть n чисел: x_1, ..., x_n. Всегда ли можно ли найти такие числа y_1, ... y_n, что для любых 1<= i, j, k, l <=n
если |x_i - x_j| < |x_k - x_l|, то обязательно |y_i - y_j| > |y_k - y_l| и
если |x_i - x_j| = |x_k - x_l|, то обязательно |y_i - y_j| = |y_k - y_l|.
a_b - это "a" с нижним индексом "b".

И если нельзя, можно ли это сделать с набором точек, где нет одинаковых расстояний?

Примечание:
Да, с баллами это я облажался. Тому, кто приведет пример алгоритма, или докажет, что это невозможно, отдам столько, сколько ему надо.

Примечание:
Баллы тут: http://otvety.google.ru/otvety/thread?tid=7332fb25088c9768

Примечание:
Задача решена.

Примечание:
zZoMROT, три ПАРЫ точек с МИНИМАЛЬНЫМИ расстояниями.

Примечание:
zZoMROT
В лемме говорится, что если взять четыре точки, то их нельзя расположить так, чтобы расстояния между первой и второй, первой и третьей, первой и четвертой были минимальными среди всех расстояний. Это раз. В наборе (-1000, 1, 2, 3) точка -1000 входит в три максимальных расстояния. Это два. Если бы можно было передвинуть эти точки так, как я описал в задаче, то после перемещения точка, которая раньше была -1000, стала бы входить в три пары с минимальными расстояниями. А это невозможно по лемме.
Короче, читай внимательней, и всё станет ясно.

Примечание:
zZoMROT
Картинка - это замечательно, но по условию все точки лежат на одной прямой.

Примечание:
Иван Козначеев,
> расстояния
> (12)=1, (13)=4, (14)=6, (23)=3, (24)=5, (34)=2
> тогда по условию задачи должна иметься перестановка точек, такая, что после перестановки расстояния будут равны
> (12)=6, (13)=3, (14)=1, (23)=4, (24)=2, (34)=5
По условию задачи расстояния не должны быть такими же, как и раньше, просто максимальное должно перейти в минимальное и т.д, а сами расстояния могут стать произвольными. Вы немного неправильно поняли условие. Но в любом случае, задачу уже решили здесь: http://otvety.google.ru/otvety/thread?tid=7332fb25088c9768

Ответы:

bestvikki

согласна с Suser
Это тем более аналитическая геометрия по моему ))

zZoMROT

Создадим отображение f: X -> Z слейдующим образом: f(x_i)=i

Пazitiv

Для решения составляется N-ный цикл, в расчете расстояний он зациклится. Объясню почему. При передвижении N-1 точки по прямой в место, наиболее удаленное от N -точки, всегда найдется N-2 точка, которая в паре с N-1 должна быть отдалена от N точки. А двигая пары точек, решение найти нельзя, т.к. расстояние м/у ними = const

zZoMROT

>> Лемма: три пары точек с тремя самыми маленькими расстяниями не могут иметь общую точку.
(то есть иметь вид xi-xj, xi-xk, xi-xm). Вроде очевидно (от противного).

zZoMROT

Дополнение #4
так а почему не может-то быть? ))
>> Рассмотрим точки -1000, 1, 2, 3
как я понял рассматривается прямая в этом частном случае ↑
[-1000]----------------------------[1]----[2]----[3]
у трех самых коротких растояний есть общие точки (1.2), (2.3), (1.3)

zZoMROT

но для любых ли 4 точек это верно?
если положить, что
точка (1)=т.А
точка (2)=т.В
точка (4)=т.D
а точка (3) принадлежит отрезку ОМ, то три минимальных расстояния имеют общую точку (1)

zZoMROT

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

zZoMROT

ой xD
не (1) общая точка, а точка (3), ибо наименьшие отрезки - (3.1), (3.2), (3.4): M'B, M'A, M'D, где M' in OM

zZoMROT

Дополнение #6
О_0 да. неправ :-)
что-то я упустил в условии xD
но если будете решать в на плоскости / в пространстве, то смело пользуйтесь моим доказательством
Спасибо за разъяснения!

Иван Козначеев

случай 1 и 2 точек не рассматриваем, как тривиальные

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.