Две задачки для школьников. : Олимпиадные задачи (М) - Страница 2 fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.
 
 
Сообщение30.05.2008, 15:26 


08/05/08
601
Мне другое когда-то предлагали.
Даны n точек и прямая. Найти точку на прямой такую, что сумма расстояний от нее до данных точек минимальна

 Профиль  
                  
 
 
Сообщение30.05.2008, 15:33 
Заслуженный участник
Аватара пользователя


18/12/07
762
Насколько проста задача для одномерного случая и насколько она сложна уже на плоскости.
Задача J.Rosenbaum
Найти точку плоскости, сумма расстояний от которой $n$ до заданных точек минимальна.
Из книги Избранные задачи. Ото Дункель и $K^o$

 Профиль  
                  
 
 
Сообщение02.06.2008, 18:21 
Заслуженный участник


11/05/08
32166
Коровьев писал(а):
Насколько проста задача для одномерного случая и насколько она сложна уже на плоскости.
Задача J.Rosenbaum
Найти точку плоскости, сумма расстояний от которой $n$ до заданных точек минимальна.
Из книги Избранные задачи. Ото Дункель и $K^o$

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

Имеется в виду следующий её вариант:

Найти прямую на плоскости, сумма расстояний от которой до заданных $n$ точек минимальна.

 Профиль  
                  
 
 
Сообщение03.06.2008, 02:00 
Заслуженный участник
Аватара пользователя


18/12/07
762
Вообще-то J.Rosenbaum нашёл только уравнения для минимальной точки.
Естественно, он ввёл функцию
\[
f(x,y) = \sum\limits_{i = 1}^n {\sqrt {(x - x_i )^2  + (y - y_i )^2 } } 
\]
Доказал, что она строго выпукла. Нашёл условия,при которых такая точка существует, а для строго выпуклой функции она единственна. И показал, что частные производные в этой точке обязаны быть равными нулю. Дальше тривиально
\[
\begin{array}{l}
 \sum\limits_{i = 1}^n {\frac{{x - x_i }}{{\sqrt {(x - x_i )^2  + (y - y_i )^2 } }}}  = 0 \\ 
 \sum\limits_{i = 1}^n {\frac{{y - y_i }}{{\sqrt {(x - x_i )^2  + (y - y_i )^2 } }}}  = 0 \\ 
 \end{array}
\]
Но вот решить эту систему, думаю, не реально.
Что до
Цитата:
Найти прямую на плоскости, сумма расстояний от которой до $n$ заданных точек минимальна.

то более используема в экспериментах такая постановка:
Найти прямую, средне квадратичное отклонение от которой до полученных $n$ точек/значений минимально.Эта задача решаема до конца.

p.s.Интересно, что для выпуклого четырёхугольника минимальная точка лежит на пересечении диагоналей.

 Профиль  
                  
 
 
Сообщение03.06.2008, 07:12 
Заслуженный участник


11/05/08
32166
Коровьев писал(а):
p.s.Интересно, что для выпуклого четырёхугольника минимальная точка лежит на пересечении диагоналей.

а как для остальных четырёхугольников? (задачка тоже решаема до конца, и очень легко).

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

 Профиль  
                  
 
 
Сообщение03.06.2008, 12:14 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
ewert писал(а):
и уж до кучи: а как минимизировать максимальное расстояние до прямой?

Да вроде "просто": найти минимальную по длине проекцию выпуклой оболочки точек и через её середину восстановить перпендикуляр...

 Профиль  
                  
 
 
Сообщение03.06.2008, 12:20 
Заслуженный участник


11/05/08
32166
worm2 писал(а):
ewert писал(а):
и уж до кучи: а как минимизировать максимальное расстояние до прямой?

Да вроде "просто": найти минимальную по длине проекцию выпуклой оболочки точек и через её середину восстановить перпендикуляр...

или ещё проще (хотя и дольше): перебрать все средние линии всех треугольников и выбрать наилучшую.

 Профиль  
                  
 
 
Сообщение07.06.2008, 21:56 


07/06/08
1
Коровьев писал(а):
Вообще-то J.Rosenbaum нашёл только уравнения для минимальной точки.

