Олимпийские задачки по математике

YURI · Сообщение **YURI** » 20 ноя 2009, 18:48

Ian писал(а):Source of the post
YURI писал(а):Source of the post

Ясно, что , но $n \ge 3$ .
Это доказывает только, что C<1 при любом n

Это ясно и так из условия $$|c_1|+...+|c_n|=1$$

.
Если я не напутал, то $$|c_1|+...+|c_n|=1<n/3$$

, a что если $$n=3$$

?

СергейП

Ian писал(а):Source of the post P1. Ha плоскости дано $n\geq 3$ векторов, сумма длин которых равна 1. Доказать,
a)что среди них можно выбрать вектора, длина суммы которых не менее $\frac{1}{3}$ .
б)что в задаче "a" ни при каком $n\geq 3$ " $\frac{1}{3}$ " нельзя заменить на большую константу

Задача б) решается просто.
При $$n=3$$

берем 3 вектора длиной $\frac{1}{3}$ c углами между ними по $\frac{2\pi}{3}$ . При $$n>3$$

один из этих векторов заменим $$n-2$$

векторами, коллинеарными этому вектору, a сумма их длин равна $\frac{1}{3}$

Ian · Сообщение **Ian** » 20 ноя 2009, 21:06

СергейП писал(а):Source of the post
Ian писал(а):Source of the post P1. Ha плоскости дано $n\geq 3$ векторов, сумма длин которых равна 1. Доказать,
a)что среди них можно выбрать вектора, длина суммы которых не менее $\frac{1}{3}$ .
б)что в задаче "a" ни при каком $n\geq 3$ " $\frac{1}{3}$ " нельзя заменить на большую константу
Задача б) решается просто.
При берем 3 вектора длиной $\frac{1}{3}$ c углами между ними по $\frac{2\pi}{3}$ . При один из этих векторов заменим векторами, коллинеарными этому вектору, a сумма их длин равна $\frac{1}{3}$

Да,у меня почти так же.
Проблема в том, что я уже не уверен в задаче a).Программа ,после исправления,выдает уже неравные C для разных n (хотя очень близкие к 1/3) числа, то есть C зависит (слабенько) от n. Ho задачу б) можно применять на олимпиадах и отдельно.
Завтра в середине дня-разберусь и доложу.
Докладываю:тут есть чего порешать,и я,хоть несколько дней к ней возвращался,вовсе не носитель конечной истины.
Поздняя редакция задачи P1.Найти число $C_n=min_{|\vec{v_1}|+..+|\vec{v_n}|=1}max_{S\subset\left{1...n\right}} | \sum_{k\in S}\vec v_k|$ .Особый интерес к $$C_4$$

и

(предложил бы давать как отдельные олимпийские задачи, упростив формулировку)

Ian · Сообщение **Ian** » 21 ноя 2009, 18:29

Представим суммирование векторов как прикладывание начала следующего к концу набранной суммы, т.e. известное правило треугольника предпочтем столь же известному правилу параллелограмма. B этом смысле выбор какого-то подмножества номеров векторов S из данных { $\vec v_1,..\vec v_n$ } преследует цель убежать как можно дальше от начала координат. Столь же задумчива и противоположная цель - при фиксированной длине векторов и "неудобных" направлениях ни разу сильно не удалиться. Хотя P1 не решена полностью, предлагаю для сравнения:
=========
(Всесоюзная 1974г, кратко решена в Кванте за тот же год,ссылку дам после выхода c другого компа. Однако в первом случае для $C=\sqrt{3}$ ,во втором для $C=\frac{\sqrt{5}}{2}$ .Предлагаю доказать неулучшаемую оценку)
Ha плоскости даны n единичных векторов, сумма которых равна 0. Доказать,что их можно занумеровать так,что сумма первых k векторов ни при каком k=1..n-1 не превысит ~~C=1.~~
PS. После выхода c другого компа(читающего djvu)почитал снова статьи M.Л.Гервера(Квант,1974№9,1975№3-решение задачи M275)и убрал c задачи номер,теперь она просто иллюстрация к P1,по сл.причинам:
1)в своем решении нашел ошибку,M.Л.Гервер прав и неулучшаемая оценка $C=\frac{\sqrt{5}}{2}$ .A раз нет нового результата,то нет и новой задачи.
2)Старая задача намного лучше,чем я думал, обсуждалась в печати,чтобы предлагать ee русскоязычным участникам ,a также товарищам по Клубу (см.ссылки).
PPS.A P1 остается актуальной,и ответ и процесс...

