Аналитические и вероятностные методы

сумм из задачи 1.1.6 (1);

сумм из задачи 1.1.6 (2);

сумм из задачи 1.1.6 (3);

количества $A_n$ подмножеств множества $\left\{ 1, 2, \ldots , n\right\}$, не содержащих двух подряд идущих чисел;

то же, что в п. (4), для трёх подряд идущих чисел.

$\ex_{P_k}(n) \gtrsim \dfrac {k-2}{2} \cdot n$.

$\ex_{C_{2k+1}}(n) \gtrsim \dfrac {n^2}{4}$.

$\ex_{K_{1,k}}(n) \sim \dfrac {k-1}{2} \cdot n$.

$n^2\left(2+\dfrac {1}{n}\right)^n = (2+o(1))^n$. По определению это означает, что существует функция $\psi (n) = o(1)$, для которой

или, что то же самое,

$3^{\sqrt{n}}\left(2+\dfrac {1}{n}\right)^n = (2+o(1))^n$.

Найдите асимптотику для $\sqrt[n]{\dbinom {n}{[n/2]}}$ (ср. с задачами 1.4.3 (2) и 6.1.10 (2)).

$\dfrac {2^n}{n+1} < \dbinom {n}{[n/2]} < 2^n$.

Найдите асимптотику для $\sqrt[m]{\dbinom {3m}{m}}$.

$\dfrac {3^{3m}}{3m+1} < 2^{2m}\dbinom {3m}{m} < 3^{3m}$.

$\dbinom {n}{[an]} = (a^{-a}(1-a)^{a-1}+o(1))^n$, где $0 < a < 1$.

$\dfrac {n!}{[a_1n]!\ldots [a_sn]!} = (e^{-a_1\ln a_1 - \ldots - a_s\ln a_s}+o(1))^n$, где $a_1+\ldots +a_s=1$, $0 < a_k < 1$.

Найдите асимптотику для $\ln (n!)$.

Найдите асимптотику для $\sqrt[n]{n!}$.

$n^ne^{-n+1} \leqslant n! \leqslant n^{n+1}e^{-n+1}$;

$n! \leqslant n^ne^{-n+1}\sqrt{n}$.

Формула Стирлинга. $n! \sim n^ne^{-n}\sqrt{2\pi n}$, т.е. $\lim_{n \to \infty } \dfrac {n!}{n^ne^{-n}\sqrt{2\pi n}} = 1$.

$\dbinom {n}{k} < \dfrac {n^k}{k!}$.

$\ln \dfrac {(n-1)(n-2)\ldots (n-k)}{n^k} = -\dfrac {k(k+1)}{2n}\left(1+O\left(\dfrac {k}{n}\right)\right)$ для $k=k_n < \dfrac {n}{2}$.

Это означает, что существует функция $\psi (n) = O\left(\dfrac {k}{n}\right)$, для которой

или, что то же самое,

$\dbinom {n}{k} = \dfrac {n^k}{k!}e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$ для $k=k_n < \dfrac {n}{2}$.

(Сформулируйте сами, что здесь означает $e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$.)

$\dbinom {n}{k} \sim \dfrac {n^k}{k!}$ для $k=k_n=o(\sqrt{n})$.

$\dbinom {2n}{n-k}\Big/\dbinom {2n}{n} = e^{-\frac{k^2}{n}(1+o(1))}$ для $k=k_n=o(n)$.

(Сформулируйте сами, что здесь означает $e^{-\frac{k^2}{n}(1+o(1))}$.)

Верно ли, что записи $e^{o(n)}$ и $o(e^n)$ <<равнозначны>>?

То есть верно ли, что для любой функции $f : \mathbb {Z} \to (0,+\infty )$ условия $\lim_{n\to \infty }\dfrac {\ln f(n)}{n}=0$ и $\lim_{n\to \infty }f(n)e^{-n}=0$ равносильны?

Подберите функции $f,g : \mathbb {Z} \to (0,+\infty )$ такие, что $f(n)\sim g(n)$, но $e^{f(n)} \neq O(e^{g(n)})$.

Могут ли функции $f,g : \mathbb {Z} \to (0,+\infty )$ одновременно удовлетворять соотношениям $f(n)=o(g(n))$ и $g(n)=o(f(n))$?

Могут ли функции $f,g : \mathbb {Z} \to (0,+\infty )$ одновременно удовлетворять соотношениям $f(n)=O(g(n))$ и $g(n)=O(f(n))$?

Следует ли из двух соотношений из п. (4), что $f(n)\sim g(n)$?

Какая функция растёт быстрее: $x^{(x^x)}$ или $(x!)^{(2^x)}$?

То есть найдите $\lim_{x\to \infty } x^{(x^x)}(x!)^{(-2^x)}$.

