Казань, Олимпиада им. Н.И.Лобачевского 2019 г.

[DeBill]

RIP в сообщении #1429619 писал(а):

Классика.

ВАХ!

-- 11.12.2019, 14:12 --

provincialka в сообщении #1429525 писал(а):

их температура мгновенно выравнивается до $T=(T_1m_1+T_2m_2)/(m_1+m_2)$.

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

[Munin]

(Оффтоп)

DeBill в сообщении #1429657 писал(а):

как известно, температура тела равна концентрации флогистона в нем

Всё-таки именно теплорода, а не флогистона.
Флогистон - это другое вещество. Это "минус-кислород" в реакциях окисления-восстановления: восстановление есть соединение с флогистоном, а окисление - разложение с выделением флогистона.

[worm2]

6. Я тоже получил, что $90^\circ(1-1/e)<60^\circ$. Но попробовал доказать оценку строго, с учётом всевозможных вариантов (например, когда уже поучаствовавшие в соприкосновении части второго тела соприкасаются друг с другом или с ещё не участвовавшими частями второго тела), и ниасилил.
С горя решил, а пусть авторы задачи тоже пострадают от недостатка строгости, как страдал я
Ответ: можно. Разбиваем второе тело на части, из которых составляем два таких же (по схеме из парадокса Банаха—Тарского), соединяем их друг с другом, а потом с первым, вуаля: $(90^\circ\cdot 2+0^\circ)/(2+1)=60^\circ$.

[DeBill]

Munin в сообщении #1429673 писал(а):

Всё-таки именно теплорода, а не флогистона.

Во как! Спасибо!

(Оффтоп)

Темнота я все таки: надо же, перепутать флогистон с теплородом! Средневековые химики убили бы меня!

[provincialka]

Смотрю, 8 задачу пока не решили (я как раз ее проверяла)

Участники олимпиады тоже не дали строгого доказательства, хотя некоторые и привели правильный пример с сумой 42.

(нытьё)

Эх! я даже не успела прорешать все задачи... занятость проклятая. Поэтому не могу оценить, трудные они или нет

[DeBill]

provincialka
Ну, можно так:
Выпишем все возможные "состояния системы" (целые числа, что появляются в последовательности). Расположим их в два столбика: в левом - все отрицательные, расположенные в порядке убывания, в правом - все неотр-е, расположенные в порядке возрастания. Расставим стрелочки (возможные переходы из состояния в состояние).
Видим: в правом столбике все стрелки - вниз, к соседу; в левом - аналогично, но вверх; по горизонтали - в обе стороны. Видим (начальное состояние - нулевое):
1. Все циклы - четной длины.
2. Все простые циклы имеют вид: столбик слева длины $k$, такой же - справа рядом, и две горизонтальные палки - снизу и сверху. Сумма чисел в таком цикле равна $-k$.
3. Но тогда и в любом цикле длины $2k$ сумма чисел равна $-k$.
4. Удалим все циклы, и рассмотрим оставшийся участок пути. Его длина - нечетна, и он имеет вид:
либо горизонтальный отрезок налево длины 1 (неинтересный)
либо вертикальный отрезок вниз нечетной длины $x$
либо - много вниз, потом налево, потом немного вверх
5. Про третий вариант можно думать как про второй: отрежем от него конечный участок "немного вниз, налево, немного вверх", так что маршрут опять можно считать состоящим из цикла, и отрезка (нечетной длины) вниз.
Ну, а теперь будем считать: (для второго варианта):
Сумма чисев в вертикальном отрезке состоящем из первых $x$ нат. чисел, равна $\frac{x(x+1)}{2}$, суммарная длина всех оставшихся циклов равна $2019 - x$, и по 2,3, сумма чисел в них равна $-\frac{2019-x}{2}$.
Итого, сумма вааще всех чисел равна $\frac{x(x+1)}{2} - \frac{2019-x}{2} =\frac{x^2-2x - 2019}{2} = \frac{(x+1)^2 -2010}{2}$, где $x$ - нечетно.
Подбирая ближайший к 2020 точный четный квадрат, найдем $x=43$, что и дает (по модулю) ответ 42.
Пример оптимального маршрута: много раз влево-вправо, затем - 43 раза вниз (т,е., $0,-1,0,-1,0,-1,0,.......,1,2,3,4,....,43$).

-- 11.12.2019, 20:20 --

10. Нет, все же можно обойтись без счета всего распределения....
Пусть $\xi_i$ - случайная величина, равная 1, если $i$-й чел не выбран, и 0 - если выбран (и тогда нас интересует $\xi$, равная сумме всех ксюшек).
Она принимает значение "1" с вероятностью $\frac{1}{4}$ (так что ее матожидание, как и матожидание ее квадрата, равно $\frac{1}{4}$ ).
Поэтому матожидание суммы равно $\frac{n}{4}$.
Найдем матожидание $\xi_i\xi_j$ (оно также равно вероятности того, что это произведение равно 1):
Если они - соседи: $\frac{1}{16}$
Если расположены "через одного" -- равна 0 (чел между ними кого то из них запятнает)
Иное: $\frac{1}{16}$
Тогда: матожидание от $\xi^2$ равно $\sum\limits_{i}^{} M\xi_i^2+ 2 \sum\limits_{i<j}^{} M\xi_i\xi_j = \frac{n}{4} +\frac{n(n-3)}{16}$ (при раскрытии скобок, каждая из ксюшек первой скобки при умножении на все (кроме трех: себя, и двух соседей через один), дает вклад, равный одной шестнадцатой).
Итого, дисперсия равна $\frac{n}{4}+\frac{n(n-3)}{16} -(\frac{n}{4})^2 =\frac{n}{16}$

