Страница 1 из 2
Опять МФТИ
Добавлено: 16 дек 2019, 05:46
Ian
3-6 курс.4.
Предположим, в единичном шаре некоторого евклидова пространства находится [math]2m точек [math]x_1,...x_{2m}. Докажите, что их можно разбить на два множества по [math]m точек каждое таким образом, что центры масс этих множеств окажутся на расстоянии не более [math]\frac 2{\sqrt m} друг от друга
Соображения по решению.
Для [math]2m точек можно найти [math](2m-1)-мерную гиперплоскость, содержащую все точки, в сечении гиперплоскостью любого единичного шара получится шар радиуса не больше 1, поэтому можем далее считать, что размерность пространства равна [math]2m-1.
Например [math]m=2, для тетраэдра , вписанного в единичный шар, минимальное расстояние между серединами противоположных ребер у правильного тетраэдра,[math]d=\frac{2}{\sqrt{3}}<\sqrt{2}-требуемая оценка не для всех [math]m является точной
Пусть перемещением одной точки мы хотим максимально испортить возможность сделать центры тяжести близко. Тогда возьмем гиперплоскость, содержащую остальные точки, и перпендикулярную ей ось через их центр тяжести. [math]2m-ю точку отодвинем на этой оси так далеко от гиперплоскости, как позволяет объемлющий шар, на некоторое расстояние [math]d_{2m} Тогда мы точно можем сказать, что проекции центров тяжести на эту ось находятся на [math]\frac 1md_{2m} друг от друга, ведь одно множество содержит двинутую точку, другое нет.
А что изменяется - при оптимальном движении и гиперплоскость должна немного отодвинуться от центра шара и в сечении дать шар чуть меньшего диаметра (как плоскость основания вписанного правильного тетраэдра отодвинута от центра вниз, а вершина вверх до упора в шар). Попробовать отодвинуть 2 точки, каждую по своей новой координате, и будет какая-то рекуррентность по [math]m для конструкций . И сделать из этого рекуррентность для оценок
Опять МФТИ
Добавлено: 16 дек 2019, 12:33
peregoudov
А размерность евклидова пространства какая? Может быть, тут надо какие-то неравенства для первого и второго моментов употребить?
Опять МФТИ
Добавлено: 16 дек 2019, 15:45
Ian
судя по тексту, размерность как угодно велика. "Евклидово" -значит расстояние считается по теореме Пифагора.
Я показал, что размерность выше 2m-1 смотреть не стоит
Например, как частный случай может быть задача про 4 точки в шаре в двадцатимерном пространстве. Но тогда существует трехмерная гиперплоскость, содержащая все 4 точки, в пересечении с шаром она дает трехмерный шар радиуса не больше 1, и можно решать в нем.
Опять МФТИ
Добавлено: 18 дек 2019, 14:13
peregoudov
Да, я, как всегда, из вашей рваной речи не понял, о чем вы. Теперь понял с размерностью.
Меня в этой задаче смущает необходимость выбора. Нужно сформулировать какой-то критерий и доказать его. Причем просто добавлять точки не получится, потому что добавление новой пары может потребовать кардинально перестроить прежнее разбиение. Нужно начинать с того, что все точки уже даны. Была у меня еще идея вместо исходных точек рассматривать центры масс всех выборок m из 2m, но она пока ничего не дала...
Опять МФТИ
Добавлено: 18 дек 2019, 17:34
peregoudov
Собственно, похоже, что сработала еще одна идея: если не знаешь, как выбрать, попробуй доказать некую оценку для суммы всех вариантов, тогда из нее будет следовать оценка для по крайней мере одного из слагаемых.
Обозначим через
радуис-векторы отдельных точек, а через
--- радиус векторы всевозможных центров масс выборок m из 2m точек. Через
обозначим центр масс всех 2m точек, он же --- центр масс всех центров масс. Тогда, если я правильно сосчитал (считал долго и муторно, но мне кажется, это должно быть как-то очевидно из матстатистики)
Сумму справа вроде бы можно мажорировать единицей, тогда по крайней мере для одной
должно выполняться
А расстояние между
и центром масс остатка вдвое больше.
Опять МФТИ
Добавлено: 18 дек 2019, 21:59
Ian
peregoudov писал(а): мне кажется, это должно быть как-то очевидно из матстатистики)
Есть такая формула в дисперсионном анализе -общая дисперсия равна сумме межгрупповой и средней внутригрупповой дисперсий. Это результат сложного раскрытия скобок в сумме квадратов.
Группы будем считать - всевозможные наборы m точек. Каждая точка получается повторена в ген.совокупности ровно
[math]C^{m-1}_{2m-1} раз
Межгрупповая средняя совпадает с общей средней, поэтому межгрупповая дисперсия и общая дисперсия считаются от одного центра
[math]c_0. А внутригрупповые средние могут быть разные и куда их приткнуть
Опять МФТИ
Добавлено: 19 дек 2019, 02:28
zykov
Вроде похоже на правду. По крайней мере для тетраэдра совпадает с экстремумом
.
Это более строгая оценка, чем требовалось -
.
Наверно они имели ввиду какое-то другое, более простое, решение...
Опять МФТИ
Добавлено: 19 дек 2019, 11:40
peregoudov
Ian писал(а):Source of the post А внутригрупповые средние могут быть разные и куда их приткнуть
Я не понял, вы что-то имеете против моего решения?
Ian писал(а):Source of the post Каждая точка получается повторена в ген.совокупности ровно
раз
Собственно, так и считалось. Давайте тогда напишу детали расчета, раз возникают вопросы.
Но вообще из матстатистики результат довольно очевидный. Если у нас есть n измерений, а дисперсия каждого измерения
, то дисперсия среднего
. А тут как бы численная реализация: дисперсия считается по куче средних, взятых по разным выборкам.
zykov писал(а):Source of the post Наверно они имели ввиду какое-то другое, более простое, решение...
Мне кажется, идея была именно такая, как я написал выше. Просто не были уверены, какое число брать: размер выборки или размер полной совокупности.
Запишем среднее по выборке
в виде
Здесь
--- вектор длины 2m из нулей и единиц, среди компонент m единиц и m нулей. Теперь "дисперсия средних" представляется в виде
Если
, то члены суммы отличны от нуля при
и произвольных остальных
, всего
комбинаций. Если
, то члены суммы отличны от нуля при
,
и произвольных остальных
, всего
комбинаций. Итого
Подставляя, получаем
Добавляем ко второй сумме диагональную часть и вычитаем такую же из первой
Первая сумма в результате дает
, вторая
, окончательно
Опять МФТИ
Добавлено: 19 дек 2019, 18:26
zykov
Да, у меня так же вышло.
Последний шаг лишний.
Вот это -
- уже нельзя мажорировать единицей (оно может быть и больше 1, но не больше 4).
Достаточно так:
Если известно, что
не равно нулю, то просто оценка будет ещё строже:
Опять МФТИ
Добавлено: 19 дек 2019, 18:27
Ian
peregoudov, спасибо за содержательный пост
Вот еще одна
3-6 курс
5. Докажите неравенство[math]\sum_{k=1}^n(x_k-x_{k-1})^2\geq 4\sin^2\frac{\pi}{2n}\sum_{k=0}^nx_k^2 для любых действительных чисел [math]x_0,x_1,...x_n, для которых [math]x_0=x_n=0
Эту решил но сложным путем
Опять МФТИ
Добавлено: 19 дек 2019, 18:41
zykov
Это как?
- это квадрат вектора
, который как известно не зависит от базиса.
- это квадрат вектора
(линейный оператор от
- дискретная производная), который так же не зависит от базиса.
Переходим просто в другой базис - дискретное преобразование Фурье. Там оператор дискретной производной будет диагональным.
Опять МФТИ
Добавлено: 20 дек 2019, 04:42
Ian
Поправил в условии коэффициент.
И сразу шаг в сторону непрерывной задачи [math]\int_0 ^1(x'(t))^2dt\to\min,\int_0 ^1(x(t))^2dt=1,x(0)=x(1)=0, почему мы с Вами 2 раза уже в предыдущих темах там Фурье не применили (доопределив функцию вне отрезка нулем)
Впрочем, в классе [math]x'(t) из [math]L_2 есть решение еще проще - рассмотрим ее синус- коэффициенты Фурье, сразу видно , что у оптимальной функции только при [math]\sin\pi t он отличен от нуля.
Опять МФТИ
Добавлено: 20 дек 2019, 18:02
peregoudov
Ну да, я ж обычно бессодержательно пишу...
zykov писал(а):Source of the post - это квадрат вектора
, который как известно не зависит от базиса.
- это квадрат вектора
(линейный оператор от
- дискретная производная), который так же не зависит от базиса.
Переходим просто в другой базис - дискретное преобразование Фурье. Там оператор дискретной производной будет диагональным.
Ни фига не понял...
Опять МФТИ
Добавлено: 21 дек 2019, 04:32
zykov
Единственное что надо обиграть, это ограничение на подпространство (проекцию):
, оно же
.
PS: Да, стандартный ход в
DFT - это периодическое дополнение (
). Дискретность
означает периодичность спектра, периодичность
означает дискретность спектра. С этим дополнением будет симметрично - и
, и спектр будут дискретными и периодическими.
Опять МФТИ
Добавлено: 21 дек 2019, 19:45
zykov
В такой форме это можно сделать. "В лоб", как условный экстремум. Но получается несколько тяжеловесно. (Там
комплексные.)
Если доопределить
по-другому - сначала расширить его до интервала от
до
так чтобы было нечётное (
).
А потом уже доопределить периодически от этого двойного интервала (период
) и брать Фурье, то в Фурье только синусы останутся без косинусов. Ограничение
получается автоматом.
В разложении Фурье можно скомбинировать члены, как
. Здесь уже
будут действительные.
Константы уже не будет в разложении (у неё
). Минимальное
будет
, которое и даст минимальную норму после действия оператора.
Экстремальные
будут
.
Опять МФТИ
Добавлено: 22 дек 2019, 20:08
zykov
Ian писал(а):Source of the post И сразу шаг в сторону непрерывной задачи
, почему мы с Вами 2 раза уже в предыдущих темах там Фурье не применили (доопределив функцию вне отрезка нулем)
Да, здесь можно аналогично сделать.
Доопределить
на
нечётным образом, потом доопределить на
периодически с периодом
.
Для периодической функции получим ряд Фурье. Т.к. она нечётная, то амплитуды косинусов будут нулевые (в том числе и амплитуда константы). Останутся только синусы.
Самые маленькие по абсолютной величине собственные значения войдут в
(т.к. константа, которая имеет ещё меньше - нулевое значение - запрещена по чётности).
Опять МФТИ
Добавлено: 22 дек 2019, 23:13
peregoudov
Ну, про циркулянты и Фурье я слыхал. Просто сначала не понял, что
стоит множителем, а не под синусом. Так вы предлагаете трактовать это неравенство как оценку нормы квадратичной формы
? Ее матрица
Раз
и
нулевые, матрицу можно обрезать
Это не циркулянт и преобразованием Фурье не диагонализуется.
Но мне кажется, что тут имелась в виду физика, одномерная цепочка масс, связанных пружинками. Решение для собственного вектора ищется в виде
, для
из каждой строки, кроме первой и последней, получается квадратное уравнение
, так что общее решение
, из первой и последней строк тогда получаем
Немного замучено, но, если учесть, что по теореме Виета
,
, то все упрощается до
так что собственные значения определяются из
или
. Откуда и получаем
,
. Нулевое собственное значение исключено, посколку для него получаем
.
Опять МФТИ
Добавлено: 22 дек 2019, 23:55
peregoudov
Ian писал(а):И сразу шаг в сторону непрерывной задачи [math]\int_0 ^1(x'(t))^2dt\to\min,\int_0 ^1(x(t))^2dt=1,x(0)=x(1)=0, почему мы с Вами 2 раза уже в предыдущих темах там Фурье не применили (доопределив функцию вне отрезка нулем)
Мне кажется, тогда уж проще так:
и получаем задачу на поиск минимума оператора энергии для частицы в яме с бесконечными стенками.
Опять МФТИ
Добавлено: 23 дек 2019, 06:16
zykov
peregoudov писал(а):Source of the post и получаем задачу на поиск минимума оператора энергии для частицы в яме с бесконечными стенками
И как этот минимум ищется?
Так же - через вариационное исчисление (универсальный метод) или, в данном случае, через спектр (
Min-max theorem).
Опять МФТИ
Добавлено: 23 дек 2019, 06:37
zykov
peregoudov писал(а):Source of the post Так вы предлагаете трактовать это неравенство как оценку нормы квадратичной формы
Вовсе нет. Там же русским языком написано: дискретная производная - первая, а не вторая.
А квадрат - это уже для нахождения нормы этого вектора.
Вобщем на википедии всё написано:
Замечание: там
, это наше
.