matematik

В N конвертов с адресами наудачу вкладываются N писем.
Какова вероятность того, что ни одно письмо не дойдет до адресата?

     

Kaktus

100%, потому что письма отправятся в топку

     

MACTEP

Вероятность равна 1 т.к. все письма засунули в мешок, а мешок потеряли...

     

adam

все-таки 1/N

     

MACTEP

может тогда попробовать 1/N! ???

     

adam

это лишнее

     

DJ.

Я бы предположил (N-1)!/N^(N-1)

! - в смысле факториал, естно, а не то что сюда надо обратить особое внимание

Но это так на вскидку - думать не охота - СПАТЬ охота
Ушел спать....

     

adam

если взять N равное 2, то у вас вероятность того что не дойдет ничего равна 1
не рекомендую тогда больше одного письма отправлять за раз))

     

MACTEP

Попробуйте с N равным 6578^99...

     

DJ.

Гоните! (или считать не умеете) - если вместо Н в мое решение подставить 2, то получим вероятность 1/2, а никак не ничего Что есть правда ибо при двух письмах и двух конвертах мы можем либо их неправильно положить и тогда не дойдет (что нам и надо) либо положить их правильно и тогда дойдет (что нам не надо). Так что не гоните - при 2-х как раз как надо выходит, хотя признаюсь, когда я решал вчера ночью в сонном состоянии я для двойки не проверял

     

Kaktus

нее, побольше, чем 1/N...

     

adam

А сколько?

     

Kaktus

Да фиг его знает. В 1.5 раза примерно

     

adam

это домыслы

     

JUMP

Друзья Хотим мы этого или нет, но письма так и так не дойдут. Со спамом борется весь мир, самые активные разносчики спама - почтальоны, которые засыпают наши почтовые ящики спамом с утра до вечера, а мы подчастую даже не глядя, вместе с этим спамом выкидываем важную почту, потому что спам настолько пудрит мозги А что уж говорить что литера "N" тем более собъет с толку всех подряд. А в прошлом году судили 3х почтальонов их разнвх стран зо одно и то же нарушение. Они из за своей лени просто не разносят почту по почтовым ящикам а их за это судят и садят Друзья, звоните друг другу

     

vikulja

50% письма или дойдут, или нет

-----------------
случаюсь здесь

     

matematik

Ответ немножко сложнее

     

Kaktus

Может, я зря на тренировку ходил... В общем, при N>=4 получается больше, чем 1/N, в 1.5 раза (проверял N=4,5), при N=1--0, при N=2,3--1/N. Меня что смущает. Пример: нумеруем письма, соответствующие им конверты, берем конверт номер 1, засовываем письмо номер 2, берем конверт номер 2, благоприятных исходов будет не N-2, а побольше, можно любое письмо совать.
Давайте поставим Зуберу пиво, а он пусть наваяет программулю...Что-то вроде метода научного тыка, он же метод Монте-Карло

     

matematik

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

     

ank

Пиво - мне.
#include <iostream>
#include <algorithm>

int main()
{

const int N=40; // максимальное число конвертов
const int D=200000; // число попыток

int s[N];

for (int n=1; n<N; n++) {

int hits=0;
for (int i=0; i<n; i++)

s[i] = i;

for (int d=0; d<D; d++) {

std::random_shuffle( s, s+n );
for (int i=0; i<n; i++) {

if (s[i] == i) {

hits++;
break;

}

}

}
std::cout << "P["<<n<<"] = " << float(hits)/D << "(" << hits << "/" << D <<")\n";

}

}

     

adam

Лучше методом рационального угадывания))

     

Kaktus

Нее, я уже не шибко умный. Зря я пива в выходные хлопнул. На тренировке выносливости не хватило...

     

Kaktus

А давай программулю наваяем, поставим численные эктременты. Если моя формула подтвердится, объявим ее эмпирической и доказывать не будем...

     

ank

P[1] = 1(200000/200000)
P[2] = 0.500375(100075/200000)
P[3] = 0.66746(133492/200000)
P[4] = 0.625235(125047/200000)
P[5] = 0.63364(126728/200000)
P[6] = 0.632575(126515/200000)
P[7] = 0.630655(126131/200000)
P[8] = 0.63383(126766/200000)
P[9] = 0.63254(126508/200000)
P[10] = 0.632725(126545/200000)
P[11] = 0.62982(125964/200000)
P[12] = 0.63163(126326/200000)
P[13] = 0.63086(126172/200000)
P[14] = 0.632295(126459/200000)
P[15] = 0.631055(126211/200000)
P[16] = 0.631985(126397/200000)
P[17] = 0.633105(126621/200000)
P[18] = 0.632035(126407/200000)
P[19] = 0.63203(126406/200000)
P[20] = 0.6327(126540/200000)
P[21] = 0.6329(126580/200000)

     

