Две задачки для школьников.

[ET]

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

[Коровьев]

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

[ewert]

Коровьев писал(а):

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

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

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

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

[Коровьев]

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

[ewert]

Коровьев писал(а):

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

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

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

[worm2]

ewert писал(а):

и уж до кучи: а как минимизировать максимальное расстояние до прямой?

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

[ewert]

worm2 писал(а):

ewert писал(а):

и уж до кучи: а как минимизировать максимальное расстояние до прямой?

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

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

[TVS]

Коровьев писал(а):

Вообще-то 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.

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

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

[Коровьев]

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

[TOTAL]

Коровьев писал(а):

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

Мало данных.

[bot]

Коровьев писал(а):

Чему равен модуль определителя четвёртого порядка все элементы которого равны $\pm 1$, если он не равен нулю?

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

[Коровьев]

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 \]

Повторив процедуру получим матрицу восьмого порядка. И т.д.

[ИСН]

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

[maxal]

Коровьев писал(а):

Максимума модуля

\[ n^{\frac{n}{2}} \]

такие определители достигают только при порядке $n=2^m$

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

[ИСН]

А, Вы уже давали ссылку, извините, забыл. Расплодилось этих одинаковых тем...