Об одной фольклорной геометрической задаче

Сообщение №4741 от Михалыч 16 сентября 2002 г. 14:52
Тема: Об одной фольклорной геометрической задаче

Задача.
На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чуществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

Мне известны несколько решений задачи, отличающихся незначительно.
Но, забегая вперед, все они используют метрические свойства плоскости. В связи с этим вопросы.
1. Существует ли неметрическое доказательство? В частности, справедливо ли утверждение задачи для конечных геометрий.
2. Как выглядит обобщение задачи (и ее решение) на случай пространств произвольной размерности?
Именно, пространство размерности d (в рассмотреном случае d=2), линейные многообразия размерности n (в рассмотренном случае - прямые), линейные многообразия размерности m"Ровно сколько" лежит в общем случае.


Отклики на это сообщение:

> Задача.
> На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чуществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

> Мне известны несколько решений задачи, отличающихся незначительно.
> Но, забегая вперед, все они используют метрические свойства плоскости. В связи с этим вопросы.
> 1. Существует ли неметрическое доказательство? В частности, справедливо ли утверждение задачи для конечных геометрий.
> 2. Как выглядит обобщение задачи (и ее решение) на случай пространств произвольной размерности?
> Именно, пространство размерности d (в рассмотреном случае d=2), линейные многообразия размерности n (в рассмотренном случае - прямые),
> линейные многообразия размерности m < n (в рассмотренном случае - точки)
>
> "Ровно сколько" лежит в общем случае?

В предыдущем посте оказалась "зажевана" последняя фраза.


> > Задача.
> > На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чуществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

> > Мне известны несколько решений задачи, отличающихся незначительно.
> > Но, забегая вперед, все они используют метрические свойства плоскости. В связи с этим вопросы.
> > 1. Существует ли неметрическое доказательство? В частности, справедливо ли утверждение задачи для конечных геометрий.
> > 2. Как выглядит обобщение задачи (и ее решение) на случай пространств произвольной размерности?
> > Именно, пространство размерности d (в рассмотреном случае d=2), линейные многообразия размерности n (в рассмотренном случае - прямые),
> > линейные многообразия размерности m < n (в рассмотренном случае - точки)
> >
> > "Ровно сколько" лежит в общем случае?

> В предыдущем посте оказалась "зажевана" последняя фраза.

Попробую предложить свой способ, возможно, один из тех, что Вы имели в виду.
Введем матрицу А n-строк, 2 столбца (для плоскости)
Ai,1=xi/yi, Ai,2=1/yi
Задача:
найти условия существования решение уравнения AX=E, E-единичный вектор, X -вектор размерности 2. Задача из лин. алгебры. Аналогично для произвольных размерностей. Я не вижу здесь принципиальных трудностей, может я чего не понял?
Михалыч, а почему актуально не использовать метрические свойства?


> > > Задача.
> > > На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чу
ществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

> > > Мне известны несколько решений задачи, отличающихся незначительно.
> > > Но, забегая вперед, все они используют метрические свойства плоскости. В связи с этим вопросы.
> > > 1. Существует ли неметрическое доказательство? В частности, справедливо ли утверждение задачи для конечных геометрий.
> > > 2. Как выглядит обобщение задачи (и ее решение) на случай пространств произвольной размерности?
> > > Именно, пространство размерности d (в рассмотреном случае d=2), линейные многообразия размерности n (в рассмотренном случае - прямые),
> > > линейные многообразия размерности m < n (в рассмотренном случае - точки)
> > >
> > > "Ровно сколько" лежит в общем случае?

> > В предыдущем посте оказалась "зажевана" последняя фраза.

> Попробую предложить свой способ, возможно, один из тех, что Вы имели в виду.
> Введем матрицу А n-строк, 2 столбца (для плоскости)
> Ai,1=xi/yi, Ai,2=1/yi
> Задача:
> найти условия существования решение уравнения AX=E, E-единичный вектор, X -вектор размерности 2. Задача из лин. алгебры. Аналогично для произвольных размерностей. Я не вижу здесь принципиальных трудностей, может я чего не понял?
> Михалыч, а почему актуально не использовать метрические свойства?

Что-то не понял.
Вопрос.
Найденное решение (в соответствии с Вашим предложением) гарантирует отсутствие третьей точки на найденной прямой?

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