\[
\begin{array}{l}
 \sum\limits_{i = 1}^n {\frac{{x - x_i }}{{\sqrt {(x - x_i )^2  + (y - y_i )^2 } }}}  = 0 \\ 
 \sum\limits_{i = 1}^n {\frac{{y - y_i }}{{\sqrt {(x - x_i )^2  + (y - y_i )^2 } }}}  = 0 \\ 
 \end{array}
\]


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

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

Однако можно построить итерационный процесс (например, основанный на методе Франка-Вульфа). Причем процесс с помощью циркуля и линейки. Когда-то подробно записывала это решение. Где-то лежит.

 Профиль  
                  
 
 
Сообщение11.06.2008, 13:18 
Заслуженный участник
Аватара пользователя


18/12/07
762
Задачка на ужас как мало данных.
Чему равен модуль определителя четвёртого порядка все элементы которого равны $\mp 1$, если он не равен нулю?

 Профиль  
                  
 
 
Сообщение11.06.2008, 14:12 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
Коровьев писал(а):
Задачка на ужас как мало данных.
Чему равен модуль определителя четвёртого порядка все элементы которого равны $\mp 1$, если он не равен нулю?
Мало данных.

 Профиль  
                  
 
 
Сообщение11.06.2008, 14:54 
Заслуженный участник
Аватара пользователя


21/12/05
5932
Новосибирск
Коровьев писал(а):
Чему равен модуль определителя четвёртого порядка все элементы которого равны $\pm 1$, если он не равен нулю?

Давненько это обсуждали здесь
Ответ: 8 или 16.

 Профиль  
                  
 
 
Сообщение12.06.2008, 00:35 
Заслуженный участник
Аватара пользователя


18/12/07
762
bot писал(а):
Коровьев писал(а):
Чему равен модуль определителя четвёртого порядка все элементы которого равны $\pm 1$, если он не равен нулю?

Давненько это обсуждали здесь
Ответ: 8 или 16.

Добавлю по ссылке здесь
Максимума модуля \[
n^{\frac{n}{2}} 
\] такие определители достигают только при порядке $n=2^m$
Есть процедура последовательного получения таких определителей.
Задача 525 из "Сборника задач по высшей алгебре" Фадеева.
Возьмём матрицу второго порядка
\[
\left( {\begin{array}{*{20}c}
   1 & 1  \\
   1 & { - 1}  \\
\end{array}} \right)
\]В ней строки (столбцы) ортогональны.
В этой матрице заменим единицы на матрицу
\[
\left( {\begin{array}{*{20}c}
   1 & 1  \\
   1 & { - 1}  \\
\end{array}} \right)
\]а минус единицу заманим на матрицу
\[
\left( {\begin{array}{*{20}c}
   { - 1} & { - 1}  \\
   { - 1} & 1  \\
\end{array}} \right)
\]Получим матрицу четвёртого порядка в которой строки (столбцы) попарно взаимно ортогональны, и модуль её определителя
\[
\left| {\left| {\begin{array}{*{20}c}
   1 & 1 & 1 & 1  \\
   1 & { - 1} & 1 & { - 1}  \\
   1 & 1 & { - 1} & { - 1}  \\
   1 & { - 1} & { - 1} & 1  \\
\end{array}} \right|} \right| = 16
\]
Повторив процедуру получим матрицу восьмого порядка. И т.д.

 Профиль  
                  
 
 
Сообщение12.06.2008, 07:28 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Как всегда, всё уже придумали до нас...
http://mathworld.wolfram.com/HadamardsM ... oblem.html

 Профиль  
                  
 
 
Сообщение12.06.2008, 07:38 
Модератор
Аватара пользователя


11/01/06
5710
Коровьев писал(а):
Максимума модуля \[
n^{\frac{n}{2}} 
\] такие определители достигают только при порядке $n=2^m$

Это неверное утверждение - наименьшим контрпримером является $n=12$.
А вообще см. http://dxdy.ru/viewtopic.php?p=114143#114143

 Профиль  
                  
 
 
Сообщение12.06.2008, 07:42 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
А, Вы уже давали ссылку, извините, забыл. Расплодилось этих одинаковых тем...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 98 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group