9 нояб. 2009 г.

Замуж за иностранца

Иногда возникает ощущение, что люди делают так, чтобы им было лучше. Это простая и естественная формулировка, которая привычно пропускает один важный момент. Люди стараются сделать так, как им кажется будет лучше. И иногда им кажется правильно.

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

Давайте попробуем разобраться в такой ситуации, где не очень ясно, что известно, а что неизвестно. Возьмём для примера женатых и холостых иностранцев, которые женились друг на друге и повыходили замуж, а теперь имеют всякие хитрые взаимоотношения. Эту забавную задачку я узнал из комментария к недавней заметке об IQ тесте:

Джек женат, но любит Анну, которая влюблена в холостого Джорджа. Верно ли, что человек, состоящий в браке, любит человека, в браке не состоящего?

Варианты ответа: «Да, это так», «Нет, это не так», «Мало данных для точного ответа», «Я уже видел эту задачку, поэтому знаю ответ». Пожалуйста, оставьте своё мнение в комментариях к заметке, не читая чужих версий.

Скорее всего, в одной из следующих заметок мы разберёмся с этой задачей, а пока я предлагаю вернуться к парадоксу раздачи подарков. Поскольку меня попросили рассказать, как найти точное решение, а изложить его в комментариях не очень легко, так как оно достаточно объёмное, то посвятим этому делу вторую половину сегодняшней заметки.

Если вам не очень интересно читать длинные и подробные математические рассуждения, то предлагаю прочесть только подведение итогов - от абзаца, начинающегося словами «Уф-ф...» :)

Сразу предупрежу, что ниже предложен не самый короткий путь, потому что у меня нет цели быстро доказать, что данная формула верна. Главная задача - показать, как до неё можно дойти. Я привожу ход мыслей, который кому-то покажется корявым, а кому-то понятным, потому что все люди разные. Надеюсь, желающие смогут прорваться сквозь лишние подробности.

Итак, есть N подарков и N людей, каждый из которых получит ровно один подарок. Это значит, что есть ровно N! способов раздать подарки этим людям (первый получает один из N подарков, второй - один из (N-1) оставшихся подарков, третьему достанется один из (N-2) подарков и так далее). Перемножаем все эти независимые случаи, получаем N*(N-1)*(N-2)*(N-3)*...*2. Запомним этот результат, он нам много раз пригодится.

Теперь давайте разберём случай, в котором первый человек уже получил свой подарок. Это значит, что у нас осталось (N-1) людей и (N-1) подарков (причём каждый подарок принёс один из этих оставшихся). Сколькими способами они могут распределить эти подарки между собой? Как мы установили в предыдущем абзаце, есть (N-1)! способов. Давайте это запомним: если один человек получил свой же подарок, то остальные (N-1) человек могут распределить между собой подарки (N-1)! способами.

Теперь рассмотрим ситуацию, когда второй человек получил свой подарок. Оставшиеся опять могут распределить подарки X1=(N-1)! способами. Аналогично для третьего, четвёртого,... , N-ного участника. Получается, что если сложить все эти случаи, то выйдет N*X1=N*(N-1)!, что как раз равно Y1=N!. Пока всё просто, но сейчас надо осознать одну важную вещь: некоторые возможные ситуации были посчитаны несколько раз. В самом деле, случай, когда первый и второй участники одновременно получили свои подарки, учтён дважды (в первой и во второй сумме). Поэтому для получения правильного ответа необходимо из нашего результата Y1=N! один раз вычесть дважды учтённые расклады (для парных совпадений). Более того, в этот Y1=N! случаев трижды включены расклады, в которых первый, второй и третий участники одновременно получили свои подарки на руки. Такие случаи тройных совпадений надо вычесть дважды (чтобы осталось ровно одно). Дальше аналогично: четвёрки посчитаны по четыре раза, их надо вычесть трижды, пятёрки посчитаны пять раз - их надо вычесть четыре раза. И так далее. Звучит сложно, но мы вот-вот доберёмся до результата.

