matematik

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

     

Kaktus

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

     

MACTEP

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

     

adam

все-таки 1/N

     

MACTEP

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

     

adam

это лишнее

     

Kaktus

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

     

adam

А сколько?

     

Kaktus

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

     

adam

это домыслы

     

DJ.

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

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

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

     

adam

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

     

MACTEP

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

     

adam

А зачем?

     

matematik

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

     

Канарейка

Задачка детская! Какакя вероятность? 50%! Либо попадет либо нет!

     

JUMP

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

     

matematik

Умница, Канарейка!
Ты правильно начала размышлять!
И первое утверждение из твоего сообщения - верное!
Действительно, задачка детская!

     

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

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

     

Kaktus

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

     

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";

}

}

     

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)

     

Kaktus

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

     

ank

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

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

     

adam

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

     

matematik

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

     

Kaktus

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

     

ank

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

     

matematik

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

     

DJ.

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

     

DJ.

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

     

adam

Извините переклинело вчера ночью прочитал как .../(N-1)^N
бывает

     

DJ.

Это если учесть что в один конверт нельзя положить два письма! А об этом в задаче сказано не было! Было сказано что пихают куда попало

     

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

     

matematik

Не, сказано ясно.
Не куда попало.
"В N конвертов с адресами наудачу вкладываются N писем."
К примеру - 25 писем вложены РОВНО в 25 конвертов

     

MACTEP

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

     

DJ.

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

     

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

     

MACTEP

Исходя их этого, могу предположить, что вероятность равна N/N!

Например: 5 писем и 5 конвертов. Вероятность того, что все они не дойдут равна
5/5! = 41,6667*10^-3 При увеличении числа писем и конвертов вероятность порядком уменьшается. То есть уже при 20 письмах и конвертах, вероятность того, что ни одно из них не достигнет адресата равна 8,220*10^-18

     

DJ.

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

     

DJ.

Вкладываются, а не уже вложены и нигде не указано что в результате все 25 конвертов окажутся с письмами - в 25 конвертов можно вложить 25 писем так что в одном из конвертов будет 2 письма, а в одном ничего

Но не важно - пусть будет по Вашему

     

Kaktus

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

     

matematik

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

     

adam

Вероятность того, что ни одно письмо не дойжет до адресата, должна увеличиватся на мой взгляд.

     

matematik

Мы как-то незаметно стали решать две задачки сразу

Первая какова вероятность?

1 - 0

2 - половинка

3 - одна треть
Если вручную посчитать и для 4 и для 5, то формулу можно и угадать, а дальше - по индукции.

и вторая задачка - есть ли предел при большом количестве конвертов

Вторая - чуть посложнее, но тоже достаточно школьных знаний

     

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!

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