Страница 1 из 1

Восточно-Сибирская олимпиада

Добавлено: 28 апр 2021, 19:45
Ian
VSO-21.jpg
VSO-21.jpg (211.92 KiB) 236 просмотра

5я казалось бы самая легкая. но именно ее не удалось решить

Восточно-Сибирская олимпиада

Добавлено: 29 апр 2021, 13:00
zykov
Ian писал(а):Source of the post 5я казалось бы самая легкая. но именно ее не удалось решить

Да, что-то непонятно...
Сначала думал, что там опечатка - вместо $3w$ должно быть $4w$.
Тогда $a=x+y+z+w$, $b=y+w$, $c=z+w$, $d=w$.
Но не сошлось. Например при $n=5$ для $(a,b,c,d)=(2,2,1,0)$ получается $(x,y,z,w)=(-1,2,1,0)$.

На компьютере проверил несколько первых $n$ - действительно сходится при $3w$.

Восточно-Сибирская олимпиада

Добавлено: 29 апр 2021, 14:39
zykov
С одной стороны, это количество целых точек в трёхмерной пирамидке $2y+2z+3w \leq n$, $y \geq 0$, $z \geq 0$, $w \geq 0$.

С другой стороны, если обозначить $b=b_1+d$ и $c=c_1+d$, то $a = n - (b_1+c_1+3d)$.
Т.е. это количество целых точек в $2b_1+c_1+4d \leq n$, $b_1+2c_1+4d \leq n$, $b_1 \geq 0$, $c_1 \geq 0$, $d \geq 0$.

(Объёмы сходятся: $V_1 = \frac{1}{3} \frac{1}{2} (\frac{n}{2})^2 \frac{n}{3} = \frac{n^3}{72}$, $V_2 = \frac{1}{3} \frac{n^2}{6} \frac{n}{4} = \frac{n^3}{72}$)

Восточно-Сибирская олимпиада

Добавлено: 30 апр 2021, 07:18
Ian
Не могу отвечать в обычном стиле, так как вчера уже видел решение жюри. Подсказка такая: Построено взаимно-однозначное кусочно-линейное непрерывное отображение одного трехмерного тела в другое, переводящее целые точки в целые. В частности, обратное отображение тоже задается формулой и по ней видно, что целые. А как трехгранную пирамидку отобразить так в четырехгранную...

Восточно-Сибирская олимпиада

Добавлено: 01 май 2021, 03:27
zykov
Ian писал(а):Source of the post А как трехгранную пирамидку отобразить так в четырехгранную...

Четырехгранная симметрична относительно плоскости $b_1=c_1$.
Если одну половину отразить относительно оси $b_1=c_1$, $d=0$, то получится трёхгранная - в основании равнобедренный треугольник с основанием $1/2$ и высотой $1/2$, высота пирамиды - $1/3$.
Отсюда и равенство объёмов.
Что касается целых точек, то там нужно акуратно границы проверить. А отражение относительно такой оси переводит целые в целые.

Восточно-Сибирская олимпиада

Добавлено: 01 май 2021, 04:12
zykov
Но удобнее не склеивать, а просто половинки рассмотреть.
Для $(x,y,z,w)$ рассмотреть точки $y \geq z$ и $y \leq z$. Их одинаковое количество, при этом точки $y=z$ учитываются дважды.
Для $(a,b,c,d)$ рассмотреть точки $b \geq c$ и $b \leq c$. Их тоже одинаковое количество, при этом точки $b=c$ учитываются дважды.

Возьмем $y \geq z$ и $b \geq c$.
Тогда $a=x+y+w$, $b=y+w$, $c=z+w$, $d=z$.
Все неравенства сохраняются. Также $y=z$ эквивалентно $b=c$.

(Обратное преобразование: $x=a-b$, $y=b-c+d$, $z=d$, $w=c-d$.)

Восточно-Сибирская олимпиада

