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

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 28 апр 2021, 19:45

VSO-21.jpg
VSO-21.jpg (211.92 KiB) 12785 просмотра

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

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 29 апр 2021, 13:00

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$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 29 апр 2021, 14:39

С одной стороны, это количество целых точек в трёхмерной пирамидке $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}$)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 30 апр 2021, 07:18

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

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 01 май 2021, 03:27

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

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

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 01 май 2021, 04:12

Но удобнее не склеивать, а просто половинки рассмотреть.
Для $(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$.)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 01 май 2021, 04:27

Типа того, но они и прямое и обратное отображение записали с помощью функции max и min

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 01 май 2021, 15:14

С 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$ и всё.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 01 май 2021, 16:53

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

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 03 май 2021, 16:24

Седьмая забавная. Описанное в ней линейное преобразование $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). $$
Последний раз редактировалось peregoudov 03 май 2021, 21:45, всего редактировалось 1 раз.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 03 май 2021, 21:31

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

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 03 май 2021, 21:42

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

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 04 май 2021, 07:07

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 (доказано в лекции)

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 04 май 2021, 12:23

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

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


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 3 гостей