matematik

Может, и вспомнишь из школы, как это число называется?

     

Kaktus

ank
Что-то не то. Ты давай понагляднее, чтобы попытки были во внешнем цикле (это которых 2000000)

     

ank

Отформатировал, чтобы смотрелось нагляднее.

     

matematik

Вот ведь как бывает.
Как программировать научатся, так школьный курс забывают...

     

ank

Полностью решение не выдам, начну только с первого абзаца (подсказки).

Допустим, что у нас есть n конвертов и k<=n писем. Обозначим вероятность того, что хотя-бы одно письмо доставлено по адресу P(k,n).
Дальше все очевидно ;-)

     

DJ.

Не понял! В первоначальных данных было н конвертов и н писем (т.е. число конвертов и писем равно), выходит что за ночь кто-то уже мог пару писем стащить, что их уже к стало??

     

Kaktus

Энто самое, оно на биноминальные коэффициенты не завязано? Я нашел функцию в октаве, так и быть, сам программулю наваяю и себе пиво поставлю

     

Kaktus

Я тоже пива хочууу.


N=3; %envelopes
P=100000; %popytki
cnt=0;
for p=1:P,
S=randperm(N); %shuffle

m=0; %match ?
for n=1:N,
if (S(n)==n),
m++;break;
end
end

if (m==0),
cnt++;
end

m=0;
end
cnt/P

     

DJ.

Вы сначала откомпилируйте и посчитайте результат

     

MACTEP

А не попробоваь ли вам посчитать вероятность того, сколько писем дойдёт и эту вероятность банально отнять от единицы = чтобы получить вероятность того, сколько писем не дойдёт.

     

Kaktus

Смотрим, что получилось:
P(2)=0.500800
P(3)=0.332600
P(4)=0.377800
P(5)=0.367300
P(6)=0.361400
P(7)=0.367300
P(8)=0.370200

Я же говорил, что побольше, чем 1/N

     

matematik

Сейчас-то хоть видите, как это элементарно написать можно?

     

Kaktus

Угу. Честно перебираем случай N=4 и нагло заявляем, что вероятность при N>=4 от N не зависит и равна 3/8

     

DJ.

А теперь докажи!

     

Kaktus

Дык, ставим серию опытов--вроде не зависит. Математик я что ли, чтобы строго доказывать, да еще аналитически
П.С. А может можно мат. индукцию приплести?

     

matematik

Звони шефу.
Может он - самый умный

     

Kaktus

что-то не то. При 5 тоже 3/8 получилось, доперебирался

     

matematik

Что, неужели и умным задачки про голодных черепах давать?

     

Plut

Можно не для самых умных и полегче, чтобы убедиться, что не совсем дурак...

     

Канарейка

Не для самых умных - задачка про черепах, я там уже отметилась, как наиболее активная из не самых умных...

     

matematik

N=1, 2, 3, 4, 5...
P=0, 1/2, 1/3, 3/8, 11/30...

     

ank

Думал, что задачка "на щелчок", а она оказалась чуть сложнее (ряд то - знакопеременный, а я его все хотел с одним знаком представить).

Знакопеременная сумма 1/k!.
Стремится она, соответственно к 1/e.

     

Kaktus

P= хз/144, хз/840, хз/(N!/N-1)... Похоже?

     

Kaktus

ХЗ=(N-2)!*2-1... вроде бы

А если так:
P=2/N+(1-N)/N!

Типа эмпирическая...

     

Eugene

Общее число исходов 2^N. Каждое из этих событий имеет равную вероятность. Соответственно вероятность того что ни одно письмо не дойдет до адресата 1/(2^N). Или не так?

     

ank

Все не так
Общее число исходов N! (в смысле N-факториал).
Ни одно письмо не дойдет в нескольких случаях, а не в одном.
Уже при N=3 видно, что такое решение не проходит.

     

Inga Zayonc

Что-то задачка не очень-то и легкая, имхо.
Вот если бы было, какова вероятность, что ровно одно письмо не по адресу, я бы сразу решила.

     

matematik

Легкая, но для самых...
Для таких, как ank.

     

kolobok

если Н равно нулю то 100 процентов

     

Kaktus

Чего-то я не то угадал...