Давайте разберём случай, в котором двое участников получили свои подарки на руки. Оставшиеся (N-2) участника, как мы выяснили недавно, могут распределить оставшиеся (N-2) подарка ровно X2=(N-2)! способами. Выходит, надо просуммировать все эти X2 конфигурации для всех возможных пар из N участников. А таких пар может быть ровно N*(N-1)/2! (потому что порядок не имеет значения). Выходит, что таких конфигураций ровно N*(N-1)/2 * X2, что как раз равно Y2=N!/2.

Опять важно отметить, что мы несколько раз посчитали одинаковые конфигурации: например, случай, когда первый, второй и третий участники одновременно получили свои подарки, учтён 3 раза. Поэтому для получения правильного ответа из нашего результата Y2=N!/2 необходимо два раза вычесть трижды учтённые расклады. Аналогично - для четвёрок, пятёрок и так далее.

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

Соберём получившийся «хаос»: заметим, что выражение T(N)=Y1-(Y2-(Y3-(Y4-(Y5-...)))) нам очень удобно. Оно как раз обладает замечательным свойством: многократно учтённые случаи благополучно вычитаются нужное количество раз, поэтому все возможные расклады остаются в количестве ровно одной штуки (надо посмотреть на эту строчку несколько десятков секунд, чтобы почувствовать это). Другими словами, T(N) - это как раз и есть идеальный ответ. T(N) - это количество ситуаций без повторов, в которых хотя бы один участник получил свой подарок обратно. Если из общего количества возможных раскладов N! вычесть T(N), то мы получим количество случаев, в которых никто не получил свой подарок обратно.

Подставим Yi в формулу и раскроем скобки: выходит T(N)=N!-(N!/2!-(N!/3!-(N!/4!-...)))=N!-N!/2!+N!/3!-N!/4!+N!/5!-...-(-1)^N.

Теперь найдём Z(N) - количество ситуаций, в которых каждый получил чужой подарок: Z(N)=N!-T(N)=N!/2!-N!/3!+N!/4!-N!/5!+...+(-1)^N.

Ну а теперь найдём P(N) - вероятность того, что никто не получит свой подарок обратно. Для этого надо разделить количество интересных нам элементарных исходов на количество всех возможных элементарных исходов N!.

P(N)=Z(N)/N! = 1/2! - 1/3! + 1/4! - 1/5! + ... + (-1)^N/N!.

Уф-ф... Длинно вышло. Поздравляю всех дочитавших до этого места :)
Если хотите предложить более короткое и ясное решение, то это будет очень интересно! Приглашаю в комментарии к заметке, посвящённой задачке о подарках. Вопросы о данном решении, пожалуйста, задавайте там же.

Ну а тот факт, что P(N) стремится к 1/e при N стремящемся к бесконечности, легко понять, так как разложение в ряд Тейлора функции экспонента как раз совпадает с P(N) при параметре -1 (exp(-1)=Sum{k=0..inf}(-1)^k/k!). Интересно вот что: P(N) стремится к 1/e очень быстро. Уже для семи участников P(N) приблизительно равно 0.3679 (то есть, совпадает с 1/e с точностью до четырёх знаков после запятой). Мне кажется, это вообще очень важно осознать: если вероятность каждого конкретного события всего лишь 1/N, но этих событий N штук, то вероятность того, что хотя бы одно произойдёт, получается около 2/3. То есть, хотя бы одно событие скорее произойдёт, чем ничего не произойдёт.

