Сундуки и монеты

Давненько не постил сюда задач «на соображалку», вот ловите… недавно узнал чудесную задачу, лет 5 назад она мелькала на хабре, а потом обсуждалась на разных форумах. У нас есть три сундука, в каждом из которых лежит по две монетки (в первом — две золотые, во втором — одна золотая и одна серебряная, в третьем — две серебряные). Мы выбираем один из этих сундуков случайным образом и вслепую вытаскиваем одну из монеток. Она оказывается золотой. Какова вероятность того, что вторая монетка в этом сундуке — тоже золотая? Под катом, конечно, будет ответ. А пока подумайте, что изменится, если сундуков будет N+1: в первом 0 золотых, во втором — 1, …, в (N+1 )-м — N. И ещё сложнее: вытаскиваем не одну, а несколько монет, все оказались золотыми, какая вероятность, что следующая монета, вытащенная вслепую из этого же сундука, также золотая?

monety

Итак, в изначальной задаче ответ, конечно, 2/3, хотя в интернете большинство отвечает 1/2. Первый раз Вы выбираете одну из 6 монет, которые лежат в сундуках. В половине случаев она будет золотой — т.е. в трёх случаях (выбираете золотую из второго сундука или первую или вторую золотую из третьего)! В двух из этих трёх случаев следующая выбранная из того же сундука монета  будет золотой. Поэтому ответ: 2/3.

Напоминает парадокс Монти Холла, не правда ли? Теперь рассмотрим обобщения задачи, которые я сам придумал (вроде, в интернете нет).

У Вас N+1 сундук, в каждом лежит N монет. Всего: N(N+1)/2 золотых монет, столько же серебряных. Они распределены по сундукам так (см. рис. для случая N=5):

  • в 1-м сундуке — все серебряные
  • во 2-м сундуке — одна золотая
  • в 3-м сундуке — две золотых
  • в (N+1)-м сундуке — все золотые

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

sunduki

Удивительно, но ответ не зависит от N! Он всегда 2/3!

Действительно, наша извлечённая золотая монета — одна из N(N+1)/2. Она не может быть из первого сундука. Если она из второго — шансы вытащить следом золотую нулевые. Если она из третьего, то шансы вытащить следом золотую — 1/(N-1) и т.д. Получаем, что искомая вероятность равна

formula

Осталось показать, что числитель равен знаменателю, поделённому на 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)-я монетка, вытащенная вслепую из этого же сундука, тоже золотая?

Пожалуй, ответ я не буду давать, жду его в комментариях… но он прекрасен;)

Реклама

13 thoughts on “Сундуки и монеты

      • Для проверки можно использовать решение для одной монетки, т.е. для 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. Я бы прикрепил картинки, но тут, к сожалению, нет такой возможности:(

  1. Здравствуйте, Александр! Спасибо за пост, прикольные задачки! 🙂 В самом начале (перед картинкой с сундуками) одна из задач сформулирована немного иначе: в последнем сундуке не N+1 золотых монет, а N, это так задумано? В этом случае, вероятность отличается от 2/3 (у меня получилось 2(N-1)^2/(3N(N+1))).

    • Здравствуйте! Не понял вопроса… вроде, у меня везде всё согласовано. Сундуков всегда N+1, в каждом по N монет, в первом — 0 золотых, во втором — 1 золотая и т.д. В последнем ((N+1)-м) тогда N монет. Вы решили без последнего сундука?

  2. Доброго времени суток.
    Где я ошибаюсь в рассуждениях? Ответ 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

      • Александр, спасибо за разъяснение — полностью согласен с таким результатом при уточнении, что «какая вероятность вытащить вторую золотую монету после первой золотой», т,е в таком случае мы можем вытаскивать вторую монету из другого сундука. В формулировке задаче меня смутило именно то, что мы не можем менять выбор сундука после первого слепого выбора, а просто достаем оставшуюся вторую монету : «Какова вероятность того, что вторая монетка в этом сундуке — тоже золотая?»

      • Нет, минуточку. Всё так, как и написано: какая вероятность вытащить вторую золотую монету из ЭТОГО ЖЕ сундука (это я уж подразумевал по умолчанию — т.к об этом сказано в условии). Изначальная формулировка правильная — сундук мы не меняем.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s