Добавлено: 01 май 2021, 04:27
Ian
Типа того, но они и прямое и обратное отображение записали с помощью функции max и min

Восточно-Сибирская олимпиада

Добавлено: 01 май 2021, 15:14
zykov
С min/max, это видимо склеенное преобразование для всей области сразу.
Мне кажется, это только усложняет. Проще и короче обратить внимание на симметрию и доказать равенство для половинки и для границы. Тогда равенство для всей области автоматом получается.

В принципе оно даже довольно интуитивно получается.
Сначала к трём измерениям переходим и получаем две пирамидки, как я писал выше. Потом каждую делим пополам плоскостями $y=z$ и $b_1=c_1$.
На границе будут треугольники, которые можно спроецировать не нарушая целостность, положив $z=0$ и $c_1=0$. Получатся два прямоугольных треугольника с катетами $1/3$ и $1/4$ для первого, и с катетами $1/4$ и $1/3$ для второго. Значит количество целых точек в этих границах одинаковое.
Сами половинки ($y \geq z$ и $b_1 \geq c_1$) будут тетраэдрами.
Первый имеет размер $1/3$ вдоль оси $w$ (имеет ребро вдоль оси), $1/2$ вдоль оси $y$ (имеет ребро вдоль оси), $1/4$ вдоль оси $z$ (не имеет ребра вдоль оси).
Второй имеет размер $1/4$ вдоль оси $d$ (имеет ребро вдоль оси), $1/2$ вдоль оси $b_1$ (имеет ребро вдоль оси), $1/3$ вдоль оси $c_1$ (не имеет ребра вдоль оси).
Проблемы возникают из-за наклонных рёбер, но к счастью наклон там 45 градусов, так что можно простым аффинным преобразованием (сохраняющим целостность в обе стороны) убрать этот наклон.
Например если заменить $y$ на $y_2=y-z$, и $b_1$ на $b_2=b_1-c_1$, то в этих осях уже по 3 ребра каждого тетраэдра будут вдоль осей.
Осталось приравнять $d=z$, $c_1=w$, $b_2=y_2$ и всё.

Восточно-Сибирская олимпиада

Добавлено: 01 май 2021, 16:53
Ian
zykov писал(а):.
Мне кажется, это только усложняет.
Да я-то не против, я считаю что у Вас хорошо доказано.
Но вот например, с задачей 3 проверял преподаватель, который явно никогда не читал функан а читал только матан. Мы пишем: будем считать эти интегралы - интегралами Лебега, и найдем условный максимум в классе ступенчатых функций (тех, которые принимают лишь конечное число значений, но на множествах сколь угодно сложно устроенных). А любую ограниченную интегрируемую по Лебегу функцию можно приблизить ступенчатыми в смысле интегральной нормы, причем ее куб будет приближен кубом этой ступенчатой. Значит, обнаружив достижимый условный максимум в классе всех ступенчатых, мы получим этот же условный максимум в классе всех интегрируемых...
Дает 1 балл из 7. пишет -не обосновано. Конечно это я пригладил тут.
Наоборот, хотя есть простое доказательство средствами матана, любой преподаватель функана нас за это обнял бы и расцеловал, свели олимпиадную задачу к рядовой -для функций, принимающих только два значения.То есть задаваемых тремя действительными параметрами. Но в общем лучше равняться на традиции того места, где проверяют (Якутск)
И кстати все задачи понравились, с хорошим вкусом подобраны

Восточно-Сибирская олимпиада

Добавлено: 03 май 2021, 16:24
peregoudov
Седьмая забавная. Описанное в ней линейное преобразование $X_{k+1}=LX_k$ --- произведение усреднения

$$ A=\begin{pmatrix} \frac1n&\frac1n&\cdots&\frac1n\\ &1\\ &&\ddots\\ &&&1 \end{pmatrix} $$

и циркулянта

$$ C=\begin{pmatrix} 0&1\\ &0&\ddots\\ &&\ddots&1\\ 1&0&\cdots&0 \end{pmatrix}, $$

