Летопись: 10 мая 2010

69-е заседание клуба "Эратосфен", 14 мая в 16 часов. "Алгоритмические" задачи - 2.

...Два с половиной года назад на своем 43-м заседании мы уже обсуждали решение замечательных "алгоритмических" задач, вызвавших тогда большой интерес гимназистов и выпускников. (Тексты старых задач можно посмотреть на сайте гимназии в "Летописи" от 16 ноября 2007 года.) За прошедшее время наша коллекция пополнилась новыми, не менее замечательными задачами... О своем решении некоторых из них расскажет
Александра Михайлова, 11 альфа.

1. Задача про город математиков. В некотором городе жили только математики со своими женами. Жены, понятное дело, склонны к измене. Каждый математик знает всё про чужих жен и ничего не знает про свою. Но если он каким-то образом догадается, что его жена ему изменяет, то в ближайшую ночь он ее убьет. Однажды в город явился странник и сказал математикам: "В вашем городе измена!". После этого за n ночей произошло m убийств. Спрашивается, как связаны между собой числа n и m?
2. Задача про подарки. Бильбо Беггинс устроил праздник и пригласил на него 100 хоббитов. Каждому хоббиту он приготовил свой подарок и подписал его. Затем он взял 100 коробок с именами приглашенных хоббитов и чисто случайным образом разложил подарки по коробкам. Бильбо собрал гостей и сказал: "В этой закрытой комнате лежат для вас подарки. Каждый из вас по очереди будет заходить в комнату, сможет раскрыть ровно половину (т.е. 50) коробок и посмотреть на их содержимое. Я буду следить за тем, чтобы вы ничего в коробках не трогали и их после себя закрывали. Затем вы будете выходить через другую дверь, и до конца игры не сможете общаться с остальными хоббитами. Если каждый из вас увидит в одной из открытых коробок свой подарок, то после окончания процедуры все вы получите ваши подарки. Но если хотя бы один из вас своего подарка не обнаружит, то никто ничего не получит." <Вряд ли такая перспектива обрадовала гостей, но хоббиты очень любят подарки, и игра началась...> Как должны поступить гости, чтобы с наибольшей вероятностью получить свои подарки? Какова будет эта вероятность?
3. Парадокс Монти Холла (игровая версия от А.Михайловой). Есть три закрытых двери, за одной из которых ведущий поместил автомобиль, а за двумя другими - по козе. Играющий получит то, что находится за угаданной им дверью. Сначала играющий выбирает одну из трех дверей и стучит в нее. После этого ведущий открывает одну из двух оставшихся дверей и показывает игроку, что за ней находится коза. Затем игрок может либо изменить свой выбор и указать на третью дверь, либо подтвердить первоначальные намерения. Как поступить игроку, чтобы вероятность выиграть автомобиль увеличилась? Какова будет эта вероятность?

...Если Вы знаете решение, то приходите и оппонируйте докладчице!
...Если Вы знаете только ответ, то приходите и узнаете много интересного!
...Если Вы ничего не знаете, то приходите, чтобы узнать хоть что-нибудь...

?