Израильский суперфинал

Ian · Сообщение **Ian** » 23 сен 2019, 16:57

https://drive.google.com/file/d/0B87lCD ... HZnBB/view

: 8910.jpg (127.82 KiB) 29375 просмотра

8ю я сделал, хотя факт был неожиданный.
9ю -есть простая гипотеза об ответе, посчитав определители возникающих линейных систем
10ю - мысли есть
Пояснения. 8.Выпуклость графика смотрит вниз, если бы везде была 2я производная, она была бы неотрицательна.
9.

a_1=0\\a_2+a_3=0\\...
и так далее, а когда индекс превысит n, отнимать от него n

zykov · Сообщение **zykov** » 23 сен 2019, 22:29

На счёт 10, может я условие не так понимаю...

Вот если $n=3$

и

,

. Возьмём

.
Как не выбирай, сумма элементов на $7$

не делится...

zykov · Сообщение **zykov** » 23 сен 2019, 22:36

8 довольно интуитивна - косинус в центре более отрицателен, чем по краям $(0,2\pi)$ .
Из-за выпуклости вниз эти центральные значения имеют меньше вес, чем положительные значения по краям.

Это можно и формально расписать, если интеграл переписать как сумму интегралов по "четверть волнам" (где косинус меняется от экстремума до нуля, или обратно) а для выпуклой функции подставить неравенства.

PS: Выпуклую функцию можно сразу ограничить нулями на концах учитывая что $\int_0^{2\pi} \cos x \; dx = 0$ и $\int_0^{2\pi} x \cos x \; dx = 0$ .

zykov · Сообщение **zykov** » 24 сен 2019, 02:40

Да, для 8 из $n=1$

следует справедливость для остальных $n$

.
Это легко показать заменой переменной интегрирования.
$\int_0^{2\pi}f(t)\cos nt \; dt=\int_0^{2n\pi}f(x/n)\cos x \; dx/n=$
$=(\int_0^{2\pi}f(x/n)\cos x \; dx+\int_{2\pi}^{4\pi}f(x/n)\cos x \; dx+...+\int_{2(n-1)\pi}^{2n\pi}f(x/n)\cos x \; dx)/n$ .

zykov · Сообщение **zykov** » 24 сен 2019, 02:44

zykov писал(а):Source of the post Как не выбирай, сумма элементов на не делится...

Или имеется ввиду, что $0$

делится на $7$

?

Ian · Сообщение **Ian** » 24 сен 2019, 07:11

zykov писал(а):На счёт 10, может я условие не так понимаю...

Вот если и , , . Возьмём .
Как не выбирай, сумма элементов на не делится...

Можно выбирать также знаки, 1+2-3=0, так как дано 6 чисел

\pm 1,\pm 2, \pm 3. Но конечно нельзя выбрать пустое множество или становящееся таким после сокращения противоположных друг другу, для этого и сказано в условии что пару противоположных не включать

Ian · Сообщение **Ian** » 25 сен 2019, 06:26

По предварительным итогам, 10ю не решил никто, максимум наполовину.
Есть

2^{n} комбинаций расстановки знаков в наборе

S=\{\pm a_{1},...\pm a_{n}\} ,а так как

m<2^{n} ,найдутся две комбинации знаков с одинаковым остатком суммы. Тогда разность сумм этих наборов делится на

m, а она имеет вид

2(\pm a_{k_{1}}+...+\pm a_{k_{s}})- нашли набор, удвоенная сумма которого делится на

m.Это более слабое утверждение. Отсюда для

m нечетных все доказано.
Кроме того, для

m=2, для которого более слабое тривиально, доказать можно все:
Тогда

n>1. Если среди

a_{i} есть четное, то выберем в

S только его, если все нечетны, то выберем в

S два из них.

peregoudov · Сообщение **peregoudov** » 25 сен 2019, 15:26

zykov писал(а):Source of the post Да, для 8 из следует справедливость для остальных .

Что выпуклая функция при ограничении на отрезок остается выпуклой, а потому из доказательства для одной волны следует доказательство для произвольного числа волн --- это понятно.

zykov писал(а):Source of the post Это можно и формально расписать, если интеграл переписать как сумму интегралов по "четверть волнам" (где косинус меняется от экстремума до нуля, или обратно) а для выпуклой функции подставить неравенства.

Я понял так:

$\int_0^{2\pi}f(x)\cos x\,dx=\int_0^{\pi/2}[f(x)-f(\pi-x)-f(\pi+x)+f(2\pi-x)]\cos x\,dx.$

Выражение в квадратных скобка положительно в силу выпуклости (среднее по двум внутренним точкам отрезка меньше среднего по его краям).

zykov · Сообщение **zykov** » 25 сен 2019, 17:17

peregoudov писал(а):Source of the post Выражение в квадратных скобка положительно в силу выпуклости

Да.
$f(\pi-x)$ и $f(\pi+x)$ лежат под отрезком с концами $f(x)$

и $f(2\pi-x)$ .

zykov · Сообщение **zykov** » 25 сен 2019, 17:21