Существует ли функция $\psi (n) = o(1)$, для которой $(2+\psi (n))^n \times 2^{-n}e^{-\sqrt{n}} \to \infty$?

(Как в любой математической задаче, нужно обосновать ответ: привести пример такой функции или доказать её существование или доказать, что такой функции не существует.)

$\ln \dbinom {n^2}{n}$;

$\dbinom {n}{[n/2]}$;

$\dbinom {n^2}{n}$;

$\dbinom {n}{[n^\alpha ]}$, $\alpha \in (0,1)$;

$(2n-1)!! := (2n-1)\cdot (2n-3)\cdot \ldots \cdot 3\cdot 1$;

$\displaystyle \sum_{k=0}^{n}\dbinom {n}{k}^2$;

$\displaystyle \sum_{k=0}^{n}\dbinom {n}{k}^4$.

$s^s = n$;

$s^{s^3} = n$;

$s(n) := \max \left\{ k : k! \leqslant n\right\}$;

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {n}{m} < 2^{\binom {m}{2}}\right\}$ (ср. с задачей 4.1.5);

$s(n) := \min \left\{ m \in \mathbb {N} : \dfrac {2^m}{m} > n\right\}$ (функция $2^m/m$ возникает как сложность реализации функций алгебры логики);

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {m}{[m/2]} > n\right\}$ (ср. с задачей 1.4.3 (2)).

количества линейных подпространств в $\mathbb {Z}_2^n$ (см. задачу 1.4.7 и определение перед ней);

количества уницикличных графов с $n$ вершинами (см. задачу 2.2.5 (2) и определение перед ней).

По каждому из 100 видов работ в фирме имеется ровно 8 специалистов. Сотрудник может быть специалистом по нескольким видам работ; распределение специалистов по видам работ известно тому, кто назначает выходные. Каждому сотруднику нужно дать выходной в субботу или в воскресенье. Докажите, что это можно сделать так, чтобы и в субботу, и в воскресенье для каждого вида работ на работе был специалист по нему. (Это задача 1.6.7.)

По каждому из нескольких видов работ в фирме имеется ровно 8 специалистов. (Теперь видов работ не обязательно 100.) Каждый вид работ имеет общих специалистов не более чем с 30 другими видами. Каждому сотруднику нужно дать выходной в субботу или в воскресенье. Докажите, что это можно сделать так, чтобы и в субботу, и в воскресенье для каждого вида работ на работе был специалист по нему.

По кругу стоит 200 студентов из 10 групп, в каждой из которых 20 студентов. Докажите, что можно в каждой группе выбрать по старосте так, чтобы никакие два старосты не стояли рядом.

То же для 1600 студентов из 100 групп, в каждой из которых 16 студентов.

Докажите, что можно раскрасить первые 8 натуральных чисел в 2 цвета так, чтобы не было одноцветной арифметической прогрессии длины 3.

Докажите, что можно раскрасить первые 15 миллионов натуральных чисел в 2 цвета так, чтобы не было одноцветной арифметической прогрессии длины 32.

Докажите, что для любого $M \in \mathbb {R}$ можно так раскрасить все вещественные числа в 2 цвета, чтобы для любого $x \in \mathbb {R}$ числа $x$ и $x+M$ были разных цветов.

Докажите, что для любых различных 25 чисел $M_1,\ldots ,M_{25} \in \mathbb {R}$ можно раскрасить все вещественные числа в 3 цвета так, чтобы для любого $x \in \mathbb {R}$ среди чисел $x+M_1,\ldots ,x+M_{25}$ были числа каждого из трёх цветов.

В множестве всех клеток шахматной доски подмножество клеток в первых трёх её строках с подмножеством клеток в последних четырёх её столбцах.

Подмножества $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4\right\}$ и $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4\right\}$.

Подмножества $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4,5,6\right\}$ и $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4,5,6\right\}$.

Подмножество чисел, делящихся на 5, и подмножество чисел, делящихся на 7.

Подмножество чисел, делящихся на 15, и подмножество чисел, делящихся на 21.

Подмножество чисел, делящихся на 15, и подмножество чисел, делящихся на 5.

Подмножество чисел, делящихся на 10, и подмножество чисел, делящихся на 7.

Подмножество раскрасок, для которых $\left\{ 1,2,\ldots ,8\right\}$ одноцветно, и подмножество раскрасок, для которых $\left\{ 11,12,\ldots ,18\right\}$ одноцветно.

Подмножество раскрасок, для которых $\left\{ 1,2,\ldots ,8\right\}$ неодноцветно, и подмножество раскрасок, для которых $\left\{ 11,12,\ldots ,18\right\}$ неодноцветно (ср. с задачей 6.2.1 (2)).

