Вероятностный метод: средние

Если среднее (математическое ожидание) больше $\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}$