> Задача.
> На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чуществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

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

А если так:
Для 3 точек очевидно, существуют 3 искомые прямые, следовательно справедливо и для случаев n=4,5. Потом, если для n выполняется, то (n+1)-я точка либо попадает на прямую (существующую для n точек), либо - нет (приехали). Если попала на прямую - выбросим это три точки, тогда для оставшегося множества точек утверждение выполняется по инд. предположению.


> > Задача.
> > На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чуществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

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

> А если так:
> Для 3 точек очевидно, существуют 3 искомые прямые, следовательно справедливо и для случаев n=4,5. Потом, если для n выполняется, то (n+1)-я точка либо попадает на прямую (существующую для n точек), либо - нет (приехали). Если попала на прямую - выбросим это три точки, тогда для оставшегося множества точек утверждение выполняется по инд. предположению.

Не пойдет. Выкидывая три точки СРАЗУ Вы "случайно" можете выкинуть нужную, именно ту которая лежит на искомой "двухточечной" прямой.


Михалыч, а как относиться к двум точкам не лежащим на одной прямой?
Тетраедр, рёбра -- точки, грани --- прямые


> Михалыч, а как относиться к двум точкам не лежащим на одной прямой?
> Тетраедр, рёбра -- точки, грани --- прямые

Не понял вопроса...

Во-первых, "базовая" задача - плоская.
Во-вторых, Вы привели пример конфигурации, в которой "все нормально".
Есть прямая, на которой лежат РОВНО ДВЕ ТОЧКИ множества (таких прямых аж шесть, кажется...)
В чем проблема?
Что есть примеры того, что утверждение задачи справедливо?
Трудно не согласиться....



> > > Задача.
> > > На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чуществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

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

> > А если так:
> > Для 3 точек очевидно, существуют 3 искомые прямые, следовательно справедливо и для случаев n=4,5. Потом, если для n выполняется, то (n+1)-я точка либо попадает на прямую (существующую для n точек), либо - нет (приехали). Если попала на прямую - выбросим это три точки, тогда для оставшегося множества точек утверждение выполняется по инд. предположению.

> Не пойдет. Выкидывая три точки СРАЗУ Вы "случайно" можете выкинуть нужную, именно ту которая лежит на искомой "двухточечной" прямой.

Видимо, я не совсем точно написал с самого начала. Пусть выполняется для n-2,
n-1 и n точек ("базис" индукции n=3,4,5), тогда выполняется (по описанным соображениям) и для n+1 точки. В такой редакции, по-моему, не важно какие точки выбросим - или я не прав?


> > Михалыч, а как относиться к двум точкам не лежащим на одной прямой?
> > Тетраедр, рёбра -- точки, грани --- прямые

> Не понял вопроса...

я говорю об обобщеии на скажем трёхмерное п-во, точками там будем считать прямые, прямыми -- плоскости. Две прямые не лежащие в одной п-ти нам подходят?
Если нет то т. это пример.


> > > > Задача.
> > > > На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чу
> ществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

> > > > Мне известны несколько решений задачи, отличающихся незначительно.
> > > > Но, забегая вперед, все они используют метрические свойства плоскости. В связи с этим вопросы.
> > > > 1. Существует ли неметрическое доказательство? В частности, справедливо ли утверждение задачи для конечных геометрий.
> > > > 2. Как выглядит обобщение задачи (и ее решение) на случай пространств произвольной размерности?
> > > > Именно, пространство размерности d (в рассмотреном случае d=2), линейные многообразия размерности n (в рассмотренном случае - прямые),
> > > > линейные многообразия размерности m < n (в рассмотренном случае - точки)
> > > >
> > > > "Ровно сколько" лежит в общем случае?

> > > В предыдущем посте оказалась "зажевана" последняя фраза.

> > Попробую предложить свой способ, возможно, один из тех, что Вы имели в виду.
> > Введем матрицу А n-строк, 2 столбца (для плоскости)
> > Ai,1=xi/yi, Ai,2=1/yi
> > Задача:
> > найти условия существования решение уравнения AX=E, E-единичный вектор, X -вектор размерности 2. Задача из лин. алгебры. Аналогично для произвольных размерностей. Я не вижу здесь принципиальных трудностей, может я чего не понял?
> > Михалыч, а почему актуально не использовать метрические свойства?