Подмножество раскрасок, для которых $\left\{ 1,2,\ldots ,8\right\}$ одноцветно, и подмножество раскрасок, для которых $\left\{ 6,7,\ldots ,13\right\}$ одноцветно.

Обязательно ли найдётся богатый здоровый умный горожанин, если в городе доля богатых горожан больше $\dfrac {2}{3}$, доля здоровых больше $\dfrac {2}{3}$ и доля умных больше $\dfrac {2}{3}$?

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

Тот же вопрос, если в городе богатых горожан больше половины, здоровых больше половины, умных больше половины, богатство и ум независимы, здоровье и ум независимы.

Пусть $A_1,A_2,A_3,A_4$ — подмножества 720-элементного множества, в каждом из которых более 480 элементов. Если $A_k$ и $A_{k+1}$ независимы для любого $k=1,2,3$, то $A_1\cap A_2\cap A_3\cap A_4 \neq \emptyset$.

Пусть $n \geqslant 2$ и $A_1,A_2,\ldots ,A_n$ — подмножества конечного множества, доля каждого из которых больше $1-\dfrac {1}{n-1}$. Если $A_k$ и $A_{k+1}$ независимы для любого $k=1,2,\ldots ,n-1$, то $A_1\cap A_2\cap \ldots \cap A_n \neq \emptyset$.

попарно независимых, но для которых $A$ не является независимым от набора $B_1, B_2$;

не являющихся попарно независимыми, но для которых $A$ независимо от набора $B_1, B_2$.

Локальная лемма Ловаса в симметричной форме. Пусть $A_1,\ldots ,A_n$ — подмножества конечного множества. Если для некоторого $d$ и любого $k$ доля подмножества $A_k$ не меньше $1-\dfrac {1}{4d}$ и существует набор из не менее чем $n-d$ подмножеств $A_j$, от которого $A_k$ не зависит, то $A_1\cap \ldots \cap A_n \neq \emptyset$.

При $d > 2$ утверждение п. (1) верно, если заменить $1-\dfrac {1}{4d}$ на $1-\dfrac {1}{e(d+1)}$.

Если $a_k=1$ при любом $k\leqslant 0$ и для некоторого $d\geqslant 2$ выполнено $a_{k+1}\geqslant a_k-\dfrac {a_{k-d}}{4d}$ при любом $k\geqslant 0$, то $a_k > 0$ при любом $k$.

$k \geqslant 10$;

$k=9$

Для любого разбиения множества вершин цикла длины $16n$ на $n$ множеств по 16 вершин можно выбрать по вершине из каждого множества так, что между выбранными $n$ вершинами нет рёбер.

То же для $11n$ вершин.

В графе степень каждой вершины не превосходит $\Delta$. Все вершины раскрашены в $r$ цветов. Вершин каждого цвета не менее $2e\Delta +1$. Тогда можно выбрать $r$ вершин разных цветов, никакие две из которых не соединены ребром.

Каждую $k$-элементную арифметическую прогрессию в $\left\{ 1,2,\ldots ,n\right\}$ пересекает не более $k^2\left[\dfrac {n}{k-1}\right]$ других таких прогрессий.

Для любого натурального $k$ существует раскраска первых $\left[\dfrac {2^{k-3}(k-1)}{k^2}\right]$ натуральных чисел в 2 цвета, для которой нет одноцветной $k$-элементной арифметической прогрессии.

Каждую $k$-элементную арифметическую прогрессию в $\left\{ 1,2,\ldots ,n\right\}$ пересекает не более $nk$ других таких прогрессий.

Для любого натурального $k$ существует раскраска первых $\left[\dfrac {2^{k-3}}{k}\right]$ натуральных чисел в 2 цвета, для которой нет одноцветной $k$-элементной арифметической прогрессии.

Если $X\subset \mathbb {R}$ — конечное множество и $m,r$ — натуральные числа, для которых $4rm(m-1)\left(1-\dfrac {1}{r}\right)^m < 1$, то для любого $m$-элементного подмножества $M\subset \mathbb {R}$ существует раскраска множества $\mathbb {R}$ в $r$ цветов такая, что для любого $x\in X$ множество $x+M := \left\{ x+a : a\in M\right\}$ содержит точки каждого из $r$ цветов.

То же для $X=\mathbb {Z}$.

То же для $X=\mathbb {R}$.

Если $\dbinom {n}{2}\dbinom {k}{n-2}+1 < 2^{\binom {n}{2}-1}/e$, то $R(n,n) > k$, где $R(n,n)$ — число Рамсея (п. 4.1).

$R(n,n) \gtrsim \sqrt{2}e^{-1}n2^{n/2}$. (Ср. с задачей 4.1.5.)

