Олимпиада Лобачевского -- 2015. Часть 2

[provincialka]

Задачи студенческой олимпиады им. Лобачевского 1 декабря 2015 г.

Задача 6.
Каких граней у $7$-мерного куба $[0;1]^7\subset\mathbb{R}^7$ больше, трехмерных или четырехмерных?

Задача 7.
Пусть $S$ --- некоторый класс функций вида $f:[0,\infty)\to[0,\infty)$, удовлетворяющий следующим условиям:
a) функции $f_1(x)=e^x-1$ и $f_2(x)=\ln(x+1)$ принадлежат классу $S$;
b) если $f(x)$ и $g(x)$ принадлежат классу $S$, то функции $f(x)+g(x)$ и $f(g(x))$ также принадлежат $S$;
c) если $f(x)$ и $g(x)$ принадлежат классу $S$ и $f(x)\geqslant g(x)$ для всех $x\geqslant 0$, то функция $f(x)-g(x)$ также принадлежит $S$.
Доказать, что если функции $f(x)$ и $g(x)$ принадлежат классу $S$, то и функция $f(x)g(x)$ тоже принадлежат классу $S$.

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

Задача 9.
Монету подбрасывают несколько раз до тех пор, пока не выпадут подряд три орла или две решки. Какова вероятность того, что бросания завершатся выпадением трех орлов? Вероятности выпадения орла и решки равны $1/2$, результаты бросков независимы один от другого.

Задача 10.
Последовательность $\{f_n\}$, состоящую из натуральных чисел, можно рассматривать как отображение $f: \mathbb{N}\ni n\mapsto f(n)=f_n\in\mathbb{N}$ ($\mathbb{N}$ --- множество натуральных чисел).
Для трех таких последовательностей $a_n$, $b_n$ и $c_n$ выполняются следующие условия: отображение $a$ --- сюръективно, отображение $b$ --- инъективно, $c_n=a_n-b_n+1$. Доказать, что $c_n=1$ для всех $n$.

[iifat]

(6)

6. Я так прикидываю, размерности $k$ будет $C_7^{7-k}$. Фиксируем ${7-k}$ координат, прочие меняем.

10. Недопол. Берём $a_n=n, b_n=2n$ — и?

[Cash]

iifat в сообщении #1080851 писал(а):

10. Недопол. Берём $a_n=n, b_n=2n$ — и?

а что тогда с $c_n$?

[provincialka]

Ха! Тут надо быть внимательным! $c_n$ -- натуральные числа! Так, небольшой "наворот" .

[NSKuber]

10. Надо доказать, что $a_n=b_n$ для всех $n$, причём из условий натуральности имеем $a_n\geq b_n$. Предположим, что существует номер $n_1$ такой, что $a_{n_1}>b_{n_1}$. Так как $a$ - сюръекция, существует $n_2$: $a_{n_2}=b_{n_1}$. Так как $b$ - инъекция, $a_{n_2}>b_{n_2}$. Процедуру можно повторить сколь угодно много раз, получим строго убывающую положительную натуральную последовательность, противоречие.

[Dmitry Tkachenko]

6. Количество $k$-мерных граней у 7-мерного куба равно $2^{7-k}C_7^k.$ Количество 3-мерных граней $2^4 C_7^3=560,$ а 4-мерных $2^3 C_7^4=280.$ Значит, 3-мерных граней больше, чем 4-мерных.

[ewert]

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

Задача 10.
Последовательность $\{f_n\}$, состоящую из натуральных чисел, можно рассматривать как отображение $f: \mathbb{N}\ni n\mapsto f(n)=f_n\in\mathbb{N}$ ($\mathbb{N}$ --- множество натуральных чисел).
Для трех таких последовательностей $a_n$, $b_n$ и $c_n$ выполняются следующие условия: отображение $a$ --- сюръективно, отображение $b$ --- инъективно, $c_n=a_n-b_n+1$. Доказать, что $c_n=1$ для всех $n$.

Это довольно очевидно, если считать $b_n$ монотонной: поскольку она подпирает $a_n$ снизу, у последней в множестве значений никак не может не оказаться пропусков (если $a_n=b_n$ вплоть до $n=m$ и $a_{m+1}>b_{m+1}$, то среди значений $a_n$ уже заведомо не окажется $b_{m+1}$). Ну а монотонности $b_n$ всегда можно добиться одновременной перестановкой обеих последовательностей.

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

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

Контрпример очевиден -- это единичная матрица. Надо доказать, что если $n$ строк попарно различны, то они попарно различны не менее чем по $(n-1)$ столбцу. Ну так по индукции же. Для $n=2$ утверждение тривиально. Пусть оно верно для некоторого $n$. Для $(n+1)$ попарно различных строк выберем $(n-1)$ столбец, по которым попарно различны первые $n$ строк. Последняя строка по этим столбцам если и совпадает, то разве что с одной из предыдущих строк. Но по хотя бы одному из оставшихся столбцов она от этой строки всё-таки отличается; вот этот столбец и добавим.

[DiMath]

7. Пусть $f,g\in S$, тогда $f_2(f),f_2(g)\in S$

Отсюда $\displaystyle f_1(f_2(f)+f_2(g))=e^{\ln ((1+f)(1+g))} -1=fg+f+g \in S$
Но $fg+f+g\geqslant f+g$ ввиду неотрицательности значений функций из $S$, значит $fg=(fg+f+g)-(f+g)\in S$.

[DeBill]

№9. Типовая задача: марковская цепь с поглощением в состояниях РР и ООО. Считаем вероятность умереть в состоянии ООО; система уравнений , ... и по формуле полной вероятности, ответ 0.3