Вероятностный метод: средние
Если среднее (математическое ожидание) больше $\alpha$, то некоторые значения больше $\alpha$
- Если сумма десяти чисел больше $100$, то сумма некоторых трёх из них больше $30$
Вариант: если у дерева $1500$ листьев, можно оборвать $800$ из них так, чтобы осталось не меньше $7/15$ тени. (С какой-то из московских олимпиад, кажется.)
- Та же задача, если числа стоят по кругу и нужна сумма трёх соседних
- Любой граф с $E$ рёбрами можно разрезать на две части так, чтобы в разрез попало не меньше $E/2$ рёбер
- В клетках шахматной доски написаны числа, сумма положительна. Докажите, что можно расставить ладьи, не бьющие друг друга, чтобы сумма была положительной
- Для любой 3-кнф можно удовлетворить не менее $7/8$ дизъюнктов
- Поверхность тела меньше $4$; докажите, что можно его повернуть так, чтобы тень была не больше $1$ (на экране, перпендикулярном направлению света)
- Фигуру площади $n$ можно поместить на клетчатой бумаге так, чтобы она покрыла не менее $n$ узлов, а можно так, чтоб не больше $n$ узлов
Вероятностный метод: оценка суммы
Если сумма вероятностей событий меньше $1$, то иногда ни одного из них не происходит.
- В окружность, где не более $30\%$ грязные, можно вписать правильный треугольник с чистыми вершинами. (Рассуждение со средними и с вероятностью.)
- В сферу, где не больше $10\%$ поверхности грязные, можно вписать куб с чистыми вершинами
- Числа Рамсея
- $R(k,l)$: сколько вершин нужно в графе, чтобы гарантировать или независимое множество из $k$, или клику из $l$;
- оценка $R(3,3)=6$;
- верхняя оценка $R(k,l)\le R(k-1,l)+R(k,l-1)$
- оценка $R(n,n)\le 2^{2n}$ (биномиальные коэффициенты)
- нижняя оценка: случайный граф
- оценка вероятности
- пересказ в виде оценки количеств
- пересказ в виде сжатия: если в графе из $n$ вершин есть монохроматический граф размера $k$, то можно вместо $k(k-1)/2$ битов обойтись $1+k\log n$ битами, получаем выигрыш при $k>\log n/2$ (примерно)
- Обход лабиринта на шахматной доске: существует последовательность команд (влево, вправо, вверх, вниз), при исполнении которой (невыполнимые команды пропускаются) мы обойдём доступную часть любого лабиринта на доске $8\times 8$ (при любом начальном положении).
- есть такое $N$, что вероятность обхода за $N$ случайных шагов положительна (для всех досок) --- не меньше $\varepsilon$;
- вероятность не обойти (данный лабиринт с данным началом) за $N$ шагов не больше $(1-\varepsilon)$;
- вероятность не обойти (данный лабиринт с данным началом) за $kN$ шагов не больше $(1-\varepsilon)^k$;
- при большом $k$ произведение $(1-\varepsilon)^k$ на число лабиринтов будет меньше $1$.
- Монотонная схема полиномиального размера и логарифмической глубины для функции majority:
- Постановка задачи: схемы, глубина, размер, монотонные схемы, универсальность, монотонная универсальность.
- Достаточно логарифмической глубины
- Схема: дерево с элементами $\mathrm{MAJ}_3$ логарифмической глубины и случайными переменными на листьях
- Оценка вероятности: функция $p\mapsto 3p^2-2p^3$ и её итерации. $O(\log n)$ шагов, чтобы отойти от середины; $O(1)$ шагов чтобы дойти до края; $O(\log n)$ чтобы сойтись к краю на расстояние $2^{-n}$