> Что-то не понял.
> Вопрос.
> Найденное решение (в соответствии с Вашим предложением) гарантирует отсутствие третьей точки на найденной прямой?

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

Если точки лежат на поверхности сферы то теорема очевидно не выполняется
например две точки находятся в полюсах.


> > > > > Задача.
> > > > > На плоскости дано конечное число точек, НЕ ВСЕ ИЗ КОТОРЫХ лежат на одной прямой. Доказать, что чу
> > ществует прямая, на которой лежат РОВНО ДВЕ ТОЧКИ данного множества.

> > > > > Мне известны несколько решений задачи, отличающихся незначительно.
> > > > > Но, забегая вперед, все они используют метрические свойства плоскости. В связи с этим вопросы.
> > > > > 1. Существует ли неметрическое доказательство? В частности, справедливо ли утверждение задачи для конечных геометрий.
> > > > > 2. Как выглядит обобщение задачи (и ее решение) на случай пространств произвольной размерности?
> > > > > Именно, пространство размерности d (в рассмотреном случае d=2), линейные многообразия размерности n (в рассмотренном случае - прямые),
> > > > > линейные многообразия размерности m < n (в рассмотренном случае - точки)
> > > > >
> > > > > "Ровно сколько" лежит в общем случае?

> > > > В предыдущем посте оказалась "зажевана" последняя фраза.

> > > Попробую предложить свой способ, возможно, один из тех, что Вы имели в виду.
> > > Введем матрицу А n-строк, 2 столбца (для плоскости)
> > > Ai,1=xi/yi, Ai,2=1/yi
> > > Задача:
> > > найти условия существования решение уравнения AX=E, E-единичный вектор, X -вектор размерности 2. Задача из лин. алгебры. Аналогично для произвольных размерностей. Я не вижу здесь принципиальных трудностей, может я чего не понял?
> > > Михалыч, а почему актуально не использовать метрические свойства?

> > Что-то не поня
л.
> > Вопрос.
> > Найденное решение (в соответствии с Вашим предложением) гарантирует отсутствие третьей точки на найденной прямой?

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

> Если точки лежат на поверхности сферы то теорема очевидно не выполняется
> например две точки находятся в полюсах.

...и "земная ось" является искомой прямой. Не так ли?


Пожалуйста, избегайте излишнего цитирования.


Здравствуйте, Михалыч.

Задача называется "задача Сильвестра".
Я видел три решения (одно у Яглома в "Неэлементарных задачах...", и два у Коксеттера, не помню в каких книжках). Да, все эти доказательства "метрические".
Я могу предложить набросок решения для плоскости, который не использует (явно) метрических свойств. Я решение до конца не доводил, так что оно может содержать пробелы, или вообще быть неверным.
1. Переформулируем в более удобном виде:
Если прямая, проходящая через любые 2 точки данного конечного мн-ва содержит и другие точки этого мн-ва, то все точки лежат на одной прямой.
2. Используем проективную дуальность, заменим прямые на точки, точки на прямые:
Если через точку пересечения любых двух прямых из конечного мн-ва проходят другие прямые из этого мн-ва, то все прямые пересекаются в одной точке.
3. Предположим, что это неверно. Т.е. существует конфигурация, такая что точек пересечения минимум две, и в каждой точке пересекаются минимум три прямые.
Теперь нужно показать, что это противоречит формуле Эйлера, например, отобразив конфигурацию на сферу (?), или присоединив бесконечно удаленную проективную прямую. Здесь вся загвоздка - боюсь, что стогий переход от проективной плоскости (или сферы) к евклидовой потребует метрических свойств.

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


> Здравствуйте, Михалыч.