Ian писал(а):Source of the post Отсюда для m нечетных все доказано.
Кроме того, для m=2, для которого более слабое тривиально

Осталось для чётных более двух доказать.

peregoudov · Сообщение **peregoudov** » 25 сен 2019, 19:43

Так вроде среди $m$

остатков от деления на $m$

один равен нулю? Такая комбинация подходит сама по себе, без вычитаний. А еще не обязательно, чтобы комбинации имели равные остатки. Можно взять остатки, в сумме дающие $m$

, тогда при сложении комбинаций опять получим делимость удвоенной суммы на $m$

...

zykov · Сообщение **zykov** » 25 сен 2019, 21:59

peregoudov писал(а):Source of the post Так вроде среди остатков от деления на один равен нулю?

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

А так просто используется Pigeonhole principle.

peregoudov · Сообщение **peregoudov** » 25 сен 2019, 22:48

А вот еще соображение. Все комбинации можно получить из какой-то одной, последовательно меняя знаки отдельных $a$

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

zykov · Сообщение **zykov** » 26 сен 2019, 05:57

peregoudov писал(а):Source of the postВсе комбинации можно получить из какой-то одной, последовательно меняя знаки отдельных . При каждой такой замене сумма меняется на четную величину.

Можно ещё просто выбросить это $a$

(или добавить, если его не было). Тогда изменится на нечётную величину, если это $a$

нечётное.

zykov · Сообщение **zykov** » 26 сен 2019, 08:27

Ian писал(а):Source of the post Есть комбинаций расстановки знаков в наборе $S=\{\pm a_{1},...\pm a_{n}\}$ , а так как ,найдутся две комбинации знаков с одинаковым остатком суммы. Тогда разность сумм этих наборов делится на , а она имеет вид $2(\pm a_{k_{1}}+...+\pm a_{k_{s}})$ - нашли набор, удвоенная сумма которого делится на .

Можно сделать аналогично, но по-другому.
Тоже $2^n$

векторов, но не "плюс-минус", а "есть или нет" (вместо коэффициентов $\{-1,+1\}$ будут $\{0,1\}$ ).
Тогда найдутся два разных вектора с одинаковыми остатками от суммы по множеству.
Если взять разность этих векторов (тут коэффициенты будут $\{-1,0,+1\}$ ), то получим то что надо. Делится на $m$

независимо от чётности.

Ian · Сообщение **Ian** » 26 сен 2019, 11:26

Действительно , 10 решена, жюри еще не публиковало.
По задаче 9. Расчеты показывают, что линейная система имеет нулевой определитель ровно при

n\ne 1,2,4,...2^k,...(степени двойки), проверено до сотни.Но доказывать удобнее не через определитель, а предъявив какое-то ненулевое решение, или противоречие, когда степень двойки. Наверное теоретически интересные какие-то ненулевые решения.

peregoudov · Сообщение **peregoudov** » 26 сен 2019, 16:42

А почему бы и не через определитель? Вот, например, для нечетных $n$

нетрудно показать, что он имеет два одинаковых последних столбца.

Ian · Сообщение **Ian** » 26 сен 2019, 17:18

peregoudov писал(а):А почему бы и не через определитель? Вот, например, для нечетных нетрудно показать, что он имеет два одинаковых последних столбца.

Тогда (0;0;...0;1;-1) является подходящим набором (при n>1 !) , и это действительно так, в k-е уравнение входят переменные с номерами от k до 2k-1, и значит не может предпоследняя войти, а последняя не войти.

Ian · Сообщение **Ian** » 29 сен 2019, 09:09

Далее можно доказать, что для всех n, имеющих нечетный множитель, больший единицы - ненулевое решение системы есть.
Можно понять как оно устроено, сравнив общее решение для n=3 (0,t,-t) и для n=6 (0,t,-t,0,t,-t) - возьмем общее решение для n, равного нечетному m>1 (0,...0,t,-t) и для n, содержащего нечетный множитель m, повторим его периодически n/m раз.
В каком случае сумма компонент вектора от k-й до (2k-1)-й включительно будет равна 0? Только если суммирование разрывает либо первую встретившуюся на этом участке пару (t,-t), либо последнюю. Если начало суммирования разрывает j-ю пару, k=jm, тогда 2k-1=2jm-1 , это значит, конец суммирования разорвет

2j(\mod\frac nm) пару, то есть в начале k-й суммы будет непарная -t, зато в конце будет непарная t и сумма равна 0.
Обратно, если конец суммирования разорвет пару с номером i (сумма будет иметь t в конце), то последнее слагаемое будет иметь номер im-1=2k-1 (-n), тогда из четности n четно и i, i=2j, тогда начало суммирования разорвет пару j, начнется с -t
Таким образом, если n не является степенью двойки -расстановка есть.
Почему нет расстановки для n - степени двойки?

Ian · Сообщение **Ian** » 04 окт 2019, 10:51

Ian писал(а):В каком случае сумма компонент вектора от k-й до (2k-1)-й включительно будет равна 0? Только если ...

Опечатка(
...будет НЕ равна 0....

Портал Естественных Наук, версия 1.1