tag:blogger.com,1999:blog-6846929136376245264.post101039618969752142..comments2024-01-03T12:54:39.457+03:00Comments on Привычка не думать: Остров БеззеркальяИлья Весеннийhttp://www.blogger.com/profile/12075968879288943233noreply@blogger.comBlogger59125tag:blogger.com,1999:blog-6846929136376245264.post-67941425539736956552010-12-29T08:31:03.510+03:002010-12-29T08:31:03.510+03:00Уважаемый аноним, Вы повторили этот вопрос в комме...Уважаемый аноним, Вы повторили этот вопрос в комментариях к следующей заметке, поэтому я опубликовал ответ именно там (<a href="http://my-tribune.blogspot.com/2010/01/blog-post_20.html?showComment=1293600604107#c57260087112868480" rel="nofollow">ссылка</a>).Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-91099073018245817952010-12-28T13:49:41.398+03:002010-12-28T13:49:41.398+03:00Илья, я в вас разочарован :) Первоначальный пост н...Илья, я в вас разочарован :) Первоначальный пост не содержал никакого решения, подло и изподтяжка подталкивал к придумыванию сложного и НЕПРАВИЛЬНОГО решения через матиндукцию, хотя ответ был очевиден. Ну это как если бы вы спросили сколько будет 2х2? и что-то туманно намекнули про комплексные числа (с их помощью можно "доказать", что будет 5) и про то, что кто-то счтитает как-то хитро, не дав ни "ответа", ни "решения". Это не ваш уровень :) В этом посте уже лучше, но тоже как-то слабо и неинтересно. <br /><br />По поводу задачи: жители - тупые компьютеры, любой алгоритм - это переработка входной информации в выходную и для применения матиндукции вы должны были бы доказать, что на каждом шаге индукции ничего не меняется во входной информации, кроме k. Могу на пальцах показать, что ситуации с k=1 и k>1 не имеют ничего общего. <br /><br />Вот вам упрощенная формулировка этой задачи: есть большое число N жителей острова. Каждый житель сегодня покончит с собой в предощущении одиночества, если будет уверен, что завтра останется 1. "Ответ": все жители покончат с собой в один день. Можно ввести какого-нибудь туриста для отвода глаз, который ничего не делает, чтобы читатели не задумывались в КАКОЙ день? Для N=1 решение очевидно. Допустим, что решение верно для k жителей, тогда оно верно для k+1 жителей, поскольку k+1 будет точно знать, что завтра останется 1. Так можно доказать все, что угодно.<br /><br />Alex.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-19592633187052414672010-02-05T10:37:03.162+03:002010-02-05T10:37:03.162+03:00Vika Moo, предлагаю обсудить эту задачку с друзьям...<b>Vika Moo</b>, предлагаю обсудить эту задачку с друзьями, это способствует пониманию. И рекомендую прочитать <a href="http://my-tribune.blogspot.com/2010/01/blog-post_20.html" rel="nofollow">комментарии к следующей заметке</a>, там всё разобрано.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-21894839285222053902010-02-04T13:25:50.907+03:002010-02-04T13:25:50.907+03:00Уфф, прочитала 2 раза и ничего не понялаУфф, прочитала 2 раза и ничего не понялаVika Moohttp://domikmeda.runoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-50150142172030406512010-01-21T06:45:44.194+03:002010-01-21T06:45:44.194+03:00Предлагаю продолжить обсуждение этой задачи в след...<b>Предлагаю продолжить обсуждение этой задачи <a href="http://my-tribune.blogspot.com/2010/01/blog-post_20.html" rel="nofollow">в следующей заметке</a>.</b>Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-9823438167717092632010-01-20T23:17:55.501+03:002010-01-20T23:17:55.501+03:00Хотя возможен такой вариант: все парные и уникальн...Хотя возможен такой вариант: все парные и уникальные собираются и тот, кто видит два цвета по одному уходит — остаётся группа с парным цветом, потом снова все собираются пока никто не станет уходить. Оставшиеся имеют уникальный цвет и остаются.Unknownhttps://www.blogger.com/profile/16629768333108482295noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-6777378986737934462010-01-20T23:13:19.322+03:002010-01-20T23:13:19.322+03:00В общем, никто не должен видеть всего один цвет, е...В общем, никто не должен видеть всего один цвет, если это не названный. Если всё-таки такой есть, то использовать вышеприведённый алгоритм нельзя.Unknownhttps://www.blogger.com/profile/16629768333108482295noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-21360416395584303142010-01-20T23:08:50.064+03:002010-01-20T23:08:50.064+03:00Поправка: у кого есть два парных цвета, т.к. это м...Поправка: у кого есть два парных цвета, т.к. это минимально необходимое количество, чтобы свалить и не должно быть уникальных цветов, кроме названного, а также "близнецов" — т.к. обладатели таких цветов будут думать, что у них цвет из минимально наблюдаемой группы, но подтвердить свою ошибку они не смогут.Unknownhttps://www.blogger.com/profile/16629768333108482295noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-85600518781035968652010-01-20T22:59:24.311+03:002010-01-20T22:59:24.311+03:00Решение для общего случая(!):
Никто не уедет (либ...Решение для общего случая(!):<br /><br />Никто не уедет (либо уедет один, если он единственный, чей цвет был назван), если они должны быть точно уверены в цвете своих глаз (предположим, что пока есть шанс, что они ошибаются в догадках, то они не уезжают, т.к. не хотят), а никто не может быть точно уверенным, если он собрался уезжать один, а заранее известно, что уехать должны более одного человека, т.к. один сразу бы точно знал, что он один и уехал — такое было бы возможно только в случае, если бы ему сообщили, что есть уникальный цвет глаз, которого он не видит, а такого не было.<br /><br />Но вот если достаточно лишь догадываться о цвете своих глаз, то тут логика такая: если у меня цвет глаз, как у группы А, то мы сваливаем через интервал времени в t*x, где x — количество, которое я наблюдаю в группе А. Если в группе А все думают также и я принадлежу группе А, то мы свалим в один день, если я ошибаюсь, то размерность А на один меньше, и один из группы А попробует свалить раньше и вместе с ним свалит вся группа А. Если я не в группе А, а группой А будем считать самую малочисленную группу, то я в группе Б, которая больше группы А, а значит группа А уже свалит в день Х и к тому времени я уже буду знать, что я не в группе А. После того как группы А не станет будем считать группой А группу Б и повторим рассуждение. Если есть две одинаковые группы, каждый будет знать, что он именно из той группы, о которой подумал, т.к. для всех других групп в случае, если бы он им принадлежал день сбора был бы следующим днём. t примем равным самому удобному для подсчёта интервалу времени, который одинаковый для всех. (тут мы основываемся на том, что для человека таких интервалов не будет два — например одинаково удобно считать восходы и заходы солнца, если оба они происходят в период бодрствования всех, причём можно считать только восходы или заходы, либо считать и то и другое, что приводит к рассинхронизации алгоритма и нельзя сказать, что более малочисленная группа уже свалила с острова, а это нужно, чтобы ошибиться и не свалить раньше времени)<br /><br />Как можно заметить тут не имеет значения сколько всего цветов, главное чтобы кто-то дал точку отсчёта. Уедут все, у кого есть парный цвет или его цвет был назван.Unknownhttps://www.blogger.com/profile/16629768333108482295noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-88561623287515059652010-01-20T21:03:33.907+03:002010-01-20T21:03:33.907+03:00Повторю, ошибка заключается в допущении, будто тур...Повторю, ошибка заключается в допущении, будто турист просто сообщил уже известную информацию. Подробнее см. <a href="http://my-tribune.blogspot.com/2010/01/blog-post_19.html?showComment=1263986768671#c4744757172511577140" rel="nofollow">мой пост выше</a>.colognoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-5836560748325032902010-01-20T21:02:26.343+03:002010-01-20T21:02:26.343+03:00"Давайте упростим ситуацию: на острове только..."Давайте упростим ситуацию: на острове только два человека и они голубоглазые. К ним подходит турист и говорит: "Эй, парни, а ведь среди вас есть голубоглазый!". Если рассуждать как в решении по индукции, то оба они на следующий день должны свалить в ад. По-моему, полный бред. Эти двое и раньше знали, что среди них есть голубоглазый."<br /><br />Да они не знали, что другой голубоглазый это знал.Ivan Bendynahttps://www.blogger.com/profile/08613485844830182291noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-40341871965733497332010-01-20T20:59:57.845+03:002010-01-20T20:59:57.845+03:00ААААААААААААА! Я все понял! Важно не то, что турис...ААААААААААААА! Я все понял! Важно не то, что турист им сообщил, а то что все слышали, как он всем это сообщил!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-78033233393933548332010-01-20T20:33:46.630+03:002010-01-20T20:33:46.630+03:00В том и вопрос, где ошибка в этих рассуждениях. Ес...В том и вопрос, где ошибка в этих рассуждениях. Если они верны для такого простого случая, то верны и для большего числа.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-25980097986481258232010-01-20T20:29:14.465+03:002010-01-20T20:29:14.465+03:002 анонимный: как раз с 2 голубоглазыми отъезд об...2 анонимный: как раз с 2 голубоглазыми отъезд обоих уж точно не "полный бред". <br />Если бы один был голубоглазым а другой кареглазым - то голубоглазый бы уехал в первый день. Если он не уехал - значит оба голубоглазые. Других вариантов просто нет.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-44589470050031032732010-01-20T20:04:53.643+03:002010-01-20T20:04:53.643+03:00Давайте упростим ситуацию: на острове только два ч...Давайте упростим ситуацию: на острове только два человека и они голубоглазые. К ним подходит турист и говорит: "Эй, парни, а ведь среди вас есть голубоглазый!". Если рассуждать как в решении по индукции, то оба они на следующий день должны свалить в ад. По-моему, полный бред. Эти двое и раньше знали, что среди них есть голубоглазый.<br />Есть следующая мысль: есть вещи, о которых математики предпочитают не распространяться (типа множества всех множеств), может и здесь что-то подобное, например, нельзя рассуждать о том, как рассуждают другие.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-28075309365426280362010-01-20T19:11:37.039+03:002010-01-20T19:11:37.039+03:00Вобщем решение насчет индукции и уезда на N+- день...Вобщем решение насчет индукции и уезда на N+- день разжевали. Насчет того, что изменил американец - попробую сформулировать - он дал отсчет того дня, когда бы уехал голубоглазый, будь он один. А дальше по индукции. <br />Но можно и другое решение предолжить: если островитяне, как сказано в условии, умны - с одной стороны и не хотят уезжать - с другой, то не уедут в день M, а подождут немного, в надежде что другие тоже умны и поступят так же. В результате, основа для расчета собьется и никто никуда не уедет.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-45566648345762079932010-01-20T18:43:18.391+03:002010-01-20T18:43:18.391+03:00Может быть я торможу, так как мне работать вообще-...Может быть я торможу, так как мне работать вообще-то надо, но пробежав по комментариям я большинство просто не понял.<br />Я условие задачи понял следующим образом.<br /><br />На острове есть 888 кареглазых и 111 голубоглазых сектантов. Это распределение самим островитянам не известно. Каждый островитянин встречался с другими, поэтому он знает, что на острове 999 человек (и голубоглазый турист). Рассмотрим островитянина, без ограничение общности, номер 1. <br />Если у него голубые глаза, то он видел 110 голубоглазых и 888 кареглазых.<br />Если у него карие глаза, то он видел 111 голубоглазых и 887 кареглазых.<br />В любом случае он видел как минимум одного голубоглазого.<br />Какие цвета у него глаза он не знает, до прибытия туриста. Турист сказал, что на острове существует один голубоглазый. Вопрос, может ли хоть кто-то догадаться о цвете своих глаз?<br /><br />Я не вижу какую новую информацию сообщил турист...<br /><br />Меня в условии задачи больше всего поразило <b>действующие</b> метро с одной станцией. Может подвох тут? :-)alexsmailhttps://www.blogger.com/profile/12580609091906492868noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-8417274156013756972010-01-20T18:16:48.187+03:002010-01-20T18:16:48.187+03:00Парадокс узника...<a href="http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%BD%D0%B5%D0%BE%D0%B6%D0%B8%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D0%B7%D0%BD%D0%B8" rel="nofollow">Парадокс узника</a>...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-25991899150804657932010-01-20T17:24:56.209+03:002010-01-20T17:24:56.209+03:00Согласен с тем, что американец дал базу. Без его с...Согласен с тем, что американец дал базу. Без его слов нет самого начала цепочки. <br /><br />Но несогласен с тем, что через день после голубых уедут все карие. Информацией о том, что на острове нет зеленоглазых, к примеру, островитянам недоступна. В условиях задачи это тоже не запрещено, так что после отбытия всех голубоглазых островитяне будут всего лишь уверены, что среди них не осталось голубоглазых.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-53596162807666437182010-01-20T16:45:10.805+03:002010-01-20T16:45:10.805+03:00непонятно!! оба решения очевидно правильны =) буду...непонятно!! оба решения очевидно правильны =) буду думать и надеяться на "неожиданное озарение щедро вознаграждает"Ivan Bendynahttps://www.blogger.com/profile/08613485844830182291noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-85392440961859300122010-01-20T16:38:10.549+03:002010-01-20T16:38:10.549+03:00после того, как американец произносит «Спасибо вам...после того, как американец произносит «Спасибо вам большое за тёплый и дружественный приём! Особенно приятно было в этом дивном месте встретить человека с такими же голубыми глазами, как у меня.», островитяне одновременно вздыхают "Глупец! Зачем ты дал нам базу индукции. Мы все отправимся в Ад." =)Ivan Bendynahttps://www.blogger.com/profile/08613485844830182291noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-85162896677154516872010-01-20T15:22:54.373+03:002010-01-20T15:22:54.373+03:00Голубоглазые уедут первые потому, что их меньше.
...Голубоглазые уедут первые потому, что их меньше.<br /><br />После того, как все увидели друг друга и знают это + знают, что есть хотя бы один голубоглазый, начинают тикать часы.<br />1 день: если бы Г был только один, то он бы уехал сегодня<br />2 день: если бы Г было два, то они бы уехали сегодня<br />3 ... и тд<br /><br />В этом смысле, визит американца играет роль запуска индукции в головах жителей. Новой информации он не сообщает, но позволяет подумать о шаге №1 "если Г один то все вокруг К".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-52134514437943374962010-01-20T15:06:38.335+03:002010-01-20T15:06:38.335+03:00Кажется, есть решение! (похоже, я был неправ насче...Кажется, есть решение! (похоже, я был неправ насчет реплики американца)<br /><br />Рассмотрим Случай 1, когда есть N кареглазых и 1 голубоглазый (N(К) и 1(Г)). Если сообщить им, что среди них есть по крайней мере один Г, то он тут же догадается (поскольку не видит других Г) и уедет.<br /><br />(предположим, что реплика американца и все дальнейшие рассуждения происходят до отхода сегодняшнего парома)<br /><br />Случай 2: N(К) и 2(Г). Сообщаем, что есть один Г. Тогда оба Г рассуждают так: "если бы я был К, тогда второй тут же понял бы, что он Г, и сегодня свалит". Когда на ближайшем пароме никто не уезжает, они оба понимают, что они Г, и уезжают на следующем пароме.<br /><br />Случай 3: N(К) и 3(Г). Сообщаем, что есть один Г. Тогда трое Г рассуждают: "если я К, тогда оставшиеся двое Г завтра уедут (поскольку это будет случай 2)". Когда двое Г на следующие день не уезжают, то все трое понимают, что они Г, и уезжают на 3 день от начала.<br /><br />Понятно, что для следующих случаев рассуждения аналогичные, то есть если на острове N(К) и S(Г), то все S голубоглазых уедут все вместе на S-ый день после реплики американца.<br /><br />Надо заметить, что К рассуждают точно так же, но их предположение (о том, что они К) подтверждается, когда все Г дружно сваливают. Поэтому все К сваливают на следующий день после Г.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-42015420560968643432010-01-20T14:26:12.004+03:002010-01-20T14:26:12.004+03:00Илья, мы и так знаем, что американец видел всех, и...Илья, мы и так знаем, что американец видел всех, и что на острове есть голубоглазые. Островитяне тоже это знают. Поэтому американец мог не сообщать, что он видел по крайней мере одного голубоглазого, это и так все знают. Единственная новая информация, содержащаяся в его словах - что он сам голубоглазы (или прикидывается таковым).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-47447571725115771402010-01-20T14:26:08.671+03:002010-01-20T14:26:08.671+03:00О, я понял, где ошибался! Оказывается, турист сооб...О, я понял, где ошибался! Оказывается, турист сообщил не только "на острове есть хотя бы один голубоглазый", но и кое-что еще.<br /><br />Пусть утверждение 0 - "на острове есть хотя бы один голубоглазый".<br />Утверждение 1 - "все островитяне знают, что утверждение 0 верно"<br />...<br />Утверждение n - "все островитяне знают, что утверждение n-1 верно"<br />...<br /><br />По индукции можно доказать, что до приезда туриста истинными были утверждения с нуля по 110 (число голубоглазых минус 1), остальные - ложными. После отъезда истинными стали все такие утверждения. Можно сказать, что он невольно сообщил островитянам все утверждения от 110 до бесконечности, о которых они и понятия не имели. То есть сообщил им не просто знание, а знание о знании о знании ... и так 110 и больше раз.colognoreply@blogger.com