Если вам эта тема показалось такой интересной, что хочется прочитать ещё что-то, то рекомендую поискать статьи с распределением Пуассона в главной роли (сейчас мы рассматривали распределение с параметром λ=1). Оно известно человечеству с 1837 года - тогда Симеон Денис Пуассон издал книгу со своими размышлениями о различных последовательностях испытаний Бернулли. В то время эти исследования не нашли себе применения, но после 1894 года распределение Пуассона пригодилось при изучении одного странного феномена: германская армия анализировала статистику трагических случаев, когда солдат был убит ударом копыта. Согласно наблюдениям, 196 солдат погибли таким образом за 280 наблюдений (20 лет умножить на 14 кавалерийских корпусов). Это значит, что можно ожидать, что события будут подчинены распределению Пуассона с параметром λ=0.7. Другими словами, должно было быть 139 случаев без смерти участника, 97 наблюдений с одной смертью, 34 наблюдения с двумя смертями и так далее. Реальность оказалось такой: 140 случаев без жертв, в 91 случае был один убытый копытом, в 32 случаях - двое. Реальные наблюдения очень хорошо совпали с теоретическими размышлениями, что очень поддержало теоретиков, хотя солдат, конечно, жалко.

В реальной жизни мы сталкиваемся с распределением Пуассона почти везде. Например, если N - количество доступных телефонных линий, то число занятых линий приблизительно подчинено распределению Пуассона. Это распределение всюду вокруг нас, поэтому бывает полезно примерно понимать его природу :)

Напишите, пожалуйста, свой ответ о женатых иностранцах и замужних иностранках в комментариях, если ещё этого не сделали.

Хорошей вам недели!

