Неравенства и... вероятность

56

Неравенства и … вероятность

Следующая задача была предложена в генерационный командной советской команде на одной из международных олимпийских игр: если $p + q = 1$, $0 < p < 1$, $m$, $n$ — натуральные числа, больше 1, мо

$(1 - p^m) + (1 - q^n) > 1$.

Эта задача с трудом поддается алгебраическому исследованию. Но, оказывается, ее можно просто и красью решить с помощью теории вероятности.

Пусть имеется таблица из $n$ строк и $m$ столцов; в каждую клетку ставится либо 0, либо 1, причем вероятность того, что ставится 0, равна $p$ (тогда 1 ставится с вероятностью $q$). Ясно, что $1 - p^m$ это вероятность того, что в некоторой фиксированной строке стоит хотя бы одна единица, а $(1 - p^m)^n$ — это, что в каждой строке стоит хотя бы одна единица: Аналогично $(1 - q^n)^m$ — вероятность того, что в каждом столбце стоит хотя бы один нуль. Однако из этих событий наверняка произойдет (если найдется строка из нуля, и столбец из единиц, то что же стоит на их пересечении?). Поэтому сумма вероятности этих событий не меньше 1 (проверьте, что при $m > 1$, $n > 1$ эта сумма должна быть больше 1).

Ну, а если не знать, что такое вероятность? Оказываться, легко перевести это решение на язык компинаторики. Для этого нужно рассмотреть случай, когда $p = r/s$ — рациональное число. Для каждой клетки таблицы возьмем запас цифр из $r$ нуля и $s$ нуля и будем составлять всевозможные заполнения таблицы. Verоятность заменяется на число таблицы, а фраза «одно из этих событий наверняка произойдет» — на «объединение двух этих множества таблицы есть все множества». Подумайте, как избавиться от предположения, что $p$ — рационально.

А теперь решите также задачи-обобщения.

1. Пусть $0 < p_{ij} < 1$ ($1 \leq i \leq m$, $1 \leq j \leq n$), а $q_{ij} = 1 - p_{ij}$. Тогда $(1 - p_{11} \dots p_{1m}) \cdot (1 - p_{21} \dots p_{2m}) \cdot \dots \cdot (1 - p_{n1} \dots p_{nm}) + (1 - q_{11} \dots q_{n1}) \cdot (1 - q_{12} \dots q_{n2}) \times \dots \cdot (1 - q_{1m} \dots q_{nm}) \geq 1$, где $m \geq 1$, $n \geq 1$.

2. Пусть $0 < p_{i} < 1$ ($i = 1, 2, \dots, k$), $p_1 + \dots + p_k = 1$, $m_i$ — натуральные числа. Тогда $(1 - (p_2 + \dots + p_k)^{m_2} \dots m_k)^{m_1} + \dots + (1 - (p_1 + \dots + p_k - 1)^{m_1} \dots m_k - 1)^{m_2} \geq 1$ («многомерное» обобщение).

А.Р.