Локальная лемма Ловаса. *Пусть $A_1,\ldots ,A_n$ — подмножества конечного множества, $J_1,\ldots ,J_n\subset \left\{ 1,\ldots ,n\right\}$ и $\gamma_1,\ldots ,\gamma_n\in (0,1)$. Пусть также для любого $k$

• доля подмножества $A_k$ не меньше $1-(1-\gamma_k)\displaystyle \prod_{j\notin J_k}\gamma_j$;

• множество $A_k$ не зависит от набора $\left\{ A_j : j\in J_k\right\}$.

Тогда доля пересечения $\displaystyle \bigcap_{k=1}^{n}A_k$ не меньше $\displaystyle \prod_{k=1}^{n}\gamma_k > 0$.*

Существует такое $c>0$, что $R(3,n) > cn\sqrt{n}$ для любого $n$.

для любого $p\in (0,1)$ существует такое множество вершин $A\subset V$, что в объединении $A$ и множества всех вершин, не соединённых ни с какой вершиной из $A$, имеется не более $np+n(1-p)^{\delta +1}$ вершин;

существует такое множество вершин $D\subset V$, что любая вершина из $V\setminus D$ соединена ребром с некоторой вершиной из $D$ и $\left|D\right|\leqslant n\dfrac {1+\ln (\delta +1)}{\delta +1}$.

Если $\dbinom {k}{m}p^{\binom {m}{2}}+\dbinom {k}{n}(1-p)^{\binom {n}{2}} < 1$ для некоторого $p\in (0,1)$, то $R(m,n) > k$ (здесь $R(m,n)$ — числа Рамсея, см. п. 4.1).

$R(4,n) \geqslant \Omega \left(\dfrac {n^2}{\ln^2 n}\right)$ (мы пишем $g \geqslant \Omega (f)$, если $f=O(g)$).

Cherchez la femme. На русско-французской встрече не было представителей других стран. Суммарное количество денег у французов оказалось больше суммарного количества денег у русских, и суммарное количество денег у женщин оказалось больше суммарного количества денег у мужчин. Обязательно ли на встрече была француженка?

Денежные купюры разного достоинства и разных стран упакованы в два чемодана. Средняя стоимость купюры равна 100 рублям. Общее число купюр в левом чемодане больше, чем в правом. Обязательно ли в левом чемодане найдётся купюра стоимостью не более 200 рублей? (Ср. с неравенством Маркова 6.3.9 (1).)

Для любых целых $l,q>0$ существует граф, не содержащий обходов длины менее $l$ и который невозможно правильно раскрасить в $q$ цветов. (См. определение правильности раскраски в п. 3.1.)

изолированных вершин;

треугольников;

$k$-клик;

$k$-клик, являющихся компонентами связности;

гамильтоновых циклов;

несамопересекающихся циклов длины $k$;

несамопересекающихся циклов длины $k$, являющихся компонентами связности с ровно $k$ рёбрами;

деревьев с $k$ вершинами;

древесных компонент данного размера $k$, т.е. деревьев с $k$ вершинами, являющихся компонентами связности.

изолированных вершин;

треугольников.

$\mathbb {E}\left[X+Y\right] = \mathbb {E}\left[X\right]+\mathbb {E}\left[Y\right]$;

$\operatorname {Var}\left[X+Y\right] = \operatorname {Var}\left[X\right]+\operatorname {Var}\left[Y\right]$, если $X$ и $Y$ независимы (т.е. для любых $x,y$ выполнено $\mathbb {P}\left(X=x,Y=y\right)=\mathbb {P}\left(X=x\right)\cdot \mathbb {P}\left(Y=y\right)$).

Неравенство Маркова. $\mathbb {P}\left(\left|X\right|>a\right) \leqslant \mathbb {E}\left[\left|X\right|\right]/a$. (Ср. с задачей 6.3.3 (1).)

Неравенство Чебышёва. $\mathbb {P}\left(\left|X-\mathbb {E}\left[X\right]\right|>a\right) \leqslant \operatorname {Var}\left[X\right]/a^2$.

а.п.н.имеется более $n/2$ изолированных вершин;

для некоторого $C>0$ а.п.н.каждая компонента связности имеет менее $C\ln n$ вершин (специалисты говорят: менее $O(\ln n)$ вершин);

а.п.н.каждая компонента связности является деревом или уницикличным графом;

для некоторого $C>0$ а.п.н.имеется менее $C$ уницикличных компонент.

При $p(n)=o(n^{-3/2})$ а.п.н.рёбра попарно не пересекаются.

При $p=p(n)=o(n^{-3/2})$ и $pn^2\to \infty$ существует такая функция $r=r(n)=o(pn^2)$, что а.п.н.число вершин степени 1 больше $pn^2-r$ и меньше $pn^2+r$, а степени всех остальных вершин равны нулю.