Множество точек.
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 12:03
Оценка:
Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.
Ветка выделена из темы Занимательные задачки
16.01.03 23:48: Перенесено из 'Алгоритмы'
Re[2]: Множество точек.
От: Кодт Россия  
Дата: 30.12.02 12:43
Оценка: 23 (3)
Здравствуйте, Pushkin, Вы писали:


P>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.

Параллельные прямые не пересекаются. Доказано Евклидом.
ZANUSSI — лохи! Доказано Лобачевским.


Рассмотрим пространство Римана, т.е. поверхность сферы. Рассмотрим "прямую", т.е. меридиан на этой сфере. Поставим на ней 3 равноудаленные точки.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: Множество точек.
От: Кодт Россия  
Дата: 30.12.02 12:58
Оценка: 8 (1)
P>>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.

Помимо Риманова пространства, этот фокус пройдет и на проекционном (включая точки с координатой +/-oo).
И еще — множество из 1 точки

На самом деле, это вопрос о мощности счетного множества.
Пусть линия проходит слева направо.
Возьмем любую точку из множества (присвоим ей номер 1). Она является серединой какого-то отрезка, следовательно, справа от нее есть еще одна точка (присвоим ей номер 2).
И так далее.
Причем мы не рассматривали то, что находится слева!

Таким образом, существует некоторое счетное подмножество (отображаемое на множество натуральных чисел) нашего множества точек.
Поэтому наше множество по меньшей мере счетно. А следовательно, бесконечно.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: Множество точек.
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 12:59
Оценка:
Здравствуйте, Кодт, Вы писали:

P>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими


К>Рассмотрим пространство Римана, т.е. поверхность сферы. Рассмотрим "прямую", т.е. меридиан на этой сфере. Поставим на ней 3 равноудаленные точки.


Отрезок — часть прямой линии между двумя точками. (Математика, 2-й класс)
Много знаний — много печали
Re[4]: Множество точек.
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 13:31
Оценка:
Здравствуйте, Кодт, Вы писали:

P>>>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.


К>Пусть линия проходит слева направо.


А кто говорил о линии?
Re[5]: Множество точек.
От: Кодт Россия  
Дата: 30.12.02 13:43
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>>>>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.


К>>Пусть линия проходит слева направо.


P>А кто говорил о линии?


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

Для многомерного пространства — то же самое.

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

Заметь, что я перешел к более сильному утверждению: не существует конечного множества точек таких, что каждая точка лежит на отрезке между двумя другими.
Очевидно, что центр отрезка лежит на нем самом.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[5]: Множество точек.
От: MichaelP  
Дата: 30.12.02 13:45
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


P>>>>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.


К>>Пусть линия проходит слева направо.


P>А кто говорил о линии?


Если решение существует, то его проекция на любую прямую тоже будет решением. Т.ч. можно ограничиться линией.
Re[6]: Множество точек.
От: Кодт Россия  
Дата: 30.12.02 13:48
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Если решение существует, то его проекция на любую прямую тоже будет решением. Т.ч. можно ограничиться линией.


Не совсем. Некоторые точки могут спроецироваться в 1.
Патологический случай — когда бесконечное число точек на прямой проецируются в 1 точку на пенпердикуляре.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[6]: Множество точек. бомбочка
От: Кодт Россия  
Дата: 30.12.02 13:50
Оценка:
Давайте же отщеплять ветки!
Заодно протестируем фичу

ЗЫ
пока что значок бомбочки не прорисовывается, но это нам не помеха.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[6]: Множество точек.
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 13:55
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Принцип здесь такой: на пространстве задается отношение строгого порядка. Например, последовательное сравнение координат.

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

Хорошо-хорошо. Я просто предпочитаю проще это говорить — в любом конечном множестве есть самая левая точка, а если их много, то из них самая верхняя, а если и их много, то самая ближняя (по Z).