[provincialka]

в 8 задаче есть более изящное решение... Надо избавиться от модулей!

[svv]

provincialka в сообщении #1429525 писал(а):

8. Последовательность целых чисел такова, что $x_0=0$, $|x_n|=|x_{n-1}+1|$ для всех натуральных $n$. Каково наименьшее возможное значение выражения $|x_1+x_2+\ldots+x_{2019}|$?

Пусть $s_0=0,\; s_n=s_{n-1}+x_n$, то есть $s_n=\sum\limits_{k=1}^n x_k$.
Докажем, что $x_n^2+2(x_n-s_n)=n$. В самом деле, выражение слева равно $0$ при $n=0$ и увеличивается на $1$ с каждым шагом:
$x_n^2+2(x_n-s_n)=(x_{n-1}+1)^2-2s_{n-1}=x_{n-1}^2+2(x_{n-1}-s_{n-1})+1$

Подставив $n=2020$, найдём $2s_{2019}=x_{2020}^2-2020$.
Видно, что $x_{2020}$ чётно. Правая часть минимальна по модулю при $x_{2020}=\pm 44$, при этом $s_{2019}=-42$.

Остаётся обосновать достижимость $x_{2020}=44$. Это просто: выбирая на очередном шаге в формуле $x_n=\pm(x_{n-1}+1)$ «плюс», мы увеличиваем текущий $x$ на 1, а выбирая «минус» два шага подряд, мы вернёмся к тому же значению $x$.

[provincialka]

svv
Ага! Авторское решение близко к этому. Можно ещё так описать: возведем рекуррентное соотношение в квадрат получим
$x_1^2=x_0^2+2x_0+1$
$x_2^2=x_1^2+2x_1+1$
...
$x_{n+1}^2=x_n^2+2x_n+1$
Складывая равенства и упрощая, получим соотношение $x_{n+1}^2=x_0^2+2\sum_{\limits}{_{i=0}^n}x_i+n+1$

[svv]

Грэйт!
Скажите, пожалуйста, а решение 6) близко к авторскому?

[DeBill]

provincialka
Красиво! Я тоже получил эту формулу для суммы (пытаясь заснуть), но - угадав ответ (по подсказке "есть короткое решение") и доказав ее по индукции.
Вообще, надо сказать, замечательная подборка задач. А как всех (после, да, становления в ступор) повеселил Николай!

-- 12.12.2019, 19:47 --

svv
Дык, типа, решение еще никто и не выложил - только ответ.
А с учетом комментария worm2, боюсь, все решения (ну, по крайней мере, то, что я сам сочинял) нуждаются в чистке....
А "неочищенное" - можно оформить так:
Если к "единичному" телу температуры $T=1-d$ приложить кусочек массы $\alpha$ температуры 1, то единичное нагреется до $T'=1-d', d' = \frac{d}{1+\alpha}$.
Значит, если к телу (нулевой температуры изначально) последовательно прикладывать кусочки массы $\alpha_1,...,\alpha_n, \alpha_1+...+\alpha_n=1$, то тело нагреется до температуру $t=1-q , q= (\prod\limits_{k=1}^{n}(1+\alpha_k))^{-1}$.
Из впуклости логарифма следует $\sum\limits_{k=1}^{n} \ln (1+\alpha_k) \leqslant \sum\limits_{k=1}^{n} \alpha_k =1$, откуда и следуют предъявляемые оценки.
Но почему не такие алгоритмы - хуже? Здравый смысл грит, что - да, но как это обосновать аккуратно?

[provincialka]

DeBill
Спасибо на добром слове! Коллектив поработал на славу, нас было около 10 человек (я в этом году только с "совещательным голосом") Но вот сложность задач оказалась завышенная..
svv
Нет, такого решения не было, по крайней мере, в решебнике. Туда включили два решения из трёх, данных автором.
Первое: явный подбор искомых матриц для верхнетреугольной матрицы и формула, позволяющая распространить этот пример на произвольный случай.
Второе: подобным преобразованием сводим матрицу к матрице с нулевой диагональю и приводим разложение для нее.

А вообще информацию о задачах и решениях за 2019 год можно получить здесь

Информация за прошлые годы и информация Оргкомитета на сайте олимпиады

-- 12.12.2019, 18:18 --

DeBill в сообщении #1429870 писал(а):

да, но как это обосновать аккуратно?

Видимо, сложно... Про то же говорит и А.Савватеев в своем разборе