{
\newcommand*{\E}[1]{\ensuremath{\mathrm{E}\left[{#1}\right]}}
\renewcommand*{\Pr}[1]{\ensuremath{\mathrm{P}\left[{#1}\right]}}
Рассмотрим алгоритм, который просто возвращает случайную перестановку маркеров. Посчитаем матожидание числа ограничений $x$, которым удовлетворяет эта перестановка. Введем индикаторную величину $x_i$, равную единице, если ограничение с номером $i$ выполнено, и нулю иначе. Тогда $\E{x} = \E{\sum_{i = 1}^{t} x_i} = \sum_{i = 1}^{t} \E{x_i}$. При этом для любого $i$ мы знаем, что $\E{x_i} = \Pr{x_i = 1} = \frac{1}{3}$, так как для каждого ограничения нахождение какого-то одного из трех маркеров между двумя другими равновероятно (можно, например, их перенумеровать). Таким образом, $\E{x} = t\frac{1}{3} = \frac{t}{3}$. Это не может отличаться от оптимального решение не более, чем в $\alpha = 3$ раз, так как в оптимальном решении не может быть удовлетворено более $t$ oграничений (их всего $t$).
}