в явном виде

$$ L=CA=\begin{pmatrix} 0&1\\ &0&\ddots\\ &&\ddots&1\\ \frac1n&\frac1n&\cdots&\frac1n \end{pmatrix}. $$

Несложно найти характеристический многочлен (лучше расписывать построчно уравнение $LX=\lambda X$)

$$ \chi(\lambda)=\lambda^n-\frac1n(1+\ldots+\lambda^{n-1}). $$

Нетрудно увидеть корень $\lambda_1=1$ с собственными правым и левым векторами $X_1^T=(1,1,\ldots,1)$ и $Y_1^T=(1,2,\ldots,n)$ и показать, что все остальные корни по модулю меньше единицы. Поэтому асимптотическое поведение определяется проектором

$$ \Pi_1=\frac{X_1Y_1^T}{Y_1^TX_1}=\frac2{n(n+1)}X_1Y_1^T. $$

Все иксы стремятся к одному и тому же значению

$$ (\Pi_1X_0)_i=\frac2{n(n+1)}(x_1+2x_2+\ldots+nx_n). $$

Восточно-Сибирская олимпиада

Добавлено: 03 май 2021, 21:31
Ian
Это типичное поведение эргодической матрицы, у которой суммы по строкам равны 1. Для такой матрицы L : [math] - матрице предельного распределения, у которой все строки равны. Характерно, что [math] и например [math] оценка схорости сходимости.

Восточно-Сибирская олимпиада

Добавлено: 03 май 2021, 21:42
peregoudov
Ваша $L_*$ --- это моя $\Pi_1$. А вот с остальным не согласен, с $L=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ не будет никуда сходится, хотя эргодичность ваша выполняется. Вообще было бы небезынтересно взглянуть, как из вашей эргодичности получается ограничение на собственные значения.

Восточно-Сибирская олимпиада

Добавлено: 04 май 2021, 07:07
Ian
peregoudov писал(а):Ваша $L_*$ --- это моя $\Pi_1$. А вот с остальным не согласен, с $L=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ не будет никуда сходится, хотя эргодичность ваша выполняется. Вообще было бы небезынтересно взглянуть, как из вашей эргодичности получается ограничение на собственные значения.
Вы правильно подкололи, "моя" эргодичность (только суммы по каждой линии 1цы и неотрицательность) -этого мало для сходимости, эргодичность это еще достижимость каждого состояния из каждого за любое число n>N шагов ( у вашей матрицы состояние 1 достижимо из 2го только при n нечетном). Прикрепляю интересную (для меня) лекцию на файлообменник, вес не позволяет сюда . https://dropmefiles.com/7zSUh , как раз недавно изучал и там все эти тождества есть и доказаны. Там как раз исследуются марковские процессы , которые могут протекать в нескольких вариантах со своими матрицами и столбцами цен, а управление- это переключение на каждом шагу между этими вариантами. В итоге получится следование марковской матрице, составленной из лучших строк данных матриц. Средний расход стремится к константе. Но тогда некорректна задача оптимизации в текущий момент, даже если поступим неоптимально один раз, средний расход не изменится. Придуман вектор bias -смещение, та конечная сумма, которая будет заработана или потеряна до выхода на этот средний расход, и его оптимизируем. Это спецкурс для аспирантов былВ итоге, та эргодичность, которая "моя" и в этой лекции, означает сходимость средних арифметических [math] что и достаточно для утверждения, что собственные значения не превосходят 1 (доказано в лекции)

Восточно-Сибирская олимпиада

Добавлено: 04 май 2021, 12:23
peregoudov
По поводу эргодичности я, конечно, глянул в Википедии, там есть и про достижимость и прочее, но кратно и без доказательств. Так что за лекцию спасибо! Я-то просто конкретное характеристическое уравнение исследовал и в частном случае доказывал.

Хотя... Чем проверять выполнение всех этих общих требований, в частном случае проще напрямую...