View Full Version : Легкая задачка для самых умных
matematik
28-02-2006, 23:20
В N конвертов с адресами наудачу вкладываются N писем.
Какова вероятность того, что ни одно письмо не дойдет до адресата?
100%, потому что письма отправятся в топку
В N конвертов с адресами наудачу вкладываются N писем.
Какова вероятность того, что ни одно письмо не дойдет до адресата?
Вероятность равна 1 т.к. все письма засунули в мешок, а мешок потеряли...
все-таки 1/N :)
может тогда попробовать 1/N! ???
может тогда попробовать 1/N! ???
это лишнее:)
нее, побольше, чем 1/N...
нее, побольше, чем 1/N...
А сколько?:)
Да фиг его знает. В 1.5 раза примерно
Да фиг его знает. В 1.5 раза примерно
это домыслы
может тогда попробовать 1/N! ???
Я бы предположил (N-1)!/N^(N-1)
! - в смысле факториал, естно, а не то что сюда надо обратить особое внимание :)
Но это так на вскидку - думать не охота - СПАТЬ охота :)
Ушел спать.... :nukkuu: :)
Я бы предположил (N-1)!/N^(N-1)
! - в смысле факториал, естно, а не то что сюда надо обратить особое внимание :)
Но это так на вскидку - думать не охота - СПАТЬ охота :)
Ушел спать.... :nukkuu: :)
если взять N равное 2, то у вас вероятность того что не дойдет ничего равна 1
не рекомендую тогда больше одного письма отправлять за раз:)))
если взять N равное 2, то у вас вероятность того что не дойдет ничего равна 1
не рекомендую тогда больше одного письма отправлять за раз:)))
Попробуйте с N равным 6578^99...
Попробуйте с N равным 6578^99...
А зачем?:)
matematik
01-03-2006, 08:45
Вероятность события - отношение числа благоприятных исходов(исходов, в которых событие происходит), к числу всех возможных исходов.
У нас число всех исходов есть число всех способов размещения писем по конвертам, которое равно N!
Канарейка
01-03-2006, 08:54
Вероятность события - отношение числа благоприятных исходов(исходов, в которых событие происходит), к числу всех возможных исходов.
У нас число всех исходов есть число всех способов размещения писем по конвертам, которое равно N!
Задачка детская! Какакя вероятность? 50%! Либо попадет либо нет!
Друзья :) Хотим мы этого или нет, но письма так и так не дойдут. Со спамом борется весь мир, самые активные разносчики спама - почтальоны, которые засыпают наши почтовые ящики спамом с утра до вечера, а мы подчастую даже не глядя, вместе с этим спамом выкидываем важную почту, потому что спам настолько пудрит мозги :) А что уж говорить что литера "N" тем более собъет с толку всех подряд. А в прошлом году судили 3х почтальонов их разнвх стран зо одно и то же нарушение. Они из за своей лени просто не разносят почту по почтовым ящикам а их за это судят и садят :) Друзья, звоните друг другу :) :) :)
matematik
01-03-2006, 09:00
Задачка детская! Какакя вероятность? 50%! Либо попадет либо нет!
Умница, Канарейка!
Ты правильно начала размышлять!
И первое утверждение из твоего сообщения - верное!
Действительно, задачка детская!
50% письма или дойдут, или нет :)
matematik
01-03-2006, 09:19
50% письма или дойдут, или нет :)
Ответ немножко сложнее
Может, я зря на тренировку ходил... В общем, при N>=4 получается больше, чем 1/N, в 1.5 раза (проверял N=4,5), при N=1--0, при N=2,3--1/N. Меня что смущает. Пример: нумеруем письма, соответствующие им конверты, берем конверт номер 1, засовываем письмо номер 2, берем конверт номер 2, благоприятных исходов будет не N-2, а побольше, можно любое письмо совать.
Давайте поставим Зуберу пиво, а он пусть наваяет программулю...Что-то вроде метода научного тыка, он же метод Монте-Карло
matematik
01-03-2006, 09:33
Может, я зря на тренировку ходил... В общем, при N>=4 получается больше, чем 1/N, в 1.5 раза (проверял N=4,5), при N=1--0, при N=2,3--1/N. Меня что смущает. Пример: нумеруем письма, соответствующие им конверты, берем конверт номер 1, засовываем письмо номер 2, берем конверт номер 2, благоприятных исходов будет не N-2, а побольше, можно любое письмо совать.
Давайте поставим Зуберу пиво, а он пусть наваяет программулю...Что-то вроде метода научного тыка, он же метод Монте-Карло
Вот и самые умные подтягиваются.
Может, попросим блондинок на этой задачке отдохнуть?
Она же изначально была рассчитана на оченно умных восьмиклассников.
Как-некоторые из нас несколько лет назад.
Нее, я уже не шибко умный. Зря я пива в выходные хлопнул. На тренировке выносливости не хватило...
Давайте поставим Зуберу пиво, а он пусть наваяет программулю...Что-то вроде метода научного тыка, он же метод Монте-Карло
Пиво - мне.
#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";
}
}
А давай программулю наваяем, поставим численные эктременты. Если моя формула подтвердится, объявим ее эмпирической и доказывать не будем...
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)
ank
Что-то не то. Ты давай понагляднее, чтобы попытки были во внешнем цикле (это которых 2000000)
Полностью решение не выдам, начну только с первого абзаца (подсказки).
Допустим, что у нас есть n конвертов и k<=n писем. Обозначим вероятность того, что хотя-бы одно письмо доставлено по адресу P(k,n).
Дальше все очевидно ;-)
Давайте поставим Зуберу пиво, а он пусть наваяет программулю...Что-то вроде метода научного тыка, он же метод Монте-Карло
Лучше методом рационального угадывания:)))
matematik
01-03-2006, 09:49
P[1] = 1(200000/200000)
P[2] = 0.500375(100075/200000)
P[3] = 0.66746(133492/200000)
P[4] = 0.625235(125047/200000)
P[20] = 0.6327(126540/200000)
P[21] = 0.6329(126580/200000)
Может, и вспомнишь из школы, как это число называется?
Энто самое, оно на биноминальные коэффициенты не завязано? Я нашел функцию в октаве, так и быть, сам программулю наваяю и себе пиво поставлю
ank
Что-то не то. Ты давай понагляднее, чтобы попытки были во внешнем цикле (это которых 2000000)
Отформатировал, чтобы смотрелось нагляднее.
matematik
01-03-2006, 10:03
Вот ведь как бывает.
Как программировать научатся, так школьный курс забывают...
если взять N равное 2, то у вас вероятность того что не дойдет ничего равна 1
не рекомендую тогда больше одного письма отправлять за раз:)))
Гоните! (или считать не умеете) - если вместо Н в мое решение подставить 2, то получим вероятность 1/2, а никак не ничего :) Что есть правда ибо при двух письмах и двух конвертах мы можем либо их неправильно положить и тогда не дойдет (что нам и надо) либо положить их правильно и тогда дойдет (что нам не надо). Так что не гоните - при 2-х как раз как надо выходит, хотя признаюсь, когда я решал вчера ночью в сонном состоянии я для двойки не проверял :)
Полностью решение не выдам, начну только с первого абзаца (подсказки).
Допустим, что у нас есть n конвертов и k<=n писем. Обозначим вероятность того, что хотя-бы одно письмо доставлено по адресу P(k,n).
Дальше все очевидно ;-)
Не понял! В первоначальных данных было н конвертов и н писем (т.е. число конвертов и писем равно), выходит что за ночь кто-то уже мог пару писем стащить, что их уже к стало?? :)
Гоните! (или считать не умеете) - если вместо Н в мое решение подставить 2, то получим вероятность 1/2, а никак не ничего :) Что есть правда ибо при двух письмах и двух конвертах мы можем либо их неправильно положить и тогда не дойдет (что нам и надо) либо положить их правильно и тогда дойдет (что нам не надо). Так что не гоните - при 2-х как раз как надо выходит, хотя признаюсь, когда я решал вчера ночью в сонном состоянии я для двойки не проверял :)
Извините переклинело вчера ночью:) прочитал как .../(N-1)^N
бывает:)
У нас число всех исходов есть число всех способов размещения писем по конвертам, которое равно N!
Это если учесть что в один конверт нельзя положить два письма! А об этом в задаче сказано не было! Было сказано что пихают куда попало :)
Я тоже пива хочууу.
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
01-03-2006, 10:25
Это если учесть что в один конверт нельзя положить два письма! А об этом в задаче сказано не было! Было сказано что пихают куда попало :)
Не, сказано ясно.
Не куда попало.
"В N конвертов с адресами наудачу вкладываются N писем."
К примеру - 25 писем вложены РОВНО в 25 конвертов
А не попробоваь ли вам посчитать вероятность того, сколько писем дойдёт и эту вероятность банально отнять от единицы = чтобы получить вероятность того, сколько писем не дойдёт.
Я тоже пива хочууу.
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
Вы сначала откомпилируйте и посчитайте результат :)
Смотрим, что получилось:
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
01-03-2006, 10:44
Смотрим, что получилось:
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
Сейчас-то хоть видите, как это элементарно написать можно?
Угу. Честно перебираем случай N=4 и нагло заявляем, что вероятность при N>=4 от N не зависит :) и равна 3/8
Вероятность события - отношение числа благоприятных исходов(исходов, в которых событие происходит), к числу всех возможных исходов.
У нас число всех исходов есть число всех способов размещения писем по конвертам, которое равно N!
Исходя их этого, могу предположить, что вероятность равна N/N!
Например: 5 писем и 5 конвертов. Вероятность того, что все они не дойдут равна
5/5! = 41,6667*10^-3 При увеличении числа писем и конвертов вероятность порядком уменьшается. То есть уже при 20 письмах и конвертах, вероятность того, что ни одно из них не достигнет адресата равна 8,220*10^-18
Угу. Честно перебираем случай N=4 и нагло заявляем, что вероятность при N>=4 от N не зависит :) и равна 3/8
А теперь докажи! :D
Не, сказано ясно.
Не куда попало.
"В N конвертов с адресами наудачу вкладываются N писем."
К примеру - 25 писем вложены РОВНО в 25 конвертов
Вкладываются, а не уже вложены и нигде не указано что в результате все 25 конвертов окажутся с письмами - в 25 конвертов можно вложить 25 писем так что в одном из конвертов будет 2 письма, а в одном ничего :)
Но не важно - пусть будет по Вашему :)
Дык, ставим серию опытов--вроде не зависит. Математик я что ли, чтобы строго доказывать, да еще аналитически :)
П.С. А может можно мат. индукцию приплести?
matematik
01-03-2006, 11:08
Дык, ставим серию опытов--вроде не зависит. Математик я что ли, чтобы строго доказывать, да еще аналитически :)
П.С. А может можно мат. индукцию приплести?
Звони шефу.
Может он - самый умный
То есть уже при 20 письмах и конвертах, вероятность того, что ни одно из них не достигнет адресата равна 8,220*10^-18
Вероятность того, что ни одно письмо не дойжет до адресата, должна увеличиватся на мой взгляд.
matematik
01-03-2006, 11:21
Вероятность того, что ни одно письмо не дойжет до адресата, должна увеличиватся на мой взгляд.
Мы как-то незаметно стали решать две задачки сразу
Первая какова вероятность?
1 - 0
2 - половинка
3 - одна треть
Если вручную посчитать и для 4 и для 5, то формулу можно и угадать, а дальше - по индукции.
и вторая задачка - есть ли предел при большом количестве конвертов
Вторая - чуть посложнее, но тоже достаточно школьных знаний
что-то не то. При 5 тоже 3/8 получилось, доперебирался
matematik
02-03-2006, 21:29
Что, неужели и умным задачки про голодных черепах давать?
Можно не для самых умных и полегче, чтобы убедиться, что не совсем дурак...:)
Канарейка
02-03-2006, 21:58
Можно не для самых умных и полегче, чтобы убедиться, что не совсем дурак...:)
Не для самых умных - задачка про черепах, я там уже отметилась, как наиболее активная из не самых умных... :xaplodit:
matematik
02-03-2006, 22:11
N=1, 2, 3, 4, 5...
P=0, 1/2, 1/3, 3/8, 11/30...
Думал, что задачка "на щелчок", а она оказалась чуть сложнее (ряд то - знакопеременный, а я его все хотел с одним знаком представить).
Знакопеременная сумма 1/k!.
Стремится она, соответственно к 1/e.
P= хз/144, хз/840, хз/(N!/N-1)... Похоже?
ХЗ=(N-2)!*2-1... вроде бы
А если так:
P=2/N+(1-N)/N!
Типа эмпирическая...
Общее число исходов 2^N. Каждое из этих событий имеет равную вероятность. Соответственно вероятность того что ни одно письмо не дойдет до адресата 1/(2^N). Или не так? :)
В N конвертов с адресами наудачу вкладываются N писем.
Какова вероятность того, что ни одно письмо не дойдет до адресата?
если Н равно нулю то 100 процентов :)
Чего-то я не то угадал...
Общее число исходов 2^N. Каждое из этих событий имеет равную вероятность. Соответственно вероятность того что ни одно письмо не дойдет до адресата 1/(2^N). Или не так? :)
Все не так :)
Общее число исходов N! (в смысле N-факториал).
Ни одно письмо не дойдет в нескольких случаях, а не в одном.
Уже при N=3 видно, что такое решение не проходит.
Inga Zayonc
03-03-2006, 22:53
Что-то задачка не очень-то и легкая, имхо.
Вот если бы было, какова вероятность, что ровно одно письмо не по адресу, я бы сразу решила.
matematik
03-03-2006, 23:00
Что-то задачка не очень-то и легкая, имхо.
Легкая, но для самых...
Для таких, как ank.
Inga Zayonc
04-03-2006, 10:04
Легкая, но для самых...На самых и не претедуем, просто в моем понимании легкая задачка - это значит можно решить в уме, если конечно озарит плодотворная дебютная идея. А тут факториалы, знакопеременные ряды какие-то, я и слов таких не знаю :lamo:
[russian.fi, 2002-2014]