Давненько не постил сюда задач «на соображалку», вот ловите… недавно узнал чудесную задачу, лет 5 назад она мелькала на хабре, а потом обсуждалась на разных форумах. У нас есть три сундука, в каждом из которых лежит по две монетки (в первом — две золотые, во втором — одна золотая и одна серебряная, в третьем — две серебряные). Мы выбираем один из этих сундуков случайным образом и вслепую вытаскиваем одну из монеток. Она оказывается золотой. Какова вероятность того, что вторая монетка в этом сундуке — тоже золотая? Под катом, конечно, будет ответ. А пока подумайте, что изменится, если сундуков будет N+1: в первом 0 золотых, во втором — 1, …, в (N+1 )-м — N. И ещё сложнее: вытаскиваем не одну, а несколько монет, все оказались золотыми, какая вероятность, что следующая монета, вытащенная вслепую из этого же сундука, также золотая?
Итак, в изначальной задаче ответ, конечно, 2/3, хотя в интернете большинство отвечает 1/2. Первый раз Вы выбираете одну из 6 монет, которые лежат в сундуках. В половине случаев она будет золотой — т.е. в трёх случаях (выбираете золотую из второго сундука или первую или вторую золотую из третьего)! В двух из этих трёх случаев следующая выбранная из того же сундука монета будет золотой. Поэтому ответ: 2/3.
Напоминает парадокс Монти Холла, не правда ли? Теперь рассмотрим обобщения задачи, которые я сам придумал (вроде, в интернете нет).
У Вас N+1 сундук, в каждом лежит N монет. Всего: N(N+1)/2 золотых монет, столько же серебряных. Они распределены по сундукам так (см. рис. для случая N=5):
- в 1-м сундуке — все серебряные
- во 2-м сундуке — одна золотая
- в 3-м сундуке — две золотых
- …
- в (N+1)-м сундуке — все золотые
Мы выбираем один из этих сундуков случайным образом и вслепую вытаскиваем одну из монеток. Она оказывается золотой. Какова вероятность того, что вторая монетка, извлечённая вслепую из этого сундука, тоже золотая?
Удивительно, но ответ не зависит от N! Он всегда 2/3!
Действительно, наша извлечённая золотая монета — одна из N(N+1)/2. Она не может быть из первого сундука. Если она из второго — шансы вытащить следом золотую нулевые. Если она из третьего, то шансы вытащить следом золотую — 1/(N-1) и т.д. Получаем, что искомая вероятность равна
Осталось показать, что числитель равен знаменателю, поделённому на 3, что легко делается по индукции.
Лично меня этот факт (что ответ всегда 2/3) поразил и позабавил. Почему-то казалось, что с ростом N вероятность должна стремиться к 1/2. Ну или хоть как-то меняться, ведь в исходной задаче было ровно 3 сундука по 2 монеты, поэтому ответ, состоящий из 2 и 3 «не режет глаз», а почему так в N-мерном случае?! Но ещё больше моя интуиция подвела меня в таком обобщении:
У Вас N+1 сундук, в каждом лежит N монет. Всего: N(N+1)/2 золотых монет, столько же серебряных. Они распределены по сундукам так (см. рис. для случая N=5):
- в 1-м сундуке — все серебряные
- во 2-м сундуке — одна золотая
- в 3-м сундуке — две золотых
- …
- в (N+1)-м сундуке — все золотые
Мы выбираем один из этих сундуков случайным образом и вслепую вытаскиваем K монеток (K<N). Они все оказываются золотыми. Какова вероятность того, что следующая (K+1)-я монетка, вытащенная вслепую из этого же сундука, тоже золотая?
Пожалуй, ответ я не буду давать, жду его в комментариях… но он прекрасен;)
Анализ малых данных 
(k+1)/(k+2) ?:)
У меня получилось, что ещё надо поделить на (N — k — 1)!, но я почти наверное ошибся 🙂
Для проверки можно использовать решение для одной монетки, т.е. для k=1 должно получаться 2/3 (при любом N). И также логично предположить, что ответ от N не будет зависеть. В общем да, похоже, что где-то ошибка:)
Да, верно.
Интересно, что если случайно рассыпать монеты по сундукам, то после каждой извлечённой золотой монеты вероятность вытащить золото уменьшается (при большом числе монет не на много).
А здесь — увеличивается! Казалось бы, мы предложили достаточно случайную схему распределения монет по сундукам, но в ней «сундук в котором есть золото содержит ещё больше золота».
Всё дело как раз в распределении монет… случайное соответствует классике — здесь все сундуки будут иметь примерно равное число золотых и серебряных монет.
А вот наше распределение — что-то типа «тяжелохвостого». Все сундуки разные по числу золота: есть совсем без него, есть только с ним — и все они равновероятны…
Стало интересно про распределение — проделал некоторые вычисления. Оказалось, что
P(s = m|A) = (k+1) C^k_m / (N+1) C^k_N
* s = m — количество золотых монет в сундуке равно m;
* A — событие, что достали k золотых монет;
* C^k_m — количество сочетаний по k из m
Возможно, эту формулу можно еще упростить, но я не придумал как..
Так вот, интересно рассмотреть некоторые частные случаи:
* m = N (т.е. сундук, в котором все монеты золотые) : P = k+1 / N+1 — т.е вероятность растет линейно от k
* m = N-1(в сундуке 1 серебряная монета): P = (N-k)(k+1) / N(N+1) — зависит квадратично от k; максимум достигается на (N-1)/2, дальше убывает.
То есть, если мы достали больше половины монет и все оказались золотыми, то уже «наверняка» это последний сундук. Соответственно и возрастает вероятность того, что следующая монета окажется золотой.
Можно смотреть и дальше, но суть в принципе уже ясна: степень полинома возрастает; пик, на котором достигается максимум, приближается к 0.
P.S. Я бы прикрепил картинки, но тут, к сожалению, нет такой возможности:(
Здравствуйте, Александр! Спасибо за пост, прикольные задачки! 🙂 В самом начале (перед картинкой с сундуками) одна из задач сформулирована немного иначе: в последнем сундуке не N+1 золотых монет, а N, это так задумано? В этом случае, вероятность отличается от 2/3 (у меня получилось 2(N-1)^2/(3N(N+1))).
Ой, извините! 🙂 Я другую задачу решил: с предположением, что в сундуках по (N+1) монеток 🙂
Здравствуйте! Не понял вопроса… вроде, у меня везде всё согласовано. Сундуков всегда N+1, в каждом по N монет, в первом — 0 золотых, во втором — 1 золотая и т.д. В последнем ((N+1)-м) тогда N монет. Вы решили без последнего сундука?
А… понял. Кстати, вижу по профилю Ваш сайт http://efimov-ml.com/
Производит впечатление!
Доброго времени суток.
Где я ошибаюсь в рассуждениях? Ответ 50% кажется правильным из исходных данных.
P(A|B)=P(AB)\P(B)
B-событие, в котором после выбора сундука >=1 золотой монеты в нем
P(B)=2/3.
A-событие, в котором после выбора сундука =2 золотых монеты в нем
P(A)=1/3
В задаче требуется найти вероятность события A, после того как событие B уже наступило, т.е
P(A|B) -?
A и B зависимые события.
Вероятность совместного появления двух зависимых событий равна произведению вероятности одного из них на условную вероятность второго, вычисленную при условии, что первое событие произошло, т.е.
P(AB)=P(B)*P(A|B) => P(A|B)=P(AB)/P(B), где P(AB)=P(A), т.к событие A вложено в событие B.
P(A|B)=P(A)/P(B)=(1/3)/(2/3)=1/2
По заданному условию задачи полная ясность, что делается только один слепой выбор. Это переложение классической задачи с мишенью. Когда делаем один выстрел. И определить вероятность попадания в 10, если известно, что мы все-таки попали в мишень. Вероятность попадания куда-то в мишень 60%, а вероятность попадания в 10 — 30%.
Вы описали решение другой задачи. Собственно, Вы сами и написали какой: какая вероятность, что в сундуке 2 золотых монеты при условии, что в нем есть одна золотая монета. Такая вероятность — 1/2. Но у нас вопрос: какая вероятность вытащить вторую золотую монету после первой золотой. Т.е. не при условии, что мы знаем что там одна золотая (это мы бы посмотрели в сундук), а при условии, что мы вытащили золотую монету и она в руках (это и есть слепой выбор: мы точно знаем, что там уже была одна золотая монета и ничего не знаем про вторую). Поэтому надо учитывать, что из последнего сундука вытащить первое золото вероятнее, чем из второго.
P(2 зол | 1 зол) = Р(обе зол) / Р(1 зол)
Р(1 зол) = Р(1 зол|2й сундук)Р(2й сундук) + Р(1 зол|3й сундук)Р(3й сундук) = 0.5*1/3 + 1*1/3 = 1/2
P(2 зол | 1 зол) = Р(обе зол) / Р(1 зол) = (1/3) / (1/2) = 2/3
Александр, спасибо за разъяснение — полностью согласен с таким результатом при уточнении, что «какая вероятность вытащить вторую золотую монету после первой золотой», т,е в таком случае мы можем вытаскивать вторую монету из другого сундука. В формулировке задаче меня смутило именно то, что мы не можем менять выбор сундука после первого слепого выбора, а просто достаем оставшуюся вторую монету : «Какова вероятность того, что вторая монетка в этом сундуке — тоже золотая?»
Нет, минуточку. Всё так, как и написано: какая вероятность вытащить вторую золотую монету из ЭТОГО ЖЕ сундука (это я уж подразумевал по умолчанию — т.к об этом сказано в условии). Изначальная формулировка правильная — сундук мы не меняем.