57 комментариев:

  1. Я уже видел эту задачку и решил её, поэтому знаю ответ. Интересно что скажут другие. =)

    ОтветитьУдалить
  2. Мало данных для точного ответа

    ОтветитьУдалить
  3. мало данных для точного ответа.
    хотя "Х женат но любит У" может означать что У не жена и тогда ответ нет

    ОтветитьУдалить
  4. хотя если подумать то ответ "да, это так"

    ОтветитьУдалить
  5. Мысль первая - "мало данных".

    После небольшого размышления - "да, это так".

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

    ОтветитьУдалить
  6. Мой ответ довольно очевидный, что настораживает. Но других вариантов не вижу - таки пишу его:
    в браке явным образом не состоит только Джордж. Его любит Анна. Следовательно, для ответа на вопрос надо установить, замужем ли Анна. Но данных на этот счёт нет - известно только, что Анну любит Джек. но на ком женат Джек - загадка.
    Итого, у меня получается - "данных недостаточно".

    ОтветитьУдалить
  7. Очевидный ответ традиционно (для этого места.-) оказался неверным, SL, спасибо за разъяснения!

    ОтветитьУдалить
  8. мало данных, т.к. неизвестно, состоит ли в браке анна

    ОтветитьУдалить
  9. «Мало данных для точного ответа», возможно Анна замужем.

    ОтветитьУдалить
  10. Анонимный09.11.2009, 10:48

    Нам дано:
    Джек — женат
    Анна — не известно
    Джордж — не женат

    Джек любит Анну
    Анна любит Джорджа

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

    Если Анна состоит в браке, то замужняя Анна любит не женатого Джорджа. Следовательно, и для этого случая утверждение верно.

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

    ОтветитьУдалить
  11. Вопрос можно понимать двояко:
    1)Верно ли, что какой-либо человек, состоящий в браке ...
    2)Верно ли, что всякий человек, состоящий в браке...

    В первом случае ответ, как это подробно расписала r-i-zhaya, «Да, это так».
    Во втором - «Нет, это не так», очевидно.

    ОтветитьУдалить
  12. Анонимный09.11.2009, 11:31

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

    ОтветитьУдалить
  13. chester, кстати вначале как раз хотел ответить «Нет, это не так», но потом всё же решил, что вопрос подразумевает квантор существования.

    Думаю, что в ответах к тесту значится «Да, это так», хотя с учётом неоднозначности вопроса правильным получается «Мало данных для точного ответа».

    ОтветитьУдалить
  14. Нет это не так. Зачем замуж выходить, если любить другого?

    ОтветитьУдалить
  15. Анонимный09.11.2009, 12:49

    Мало данных для точного ответа.

    ОтветитьУдалить
  16. Анонимный09.11.2009, 12:56

    «Мало данных для точного ответа»
    Джек состоит в браке и любит Анну, про которую неизвестно состоит ли она в браке или нет. Джорджа, не состоящего в браке...
    Чорт! Стопудово "Да". Если Анна не состоит в браке, то Джек ее любит и это то что нужно. Если она состоит в браке, то любит Джорджа, который холост, и это опять то что нужно.
    Невнимательность - вторая тяжелая "болезнь" после лени. =)

    ОтветитьУдалить
  17. Этот комментарий был удален автором.

    ОтветитьУдалить
  18. Из условия задачи следует, что

    женат\замужем любит
    Джек T Анну
    Анна T\F Джордж
    Джордж F Анна\не Анна

    где T-означает true-верно, F-означает false-не верно. Также молчаливо предполагается только гетеросексуальные пары.

    Видно, что из условий задачи возможно 4 различных ситуаций, т.е. на первый взгляд, инофрмации недостаточно. Но рассмотрев все 4 ситуации мы обнаружим, что в каждой из ней существует требуемая пара, поэтому ответ - "да, это так".

    ОтветитьУдалить
  19. Сначала думал, что данных мало. Потом начал делать предположения насчёт Анны и "да, утверждение верно"

    ОтветитьУдалить
  20. Анонимный09.11.2009, 21:16

    Ответ «да», если в вопросе подразумевается квантор существования, но т.к. подразумевается он весьма неочевидно, то я вижу скорее квантор общности и ответ «недостаточно данных»:
    ― если Анна окажется замужем, то ответ будет «нет»,
    ― если Анна окажется не замужем, то ответ будет «да».

    Лучше сказать так: недостаточно данных, чтобы понять сам вопрос.

    ОтветитьУдалить
  21. Анонимный09.11.2009, 22:31

    Мало данных для точного ответа

    ОтветитьУдалить
  22. Сначала решил, что мало данных, но перед тем как ответить ещё раз проверил, и оказалось, что да, это так. )

    ОтветитьУдалить
  23. конечно это так. данных совершенно достаточно :))

    ОтветитьУдалить
  24. Да, это так - в любом из двух возможных вариантов утверждение будет верно.
    С подарками - получается, я был на правильном пути, но затормозил на том, как сосчитать варианты с несколькими несчастливцами.

    ОтветитьУдалить
  25. Анонимный10.11.2009, 13:47

    Илья, у нас тут спор возник с человеком, который не захотел решать задачу логическим путем. Сказал, что верно с вероятностью 50%, и был таков. Какая вероятность у ответа "Да, верно", почему и является ли это решением?

    ОтветитьУдалить
  26. maximalsit-zzz, в Вашем комментарии выше приведено полное решение.

    Если оппонент не интересуется логическими аргументами, то и понятие правильного ответа не имеет для него смысла - во что хочет, в то и верит. Для исправления ситуации можно предложить другие задачи, в которых интуиция подсказывает одно, а трезвые вычисления - другое. Тогда, возможно, человек поймёт, что в некоторых случаях надо думать, а не только чувствовать.

    chester, увы, я допустил эту неточность в формулировке :(
    Благо, большинство комментаторов поняло, что речь идёт о существовании... Надо будет запомнить этот момент, чтобы в будущем не порождать такой путаницы. Спасибо, что пояснили!

    ОтветитьУдалить
  27. Анонимный10.11.2009, 15:14

    Нет, вы не поняли. Да, он не захотел лезть в логику, но он полез в теорию вероятности и посчитал, что "Верно с вероятностью 50%". Он сказал, что для него это решение и что каждый из нас по своему прав. Вот я и задал эти вопросы. Вопросы у меня все те же, можете ли ответить теперь?

    ОтветитьУдалить
  28. maximalsit-zzz, да, теперь я совсем ничего не понял.

    Судя по Вашему первому комментарию, Вы понимаете эту задачу, прочувствовали её тонкости и смогли решить. Рассуждения так ясны и прозрачны, что Вы должны быть уверены в них.

    Но другой человек что-то неправильно посчитал или ошибся с применением какого-то метода. Или даже неправильно понял условие. И он не объясняет, как именно получен его результат.

    Верно ли я понял, что Вы спрашиваете, кто из вас прав? Да какая разница, что я думаю?! Если решение верно, то оно верно при любом моём мнении. И выше я уже один раз подтверждал, что считаю Ваше решение правильным. Что я ещё могу добавить?

    Или я не понял Ваш вопрос?

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

    ОтветитьУдалить
  29. Анонимный10.11.2009, 15:51

    Мало данных! Буду читать дальше.

    ОтветитьУдалить
  30. Есть предположение, что 50% возникли из того, что пары 2 (Джек-Анна и Анна-Джордж), но утверждение верно только для одной из них.

    ОтветитьУдалить
  31. Мало данных.

    Неизвестно, состоит ли в браке Анна.

    ОтветитьУдалить
  32. Про применение Пуассона (или, в непрерывности - Гаусса, если я правильно помню) нам хорошо рассказали на первом курсе ФизФака. Нормальное распределение (По горизонтали - количество денег на человека, по вертикали - доля в населении) должно быть в стране по деньгам для того, что бы в стране была стабильность. Отсюда сразу вытекает что такое средний класс - это те, кто находится под (высота горки)/sqrt(2), вытекает, что если государство не обладает таким распределением - то оно нестабильно (СССР, например, это было плато с узким пиком в области "все есть"). И т.д.

    "Идею - дарю" (с)

    ОтветитьУдалить
  33. Анонимный11.11.2009, 00:19

    Вопрос задан некорректно.
    Читаем:
    "Женатый Джек любит Анну, которая влюблена в холостого Джорджа. Верно ли, что есть состоящий в браке человек, который любит ТОГО, кто в браке не состоит?"
    Русский язык под словом "ТОГО" может подразумевать лицо мужского рода.
    Если, я буду под словом "ТОГО" подразумевать только МУЖЧИНУ, а не человека вообще (а мне ничто не мешает это делать и нельзя меня счесть не правым в такой ситуации, ибо сама постановка вопроса дает мне пространство, в том числе и для такого его толкования), то ответ будет НЕТ, поскольку в ситуации, когда Анна не замужем, женатый Джек любит ТУ- то есть лицо женского рода. И поэтому ответ нет, так как не всегда есть человек который любит ТОГО (лицо мужского рода), кто в браке не состоит.

    Правильная и исчерпывающая постановка вопроса не дающая никаких оснований для дачи иного ответа, кроме как ответ "ДА":

    "Женатый Джек любит Анну, которая влюблена в холостого Джорджа. Верно ли, что из данных трех людей есть состоящий в браке человек, любящий ЧЕЛОВЕКА, который в браке не состоит?"

    Только при подобной постановке вопроса ответ ВСЕГДА будет ДА.

    Вопрос (по крайней мере на русском языке) приведенный в задаче в том виде, в котором он приведен дает отвечающему возможность задать дополнительный вопрос (Вопрос типа: “Извините, а можно уточнить: под словом ТОГО подразумевается МУЖЧИНА или ЧЕЛОВЕК вообще, то есть безотносительно его пола?” Ибо от того, что мы будем понимать под словом “ТОГО” зависит наш ответ).

    Далее. Если есть возможность задать такой вопрос, то выходит, что в самом вопросе для ОДНОЗНАЧНОГО ответа данных, увы, НЕДОСТАТОЧНО. И формально ответ – недостаточно. В таком виде в каком задача сформулирована изначально ее нельзя включать в учебники по логике. Как бЕ.

    ОтветитьУдалить
  34. Анна либо в браке, либо нет. В первом случае состоящая в браке Анна любит неженатого Джорджа. Во втором случае женатый Джек любит незамужнюю Анну. Стало быть, ответ - да.

    ОтветитьУдалить
  35. Sergey, спасибо за мысль, я подумаю.

    Уважаемый аноним, благодарю за подробный разбор и советы.

    Отмечу только, что докопаться всегда можно. Например, на одном форуме, где я публиковал эту задачу, были критики, интересующиеся следующим:
    1) Является ли женщина человеком?
    2) Слова "любит" и "влюблён" означают одно понятие или разное.
    И Ваша формулировка, увы, тоже не выдерживает таких вопросов.

    Моя позиция такая:
    1) Путаница с "утверждение верно всегда" или "верно хотя бы раз" в вопросе есть, поэтому данный момент надо исправить (выше я уже это писал).
    2) "Того" в русском языке может означать мужской род или слово неизвестного рода. Если ребёнку говорят "покажи рукой на того, кого ты больше любишь", то призывают выбрать между матерью и отцом (зачем-то), а не указать на отца, так ведь?
    3) Правильная и исчерпывающая постановка вопроса является длинной (потому что вместо "женщина" в ней "человек женского рода", а вместо "влюблён" - "находится в состоянии любви" и так далее). И очень трудно доказать её полную корректность. Вдруг ещё кто-то что-то не поймёт? Ах, да, ещё необходимо упомянуть, что Анна, Джордж и Джек - имена разных людей, а не одного (и такой вопрос мне задавали!). И что человек не может одновременно состоять в браке и не состоять.

    Для меня была важна краткость формулировки, чтобы она не отпугивала читателей. И нынешняя версия показала, что большинство справляется с пониманием условия. Главная проблема - отсутствие указания на существование человека, но и с ней большинство справилось.

    Ещё раз спасибо за Ваши замечания!

    ОтветитьУдалить
  36. Анонимный14.11.2009, 20:23

    Да, это так.

    ОтветитьУдалить
  37. Причем здесь человек женского пола? Рассуждения выдерживают даже предположение, что Анна - мужчина, негетеросексуальные браки и множественность браков.

    ОтветитьУдалить
  38. Анонимный09.07.2010, 18:28

    мало данных. мы не знаем статуса Анны

    ОтветитьУдалить
  39. Анонимный14.04.2011, 21:06

    Да, знал эту задачу. По-моему формулировка на английском более лаконична.

    ОтветитьУдалить
  40. Анонимный05.11.2011, 13:56

    Тут же очевидно все.Предполагаем 2 варианта и в обоих наше утверждение истинно.

    ОтветитьУдалить
  41. Ответ один – Да, это так!

    Вижу путаницу у многих при решении и попытаюсь написать в более простой разбивке ситуации.
    Решение данной задачи, логичнее объяснять, не основываясь на этику и грамматику, приведенного примера. А перевезти в разряд аббревиатур. После чего задача станет похожа на схему или алгоритм на начальном этапе программирования.
    И так:
    Задача с одной переменной. Где Анна: или Да(в браке) или Нет (не в браке).
    Значит, условие задачи выглядит только в последовательности с права налево и зависит от двух вариантов Анны (Да или Нет):
    1. ДА (Джек в браке) >Да (Анна в браке) > Нет (Джордж не в браке).
    2. ДА (Джек в браке) >Нет (Анна НЕ в браке) > Нет (Джордж не в браке).
    Вопрос - Верно ли, что человек(м/ж), состоящий в браке(Да, в браке), любит человека (м/ж), в браке не состоящего(Нет, не в браке)?
    Ситуация изложенный в двух вариантах показывает нужное совпадение
    Да, в браке> Нет, не в браке.
    в варианте 1 на этапе Да (Анна в браке) > Нет (Джордж не в браке).
    И варианте 2 ДА (Джек в браке) >Нет (Анна НЕ в браке), т.е в обоих случаях.
    Соответственно ответ один – Да, это так.

    ОтветитьУдалить
  42. Анонимный10.04.2014, 03:39

    Да, если Анна не замужем, то это ее любит женатый, если же она замужем, то, выходит, тогда она, состоящая в браке, любит холостого. С семейным положением остальных участников все очевидно из условия. НО - если только в оригинальном тексте "человек" был обозначен как "person", а не "man". К чему-то ведь все-таки "иностранцы" были помянуты, причем имена явно из англоязычных стран... (Ответ не читал, задачка раньше не попадалась)

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний