Три задачки
Sep. 13th, 2013 08:10 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mathclimberиз моих любимых:
1. Бросаем случайным образом 4 точки на сферу. Какова вероятность, что центр сферы попадёт внутрь тетраэдра с вершинами в этих точках?
2. На плоскости нарисована клякса площадью меньше единицы. Доказать, что её можно сдвинуть так, что она не будет закрывать ни одну точку с целыми координатами.
3. В стране Анчурии проходит математический конгресс, в котором принимают участие 100 математиков. За несколько дней до окончания конгресса в оной стране происходит переворот и военная хунта захватывает власть. Глава хунты, полковник Фидель Аугусто Чавес, приказывает всех математиков арестовать. Но полковник, в сущности, добрейшей души человек. Вот он приходит в тюрьму к математикам, и говорит такую речь:
"Мы тут, разумеется, решили вас всех расстрелять. Но я хочу дать вам шанс. В соседней комнате лежит 100 карточек. На одной стороне у них числа от 1 до 100, а на обратной - ваши имена. Вы будете по одному заходить в комнату, где карточки будут лежать числами вверх. Каждый может перевернуть 95 карточек. Если каждый из вас, переворачивая карточки, найдет свое собственное имя - тогда всех прикажу отпустить. А вот если хоть один не найдет - тогда уж всех расстреляют..."
Оцените шансы того, что для математиков все кончится хорошо.
Поясню условие последней задачи: на каждой карточке только одно имя и только одно число, числа и имена не повторяются. Каждый проходит через комнату с карточками один и только один раз. Перед началом процесса математики могут между собой договориться о чем угодно, но тот, кто уже прошел через комнату, не может передать никакой информации остальным (и, перед тем как зайдет следующий, карточки переворачивают обратно числами вверх). Естественно, карточки непрозрачны, и на них ничего рисовать нельзя. Менять их расположение тоже смысла нет - все равно к приходу следующего все перемешают.
Все можно решить в уме, даже первую, хоть она и была типа самой сложной задачей на какой-то международной олимпиаде. В третьей главное стратегию придумать, и сразу станет ясно, что шансы не так плохи, как кажется.
Это я прочитал http://avva.livejournal.com/2672659.html, и тоже решил поделиться :)
1. Бросаем случайным образом 4 точки на сферу. Какова вероятность, что центр сферы попадёт внутрь тетраэдра с вершинами в этих точках?
2. На плоскости нарисована клякса площадью меньше единицы. Доказать, что её можно сдвинуть так, что она не будет закрывать ни одну точку с целыми координатами.
3. В стране Анчурии проходит математический конгресс, в котором принимают участие 100 математиков. За несколько дней до окончания конгресса в оной стране происходит переворот и военная хунта захватывает власть. Глава хунты, полковник Фидель Аугусто Чавес, приказывает всех математиков арестовать. Но полковник, в сущности, добрейшей души человек. Вот он приходит в тюрьму к математикам, и говорит такую речь:
"Мы тут, разумеется, решили вас всех расстрелять. Но я хочу дать вам шанс. В соседней комнате лежит 100 карточек. На одной стороне у них числа от 1 до 100, а на обратной - ваши имена. Вы будете по одному заходить в комнату, где карточки будут лежать числами вверх. Каждый может перевернуть 95 карточек. Если каждый из вас, переворачивая карточки, найдет свое собственное имя - тогда всех прикажу отпустить. А вот если хоть один не найдет - тогда уж всех расстреляют..."
Оцените шансы того, что для математиков все кончится хорошо.
Поясню условие последней задачи: на каждой карточке только одно имя и только одно число, числа и имена не повторяются. Каждый проходит через комнату с карточками один и только один раз. Перед началом процесса математики могут между собой договориться о чем угодно, но тот, кто уже прошел через комнату, не может передать никакой информации остальным (и, перед тем как зайдет следующий, карточки переворачивают обратно числами вверх). Естественно, карточки непрозрачны, и на них ничего рисовать нельзя. Менять их расположение тоже смысла нет - все равно к приходу следующего все перемешают.
Все можно решить в уме, даже первую, хоть она и была типа самой сложной задачей на какой-то международной олимпиаде. В третьей главное стратегию придумать, и сразу станет ясно, что шансы не так плохи, как кажется.
Это я прочитал http://avva.livejournal.com/2672659.html, и тоже решил поделиться :)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-09-14 10:16 am (UTC)no subject
Date: 2013-09-14 11:17 am (UTC)no subject
Date: 2013-09-14 11:25 am (UTC)no subject
Date: 2013-09-14 11:28 am (UTC)На самом деле, там может быть любое измеримое множество с мерой < 1, но зачем людей пугать?..
no subject
Date: 2013-09-14 11:42 am (UTC)no subject
Date: 2013-09-14 11:49 am (UTC)no subject
Date: 2013-09-14 04:24 pm (UTC)Ниже решение.
Я попробовал написать белым по белому. Видно? ;)
no subject
Date: 2013-09-14 04:39 pm (UTC)no subject
Date: 2013-09-14 05:55 pm (UTC)Вот.
no subject
Date: 2013-09-14 08:11 pm (UTC)Что написано молоком на полях - я сейчас не вижу (смартфон не показывает). Завтра посмотрю.
no subject
Date: 2013-09-14 08:18 pm (UTC)Вот. На Ваши задачки никакой шоколадки не хватит!
no subject
Date: 2013-09-14 10:39 pm (UTC)no subject
Date: 2013-09-15 02:04 am (UTC)Сейчас подумаю. Насколько это возможно после хеви-металлического концерта и пива :)
no subject
Date: 2013-09-15 07:30 am (UTC)Можно ещё найти пример такого n, для которого задача с n точками и n монетами имеет отрицательное решение.
Эту задачу придумал какой-то японский дизайнер в 2008 году :)
no subject
Date: 2013-09-15 04:24 pm (UTC)no subject
Date: 2013-09-15 04:31 pm (UTC)Во-первых, военные конфисковали их паспорта, и знают, кого как зовут. Во-вторых, даже если бы и не знали, оцените вероятность того, что хоть один не найдёт карточку с нужным номером. В третьих, чем это вообще отличается от "наивно-честной" стратегии (искать самого себя)?
no subject
Date: 2013-09-15 04:33 pm (UTC)Только можно эту задачу решить вообще без всяких интегралов, матожиданий, и прочего. :)
no subject
Date: 2013-09-16 02:51 am (UTC)no subject
Date: 2013-09-16 02:52 am (UTC)Отличается тем, что номера карточек всегда видны, а имена - нет.
no subject
Date: 2013-09-16 09:44 am (UTC)no subject
Date: 2013-09-16 12:12 pm (UTC)текст
Вроде, работает?..
no subject
Date: 2013-09-16 12:15 pm (UTC)Я до такого решения додумался далеко не сразу, сначала пришло в голову что-то через формулу полного мат.ожидания, и формулу для площади сферического треугольника (которая сумма углов минус π).
no subject
Date: 2013-09-16 12:17 pm (UTC)no subject
Date: 2013-09-16 12:18 pm (UTC)no subject
Date: 2013-09-16 12:21 pm (UTC)Я третью задачу как-то раз в конце семестра дал своей группе по верояти, с наказом "решите - контрольная будет лёгкая, не решите - будет всем цугундер". И ведь решили! "Жить захочешь - еще не так раскорячишься" (с)
no subject
Date: 2013-09-16 12:46 pm (UTC)Люблю такие задачки. Но чувствуется, что "давно не брал я в руки шашки" :).
Про первую задачку так и хочется дать стандартный ответ: 1/2 либо попадет, либо не попадет ;).
Но после подсказки, что можно решить без интегралов появилась идея подобной же сложности:
Бросаем случайным образом на сферу для начала 3 точки, пусть будут а, б и с и проецируем их через центр о на противоположную сторону сферы: а", б" и с". Если рассмотреть точки а, б, о, а" и б", то очевидно, что они лежат на плоскости большого круга точно также как группы точкек б, с, б", с" и с, а, с", а". Таким образом получили сферический треугольник а"б"с". Для того, чтобы центр сферы оказался внутри тетраэдра абсд необходимо и достаточно, чтобы вершина д лежала внутри сферического треугольника а"б"с". Три больших круга делят сферу на восемь сферических треугольников, значит вероятность того, что точка д попадет в один такой конкретный сферический треугольник - 1/8.
Про кляксу тоже без формул?
no subject
Date: 2013-09-16 12:49 pm (UTC)no subject
Date: 2013-09-16 01:03 pm (UTC)no subject
Date: 2013-09-16 05:36 pm (UTC)Если после первого сдвига кляксы оказалась покрыта другая целая точка, то сдвиг (-x1, -y1) не годится. Найдем новый сдвиг.
Построим суммарный сдвиг (-x1-x2, -y1-y2) и возьмем от него целую часть по каждой координате.
И так далее. Хоть до бесконечности.
Получим _счетное_ множество "не годящихся" сдвигов (т.к. множество точек с целыми координатами счетное). А в квадрате (-0.5,+0.5)х(-0.5,+0.5) континуум точек. Значит, какая-то из них не является "не годящейся".
Так годится?
no subject
Date: 2013-09-16 05:52 pm (UTC)ИМХО, в этом решении не хватает фразы о случайном равномерном выборе одного из восьми треугольников.
Наверно так?
no subject
Date: 2013-09-16 08:26 pm (UTC)Кроме того, при таком подходе, непонятно почему следующая итерация не может "испортить" то, чего мы добились на предыдущих этапах.
no subject
Date: 2013-09-16 08:32 pm (UTC)no subject
Date: 2013-09-17 09:53 am (UTC)no subject
Date: 2013-09-17 10:04 am (UTC)no subject
Date: 2013-09-17 11:38 am (UTC)no subject
Date: 2013-09-17 11:40 am (UTC)no subject
Date: 2013-09-17 12:35 pm (UTC)no subject
Date: 2013-09-17 10:39 pm (UTC)no subject
Date: 2013-09-19 09:47 pm (UTC)А что за фокус?
no subject
Date: 2013-09-19 11:33 pm (UTC)а) математиков жалко;
б) когда можно открывать 95, с вероятностью 0,91 уже самый первый математик выйдет из комнаты будучи абсолютно уверенным, что спасутся все!
Фокус, я думаю, такой. Фокусник предлагает группе человек из 10 вытащить по одной карте из колоды, и запомнить её. (Или, скажем, записать имя какого-нибудь знаменитого человека на бумажке, не суть важно.) Затем эти карты кладутся на стол рядом с фокусником, рубашкой вверх. Фокусник говорит, что сейчас эти карты назовёт, одну за другой. Вот он водит рукой над первой картой, говорит "дама пик!", переворачивает карту, не показывая её зрителям, ругается, говорит, что звёзды не так сошлись, и угадать не удалось. Зато все остальные карты он "угадывает" верно. Просто называя предыдущую открытую им карту :)
no subject
Date: 2013-09-19 11:37 pm (UTC)Все математики должны пронумероваться, и каждый перед заходом в комнату берёт с собой список соответствия номеров и имен. Дальше, первым делом надо открыть карточку, с номером, соответствующим собственному имени в списке (составленном самими математиками). Взяв первую карточку, обнаружим с другой стороны одно из имен и, подсмотрев в свой список соответствия, берём следующим именно то число, которое соответствует открывшемуся имени. И так далее, по цепочке. Пока цикл не замкнётся; но в момент, когда он замкнётся, математик откроет карточку с собственным именем!
Нетрудно видеть, что вероятность успеха получается 1 - 1/100 - 1/99 - 1/98 - 1/97 - 1/96 (т.е. вероятность, что случайная перестановка не имеет циклов длины 100, 99, 98, 97, 96). В общем, неплохие у них шансы :)
no subject
Date: 2013-09-23 03:30 pm (UTC)Ведущий перед зрителем раскладывает веером колоду, рубашкой вверх. Просит зрителя показать, например, десятку пик (карты произвольные и каждый раз разные). Зритель показывает на карту пальцем, ведущий забирает ее себе в руку. Затем ведущий просит показать еще какую-нибудь карту, например, семерку треф, зритель показывает, ведущий забирает в руку. Дальше ведущий говорит "Ну а короля червей я покажу сам" и забирает в руку еще одну карту. Затем ведущий вскрывает руку, и там оказывается правильный набор.
Как ему это удалось? Перед тем, как разложить колоду, во время перемешивания, ведущий запоминает одну из карт (десятка пик) и ее местоположение. Проще всего подсмотреть самую нижнюю карту, но при определенной ловкости можно запомнить и карту из середины колоды. А дальше понятно.
Разница в том, что тут цикл действительно замыкается, нету такого, что "звезды не так сошлись". Думаю, что Ваш фокус я бы раскусил сразу, о вот описанный выше, когда мне его показывали, я сразу не раскусил :)
no subject
Date: 2013-09-23 11:13 pm (UTC)no subject
Date: 2013-09-29 05:05 am (UTC)no subject
Date: 2013-09-29 11:29 am (UTC)no subject
Date: 2014-12-08 07:17 pm (UTC)no subject
Date: 2014-12-08 07:58 pm (UTC)