К>Заметь, что я перешел к более сильному утверждению: не существует конечного множества точек таких, что каждая точка лежит на отрезке между двумя другими.


Да, конечно.
Re[6]: Множество точек.
От: Vi2 Удмуртия http://www.adem.ru
Дата: 30.12.02 14:01
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Хорошо. Возьмем любую точку (#1), проведем через нее вертикаль.
К>Если отрезок, серединой которого она является, не вертикален, то один из концов (#2) лежит справа от вертикали. Перейдем к нему.
К>Если же он вертикален — возьмем верхний конец (#2) и повторим наши изыскания.

Для чего такие сложности? Достаточно сказать, что существуют по крайней мере 2 ("другие") точки, как появляется линия, соединяющая их. (Либо она не существует либо еще какие-нибудь не-евклидовые казусы)
И далее ...
Vita
Выше головы не прыгнешь, ниже земли не упадешь, дальше границы не убежишь! © КВН НГУ
Re[7]: Множество точек.
От: MichaelP  
Дата: 30.12.02 14:04
Оценка:
Здравствуйте, Кодт, Вы писали:

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


MP>>Если решение существует, то его проекция на любую прямую тоже будет решением. Т.ч. можно ограничиться линией.


К>Не совсем. Некоторые точки могут спроецироваться в 1.

К>Патологический случай — когда бесконечное число точек на прямой проецируются в 1 точку на пенпердикуляре.

Я не зря сказал: "На любую прямую". Если кол-во точек конечно, то и конечно множество прямых их соединящих. Следовательно, мы всегда можем выбрать прямую не ортогональную всем этим прямым.
Более того, даже если множество точек счетно. Для простоты рассмотрим плоскость. Так как множество угловых коэф-тов всех соединяющих прямых тоже счетно -> не всюду плотно -> можно найти прямую для проекции.
Re[7]: Множество точек.
От: Кодт Россия  
Дата: 30.12.02 14:20
Оценка:
Здравствуйте, Vi2, Вы писали:

Vi2>Здравствуйте, Кодт, Вы писали:


Vi2>

К>>Хорошо. Возьмем любую точку (#1), проведем через нее вертикаль.
К>>Если отрезок, серединой которого она является, не вертикален, то один из концов (#2) лежит справа от вертикали. Перейдем к нему.
К>>Если же он вертикален — возьмем верхний конец (#2) и повторим наши изыскания.

Vi2>Для чего такие сложности? Достаточно сказать, что существуют по крайней мере 2 ("другие") точки, как появляется линия, соединяющая их. (Либо она не существует либо еще какие-нибудь не-евклидовые казусы)
Vi2>И далее ...

Дело в том, что эти "2 другие точки" могут быть уже задействованы. И фокус здесь именно в том, что в евклидовом пространстве есть отношение строгого порядка, позволяющее эффективно отсекать уже проверенные точки.
А в римановом пространстве — нет. Поэтому мы, взяв 3 точки на замкнутой линии, можем колбаситься по ним сколько угодно.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[2]: Множество точек.
От: Atilla Россия  
Дата: 30.12.02 15:56
Оценка:
Здравствуйте, Pushkin, Вы писали:


P>Доказать, что не существует конечного множества точек, в котором каждая точка есть середина отрезка между какими-то двумя другими.


Рассмотрим функцию от 2-х точек: f(x1, x2)=|x1-x2|.
Т.к. множество пар конечно, на некоторой паре достигается максимум этой функции. Пусть достигается на паре (a,b). Но по условию точка, допустим, a, — есть середина отрезка (c,d), причем |c-d|>0 (считаем, что точки не совпадают), а в этом случае(*) max(|b-c|, |b-d|)>|a-b|, т.е. (a,b) — никакой не максимум.

(*) это верно для Евклидова пространства. Для других — не факт.
<< RSDN@Home 1.0 beta 4 >>
http://forum.buhpravda.ru/images/smilies/umnik.gifКр-ть — с.т.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.