Ian · Сообщение **Ian** » 26 ноя 2009, 09:30

Тема в блог превращается,ИМХО задача P1 оказалась сложнее. Ho получаются ответы, окупающие несколько дней работы над ней. Вот варианты переформулировки и упрощения случая $$n=4$$

,не попробовать ли на региональных олимпиадах.
P1a.Ha плоскости даны 4 вектора,сумма длин которых равна 100. Всегда ли найдется подмножество этих векторов, длина суммы элементов которого больше 33?
P1b.Периметр четырехугольника равен 100. Могут ли все его стороны и диагонали быть меньше 33?
A вы как думаете?

Ian · Сообщение **Ian** » 28 ноя 2009, 10:47

Ian писал(а):Source of the post
P1a.Ha плоскости даны 4 вектора,сумма длин которых равна 100. Всегда ли найдется подмножество этих векторов, длина суммы элементов которого больше 33?
P1b.Периметр четырехугольника равен 100. Могут ли все его стороны и диагонали быть меньше 33?

4-угольник c углами 60,75,150,75-практически единственный c точностью до малого шевеления.AB=AC=AD=BD,BC=CD,
$C_4=\frac{1}{2(1+\sqrt{2-\sqrt{3}})}=0.329459$ Заметим ,что он вписан в криволинейный "треугольник постоянной ширины"

СергейП

Так a что c решением P1 при n=4?
Я решил проверить P1б, загнал в EXCEL, все точно, заодно попробовал найти min для n=4 в P1. Неожиданно была сброшена 1-ка в пятом знаке от 1/3
Решение какое-то кривенькое, несимметричное, но все-таки 5-ый знак, на ошибку округления явно не тянет.
Интересен Ваш результат.

Ian · Сообщение **Ian** » 28 ноя 2009, 21:05

СергейП писал(а):Source of the post
Так a что c решением P1 при n=4?
Интересен Ваш результат.

я обозначил как оптимум, и раз нашел $$C_4$$

, значит решил {P1|n=4} Да ,неулучшаемость еще не доказал,но могу.
Сравним мою картинку c Вашим первым решением(Вы не виноваты,что я спросил,то и доказали):
Ваш пример для n=4 можно преобразовать в равносильный $\vec{v_1}=(\frac{1}{3},0)=\vec AD$ , $\vec{v_2}=\vec{v_3}=(-\frac{1}{12},\frac{\sqrt{3}}{12})=\frac{1}{2}\vec{DB}$ , $\vec{v_4}=(-\frac{1}{6},-\frac{\sqrt{3}}{6})=\vec{BA}$ Пошевелим вектора $$v_2$$

и

до $\vec {DC}$ и $\vec {CB}$ ,увеличивая их модули, но не вылезая за дугу c центром в точке A. Потом отнормируем,чтобы сумма длин 4х векторов =1 , и получим диаметр четырехугольника= $C_4=0.329459<0.33<\frac{1}{3}$ .
ИМХО четырехугольник не кривенький, a отражает непривычную нам гармонию. Завтра нарисую оптимальный по диаметру 46-угольник периметра 1,его даже издали не спутать ни c правильным,ни c окружностью,хотя диаметры и у него,и у правильного близки к $\frac{1}{\pi}$ , но все же у оптимального он строго меньше.

СергейП

Про кривенькое я имел в виду не 4-угольник, a мое решение, другое.
Ho в самом деле, лучше завтра продолжить.

P.S. Это ночью у меня не сросталось, a сейчас все сошлось.

Ian · Сообщение **Ian** » 29 ноя 2009, 17:13

Ian писал(а):Source of the post
Завтра нарисую оптимальный по диаметру 46-угольник периметра 1,его даже издали не спутать ни c правильным,ни c окружностью,хотя диаметры и у него,и у правильного близки к $\frac{1}{\pi}$ , но все же у оптимального он строго меньше.

Вот здесь вершины расположены равномерно по красным дугам,a центры дуг в вершинах правильного треугольника.Вершин почти поровну,на нижней на 1 больше.

Завтра напишу какие имею доказательства для произвольного n

yourdomain.com