> Задача называется "задача Сильвестра".
> Я видел три решения (одно у Яглома в "Неэлементарных задачах...", и два у Коксеттера, не помню в каких книжках). Да, все эти доказательства "метрические".
> Я могу предложить набросок решения для плоскости, который не использует (явно) метрических свойств. Я решение до конца не доводил, так что оно может содержать пробелы, или вообще быть неверным.
> 1. Переформулируем в более удобном виде:
> Если прямая, проходящая через любые 2 точки данного конечного мн-ва содержит и другие точки этого мн-ва, то все точки лежат на одной прямой.
> 2. Используем проективную дуальность, заменим прямые на точки, точки на прямые:
> Если через точку пересечения любых двух прямых из конечного мн-ва проходят другие прямые из этого мн-ва, то все прямые пересекаются в одной точке.
> 3. Предположим, что это неверно. Т.е. существует конфигурация, такая что точек пересечения минимум две, и в каждой точке пересекаются минимум три прямые.
> Теперь нужно показать, что это противоречит формуле Эйлера, например, отобразив конфигурацию на сферу (?), или присоединив бесконечно удаленную проективную прямую. Здесь вся загвоздка - боюсь, что стогий переход от проективной плоскости (или сферы) к евклидовой потребует метрических свойств.

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

Здравствуйте и спасибо Б.Б.!

По существу Вашего ответа.
1. Я что-то когда-то делал с использованием прективной двойственности и тоже, как и Вы, до конца не дотянул
2. Рецидив моего интереса к этой задаче, вне связи с метричностью доказательства, связан вот с какими (сырыми) соображениями.
Интересует именно обобщение на высшие размерности.
Пусть есть два конечных множества точек в многомерном пространстве. При априорном предположении и СУЩЕСТВОВАНИИ разделяющей гиперплоскости
существуют "какие-то" алгоритмы ее построения. (В принципе, априорное требование линейной разделимости можно ослабить, но сейчас это не очень важно).
Мне хотелось бы строить гиперплоскость "быстро", в некотором смысле.
Есть смутные подозрения, что такое ускорение может быть получено с использованием многомерной версии задачи Сильвестра, которая обеспечивает(?) редукцию алгоритма к меньшим размерностям.
Буду благодарен (в пределах разумного) за любые соображения по поводу многомерной версии.
Сформулированная задача построения разделяющей гиперплоскости - одна из популярнейших в теории распознавания образов.
С уважением,
vche


> > Если точки лежат на поверхности сферы то теорема очевидно не выполняется
> > например две точки находятся в полюсах.

> ...и "земная ось" является искомой прямой. Не так ли?

Почему любой из меридианов, мы же вроде сфере смотрим. Любая третья точка будет лежать на одном из мередианов.


Естественно, на сфере есть контрпримеры. Например, конфигурация октаэдра - 2 меридиана и экватор.

> > > Если точки лежат на поверхности сферы то теорема очевидно не выполняется
> > > например две точки находятся в полюсах.

> > ...и "земная ось" является искомой прямой. Не так ли?

> Почему любой из меридианов, мы же вроде сфере смотрим. Любая третья точка будет лежать на одном из мередианов.


> > Здравствуйте, Михалыч.

> > Задача называется "задача Сильвестра".
> > Я видел три решения (одно у Яглома в "Неэлементарных задачах...", и два у Коксеттера, не помню в каких книжках). Да, все эти доказательства "метрические".

Михалыч, я тут поговорил со знаюшим товаришем, он сказал, что у Коксетера во "Введении в геометрию" второе доказательство использует только аксиомы "упорядоченной геометрии". Kроме инцидентности используется очень серьезная аксиома об отношении "между".
Он также сказал, что теорема может иметь аналоги в комплексных проективных пространствах, в частности он не сомневается, что она верна в P^3(C).

Не знаю, поможет ли ето Вам.


> > > Здравствуйте, Михалыч.

> > > Задача называется "задача Сильвестра".
> > > Я видел три решения (одно у Яглома в "Неэлементарных задачах...", и два у Коксеттера, не помню в каких книжках). Да, все эти доказательства "метрические".

> Михалыч, я тут поговорил со знаюшим товаришем, он сказал, что у Коксетера во "Введении в геометрию" второе доказательство использует только аксиомы "упорядоченной геометрии". Kроме инцидентности используется очень серьезная аксиома об отношении "между".
> Он также сказал, что теорема может иметь аналоги в комплексных проективных пространствах, в частности он не сомневается, что она верна в P^3(C).

> Не знаю, поможет ли ето Вам.

Еще раз спасибо и "знающему товарищу" - тоже...
Для меня была бы идеальной любая идея о переносе на пространства над полем р-адических чисел.
Но там с "между" должны быть проблемы.
А это отношение, кажется, по существу...
Похоже, что мимо.
Коксетера в своей библиотеке не обнаружил, но точно был...Будем искать.
С уважением
vche


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100