Первый кандидат при подсчете всегда опережал второго

[Zo]

Есть следующая задачка.
Два кандидата получили на выборах n и m голосов соответственно, причем n>m. Какова вероятность того, что при подсчете голосов первый кандидат всегда опережал второго?

Подскажите, пожалуйста, как ее решать или где есть решение.

[Dan_Te]

Условие написано ОЧЕНЬ нечетко. Я предполагаю, что
1) каждую секунду проверяют одну анкету и учитывают один новый голос
2) допускается одинаковое кол-во голосов у кандидатов в какие-то моменты времени. Например, в начальный момент времени.

Представим себе целочисленную решетку, точнее прямоуг-к с углами (0,0) и (n,m). Вначале мы находимся в точке (0,0), каждая анкета за победителя - шаг вправо, за проигравшего - шаг вверх. Нас интересуют пути из нуля в (n,m), не пересекающие прямую х=у. Точнее, кол-во таких путей.

Начинаем считать. Из (0,0)
можно попасть в (1,0) одним способом
можно попасть в (1,1) одним способом, через (1,0)
можно попасть в (2,0) одним способом, через (1,0)
можно попасть в (2,1) двумя способами, через (2,0) или (1,1)
...

В точках решетки пишем кол-во способов, которыми туда можно попасть. Видим и доказываем по индукции, что в точке (a,b) надо писать C_a^b.
Отсюда ответ: p = C_n^m / 2^(n+m)

[Yasha]

ваше решение не верно.
ответ: (n-m)/(n+m).
смотрите например в ГНЕДЕНКО.

[Dan_Te]

Ох, я и правда бред написал. Целых две ошибки.
Решить указанным мной методом можно, но уже не так просто, как хотелось бы.

Для случая, когда кандидатам разрешено иметь одинаковое кол-во голосов ответ будет (n-m+1)/(n+1). Ответ (n-m)/(n+m) получается, если им нельзя иметь одинаковое кол-во голосов, кроме как в начальный момент времени.

[AndriyMarevich]

Неграматно написано условие!
Если позволять те подсчёты, в которых бюллетений за кондитатов оказывается поровну в некоторых моментах, то:
$P(n>=m ALWAYS)=f(m;n)/P(m;n)$
$f(y;x)=P(y;x)- \sum_{i=0}^{y-1}f(i;i)P(y-i-1;x-i)$

начальное условие: $f(0;0)=1$
также надо иметь в виду:

$f(1;x)=x$ и $f(0;x)=1$

т.к. $\sum_{i=0}^{y-1}=0$, если $y-1<0$

Не знаю как выразить аналитически $f(i;i)$ только

[AndriyMarevich]

AndriyMarevich в сообщении #341315 писал(а):

$n>=m ALWAYS$

Не обращайте на эту надпись внимания

[AndriyMarevich]

AndriyMarevich в сообщении #341315 писал(а):

Если позволять те подсчёты, в которых бюллетений за кондитатов оказывается поровну в некоторых моментах

Заново пишу решение, но теперь с объяснениями.
$f(x;y)$ - множество всевозможных извлечений всех бюллетений ($x$ за проигравшего и $y$ за победителя) при каждом из которых (извлечений) выполняется условие: $Y \ge X$ ($Y$ это количество достанных бюллетений за победителя, а $X$ - за его оппонента).

$$f(x;y)=P(x;y)-|\bigcup\limits_{k=1}^{x+y}M_{k}|$$

$M_k$ - множество всех доставаний всех бюллетений при которых (доставаниях) выполняется условие:
условие $Y \ge X$ нарушается впервые непосредственно после вынимания из урны $k$-го бюллетеня.
Множества $M_k (k=1,...,x+y)$не пересекаются.
Нужно заметить, что $|M_{k}|=0$, если $k=2q$, где $q \in N$
А так же, что условие $Y \ge X$ может впервые нарушиться максимум непосредственно после $(2x -1)$ выниманий бюллетений.
Поэтому: $|M_{2i+1}|=f(i;i)P(x-i-1;y-i)$
Наконец, решение задачи:

$$\frac{P(x;y)-\sum\limits_{i=0}^{x-1}f(i;i)P(x-i-1;y-i)}{P(x;y)}$$

Как найти $f(0;0)$?
$f(0;0)=P(0;0)-\sum\limits_{i=0}^{-1}f(i;i)P(-1-i;-i)=\frac{0!}{0!0!}-0=1$

-- Чт авг 12, 2010 19:52:42 --

Если в задаче условие: "не иметь одинакового количества достанных бюллетений за 1-го и 2-го кандидатов", то ответ:

$$\frac{f(x;y-1)}{P(x;y)}$$

(первый вытянутый бюллетень за победителя)

[AndriyMarevich]

Задача на ту же тему.
Два игрока играют $N$ раз в орлянку.
Какова вероятность того, что их выигрыши не совпадали после каждой игры?
решение:

$$\frac{2^{N-1}-\sum\limits_{i=0}^{i_{konechnoe}}f(i;i)2^{N-2i-2}}{2^N}2$$

Как найти $i_{konechnoe}$?

$$ \left\{ \begin{array}{l} 2i < N-1,\\ i_{konechnoe}= max(i), \end{array} \right. $$

откуда $i_{konechnoe}=[\frac{N}{2}]-1$
ответ задачи:

$$2\frac{2^{N-1}-\sum\limits_{i=0}^{[\frac{N}{2}]-1}f(i;i)2^{N-2i-2}}{2^N}=1-\sum\limits_{i=0}^{[\frac{N}{2}]-1}\frac{f(i;i)}{2^{2i+1}}$$

[--mS--]

А можно вкратце объяснить, что это такое Вы тут пишете и зачем? Какой-то полный сюрреализм. Множества делим непонятно на что, получаем "ответы", в которых одни неизвестные величины и т.п.

[AndriyMarevich]

Почему неизвестные величины? $f(x;y)$ это рекурентная функция.

[PAV]

AndriyMarevich
строгое замечание за систематическое поднятие давно обсужденных тем (в просторечье - за некрофилию), а также малосодержательные, дурно изложенные, а порой просто неверные комментарии, которые могут сбить читателей с толку. Что касается данного конкретного случая, то для конкретных чисел значение можно посчитать рекуррентно, хотя в Вашем изложении понять суть этого способа совершенно нереально. Однако речь идет о точном значении вероятности, вычисляемом по непосредственной формуле. Этот ответ вместе со ссылкой приведен уже выше в сообщении Yasha. Он очень простой и конкретный, в отличие от всего, что Вы здесь понаписали.

Данный форум преследует образовательные цели, поэтому безграмотные советы фактически являются нарушением. Оказывать помощь нужно только при условии, что сам точно в теме. А написанное Вами - это не решение, а какая-то бессмыслица.