Сегодня я предлагаю погрузиться в интересную математическую проблему, выталкивающую пытливые умы к непростому философскому вопросу. Но сначала давайте вспомним, что одна из важнейших функций науки - предсказание. Соответственно, хорошая научная теория способна с высокой точностью предсказывать результаты многих экспериментов. А плохая теория часто ошибается, поэтому её перестают рассматривать.
Каждому ясно, что в физике, химии или биологии эксперименты проводятся постоянно. Но можем ли мы ставить эксперимент в математике? Конечно, можем! В своей голове. Или в компьютере :)Ниже будет текст задачи, а в следующей заметке два её «очевидно правильных» решения. Тонкость в том, что эти решения приводят к противоположным ответам. И остаётся только развести руками: ошибка явно есть, но где? Или в методе математической индукции, или в математической логике, или в математике вообще. И как тогда можно пользоваться этим инструментом, если он способен предсказать два противоположных исхода?!
Что-то похожее было, когда мы разбирали доказательство того «факта», что все стороны произвольного треугольника равны. Кто-то смог обнаружить ошибку в том «доказательстве», но её удалось быстренько закрыть. Конечно, потом мы окончательно разобрались с хитрой геометрической задачкой. Но в тот раз мы точно знали, что бывают треугольники со сторонами разной длины. Другими словами, было ясно, куда копать. А в сегодняшней задачке, я надеюсь, эта ясность придёт далеко не сразу.
Итак, вводная:
На острове Беззеркалья счастливо живут 888 кареглазых и 111 голубоглазых сектантов. Религия им всем предписывает покинуть остров в течение суток, если они узнают цвет своих глаз. Поэтому на острове нет зеркал и никто не ведёт бесед о глазах. И каждый день в 17 часов на остров прибывает паром, увозящий несчастных, которые каким-то образом случайно узнали цвет своих глаз, на другой остров «Ад» (там живут сектанты, знающие цвет своих глаз).
Уезжать на другой остров никто не хочет (наверное, название не нравится). Но если вдруг узнал цвет своих глаз, то вера обязывает это сделать. При этом никто не хитрит: если до чего-то можно догадаться, то они догадываются. Все жители острова очень умные!
Что происходит дальше? На наш бедный остров обрушивается всепроникающая демократия. Хорошо ещё, что происходит это в не очень большом масштабе: приезжает всего один американский турист. Много это или мало? Скоро узнаем!
Американский турист был подробно проинструктирован представителями ЮНЕСКО. Ему объяснили, что нельзя никак информировать островитян о цвете глаз, потому что для мировой культуры крайне важно сохранить эту очень умную, но весьма странную популяцию. Её ведь очень трудно восстанавливать! Почти все люди нашей планеты знают цвет своих глаз, поэтому не могут стать новыми жителями острова Беззеркалья.
Экскурсии прошли очень хорошо и интересно: островитяне показали американцу свои театры, музеи, библиотеки, метро (единственная в мире действующая сеть станций метро, состоящая всего из одной станции) и знаменитые статуи с закрытыми глазами. Поскольку жителей на острове мало, то американец смог увидеть каждого (и все об этом знают). Прощаясь, растроганный турист сказал: «Спасибо вам большое за тёплый и дружественный приём! Особенно приятно было в этом дивном месте встретить человека с такими же голубыми глазами, как у меня.»
На этом условие задачи заканчивается, а начинается вопрос: как поменяется жизнь на острове после отъезда разговорчивого туриста?
Пояснения:
0. Жители острова легко могут видеть друг друга. Они вообще общительные ребята - никто по пещерам не прячется. И солнцезащитными очками глаза друг от друга они тоже не прячут :)
1. Раз уж выше был упомянут метод математической индукции, то в следующей заметке будет предложено основанное на нём рассуждение. Но я думаю, что гораздо интереснее придумать его своими силами. Чтобы попытаться понять, есть ли в нём ошибка. И если есть, то где :)
2. Это не очень простая задача. Но для её понимания не надо иметь специальных знаний. Достаточно сосредоточиться. У меня ушло несколько дней на размышления, но неожиданное озарение щедро вознаграждает. Желаю всем пройти таким путём! Это того стоит.
3. Если вам знакома данная задача, то, пожалуйста, не мешайте другим читателям самостоятельно продвигаться в её понимании. Пожалуйста, не надо делать «прозрачных намёков», отбивающих интерес!
Хорошего вам дня и интересных мыслей!
Ну, для начала, если люди на острове стремятся догадаться, какого цвета у них глаза, то все, с кем встречался турист, поплывут на "Ад". Ибо если они все друг на друга посмотрят, то обнаружат единственного голубоглазого, и таким образом, поймут, что они кареглазые. Голубоглазый тоже узнает про свои глаза по тому, что все вокруг кареглазые, а голубоглазым был один. Все, кого турист не заметил, ничего про свои глаза не узнают.
ОтветитьУдалитьЕсли я правильно понял, то турист встречался со всеми островитянами. Тогда он фактически сообщил, что на острове живет по меньшей мере один голубоглазый. Но это и так было известно каждому островитянину, следовательно верно одно из трех:
ОтветитьУдалить1. Ничего не произойдет.
2. Кто-то отправится в ад, но турист не имеет к этому отношения: каждый островитянин задолго до прибытия туриста мог бы выдумать себе воображаемого друга, говорящего только правду, и услышать от него ту самую злосчастную фразу.
3. Кто-то отправится в ад, потому что у островитян ограниченное мышление, не позволяющее представлять гипотетические ситуации, пока они не произойдут на самом деле.
Если верен пункт 1, то задача тривиальна.
2 - надо выкинуть из задачи туриста и решать без него.
3 - противоречие условию "все жители острова очень умные".
Как-то так.
А сами сектанты знают скока и каких людей живут на острове (888 + 111)?
ОтветитьУдалитьТурист уходя указал на конкретного человека с голубыми глазами? Или просто сказал фразу неуточняя личность сектанта?
Думаю, что если бы они знали количество кареглазых и голубоглазых, то уже давно бы посчитали кол-во тех и других, которые видят и таким образом поняли бы цвет своих глаз.
ОтветитьУдалитьЗадача - УГ, призываю Онотоле для очистки сего блога от скверны!
ОтветитьУдалитьИсходно жители острова либо не знают распределения по цветам глаз, либо никто из них не знает больше 996 человек.
На острове может остаться от 0 до 999 человек:
1. Турист встретил 889 человек, каждый из них знает всех остальных, голубоглазый один. Голубоглазый увидел, что остальные кареглазые, понял, уехал, все кареглазые поняли цвет своих глаз, уехали, по количеству догадались оставшиеся голубоглазые, уехали.
2. Те кто провожали туриста не знают всех, с кем он встречался, информацию о цвете глаз дальше не передают, все остаются.
3. Любой промежуточный вариант.
Аффтар, больше не пеши!
Это анонимус от 20.01.10 0:52
ОтветитьУдалитьВ первом варианте неправильно, надо так:
1. Турист встретил 889 человек, каждый из кареглазых знает 887 человек, в т.ч. обязательно голубоглазово, голубоглазый знает всех. Голубоглазый увидел, что остальные кареглазые, понял, уехал, все кареглазые поняли цвет своих глаз, уехали, по количеству догадались оставшиеся голубоглазые, уехали.
Анонимус от 20.01.10 0:52, скорее всего, турист встречал всех, и все островитяне это знают. Интересно, конечно, что думает об этом сам Илья.
ОтветитьУдалитьЕсли турист встречался только с ограниченным числом людей, в котором только один с голубыми глазами, все отправляются в адЪ
ОтветитьУдалитьЕсли турист встречался только с ограниченным числом людей, в котором двое с голубыми глазами, каждый голубоглазый прошвырнёт предыдущий пункт в уме и будет ждать, что второй пойдёт в адЪ. когда паром отойдёт, он дотумкает и они отправятся в адЪ на следующем пароме (оба голубоглазых, т.е. тех, кто видел только одного с голубыми глазами + те кареглазые, которы узнали об их отъезде позже)
Если турист встречался только с ограниченным числом людей, в котором трое с голубыми глазами, каждый голубоглазый подумает "ну, кто-то из них"... кажется, да, между 2 и 3 индукции не возникает, а после 3 в Багдаде всё спокойно
Плохо сформулировано условие задачи. Стоило хотя бы дать пояснения на тему того, с каким количеством людей встречался турист. И второе, знают ли жители острова сколько из них кареглазые, и сколько - голубоглазые. Если да, то им достаточно просто собраться всем вместе и тогда все поедут в Ад :)
ОтветитьУдалитьmygentoonotes, почему все должны уезжать с острова, если их видел турист? Поясните мысль, пожалуйста, она не совсем очевидна. Вы пишете «Ибо если они все друг на друга посмотрят, то обнаружат единственного голубоглазого», как будто на острове всего один голубоглазый. Но их заведомо больше сотни...
ОтветитьУдалитьcolog, всё верно, турист видел всех. И все жители острова об этом знают. Третий пункт своей гипотезы можете смело вычёркивать, так как он противоречит условию задачи, как Вы верно заметили.
Ответы анонимам:
>А сами сектанты знают скока и каких людей живут на острове (888 + 111)?
Конечно, не знают. Иначе, они бы сразу вычислили свой цвет глаз, посчитав всех вокруг.
>Голубоглазый увидел, что остальные кареглазые, понял, уехал, все кареглазые поняли цвет своих глаз
Так будет, если на острове всего один голубоглазый. Но их же 111 по условию!
Или это Вы базу индукции доказываете?
SunChaser, а почему все должны уехать, если турист встречался только с ограниченным числом людей, в котором только один с голубыми глазами?
Было бы логично, если бы уехали только те, кого видел турист.
Andrew, да, Вы правы, уточнение о том, что все видели всех необходимо (я дополнил условие). Но я думаю, что информация о том, чего аборигены не знали, явно является лишней. С тем же успехом можно было заявлять, что следует указывать указывать в условии на то, что аборигены не знают свою ДНК (это бы им тоже позволило выяснить свет глаз). И так далее.
Хотелось бы уточнить условие задачи.
ОтветитьУдалитьНиже решение задачи в том виде, в котором ее понял я.
1. Все жители острова одинаковы по всем параметрам кроме цвета глаз. (Т.е. одинаково умные, честные и т.п.)
2. Цвет глаз определяется определяется бинарно - либо коричневый, либо голубой (никаких оттенков).
3. Люди с глазами другого цвета не рождаются в принципе.
4. Все жители острова знакомы друг с другом и с американцем и знают цвет глаз друг друга.
5. Вообще вся информация о чем-либо передается всем жителям одновременно и без задержек и реагируют на нее (анализируют) они тоже одинаково. (Т.е. заранее оговорено, что все находятся в абсолютно равных условиях, кроме данного цвета глаз. Это значит, что полностью исключены случаи, когда кто-то живет отшельником и вообще не в курсе, что происходит; случаи когда кто-то ошибся с цветом глаз другого или вообще не знает у кого какие глаза и т.п.)
6. Все жители острова знают о данных пунктах 1-5 (и возражений не имеют :) )
Такие оговорки необходимы, т.к. математическая задача должна иметь однозначное условие, иначе это уже область психологии, а не математики.
В такой трактовке заявление американца можно переформулировать так: на острове есть не менее одного человека с голубыми глазами. Но из пп. 1-6 следует, что все знают какие у кого глаза, а так как голубоглазых 111, то каждый житель острова владеет информацией о том, что жителей с голубыми глазами не менее одного. Следовательно, американец не дал островитянам никакой дополнительной информации относительно их глаз. Следовательно, чтобы не произошло дальше, американец не виноват.
А произойти может следующее:
1. Ничего не случится. Информация американца не дала ничего нового, следовательно островитяне будут жить как жили, а так как жили они не зная о своих глазах, то и дальше так будут жить.
2. Независимо от американца, путем логического анализа через некоторое время t какой-то островитянин узнает о цвете своих глаз. Но так как все островитяне с одинаковыми глазами равны, то все они придут к выводу относитльно своих глаз одновременно. Таким образом, остальные островитяне (с другим цветом глаз) либо придут к такому же выводу одновременно с первыми, либо через некоторое время после них, однако не позже чем они увидят первых уезжающих с острова. В этот момент они сделают вывод, что у них другой цвет глаз и их судьба тоже решена.
Это решение построено исходя из пп. 1-6.
Если же я неправильно понял условие, то поправьте, пожалуйста.
RK.
RK, Вы правильно поняли условие задачки. Но ещё не решили её ;)
ОтветитьУдалитьТо, что числовое распределение по глазам аборигенам неизвестно (888/111) всё же надо было явно указывать.
ОтветитьУдалитьМысль N1
Ну, если цветовосприятие у аборигенов такое же, как у американца (что весьма спорно), то должен уехать в АД человек с такими же глазами, как у американца, не найдя их ни у кого из соплеменников такого же оттенка глаз.
Мысль N2
Если всё таки считать, что речь не про оттенок глаз, а про то что американец сообщил, что голубоглазые на острове есть. По крайней мере один.
Что дальше... вспоминаются задачи о «Задача о трёх колпаках на трёх мудрецах» и про «Неожиданная казнь», но дальнейшее рассуждение пока что не понятно.
Главный вопрос что же знают аборигены? Например, знают ли они, что у них на острове только голубые и ка
88;ие глаза и нет зелёных, серых, красных (альбиносы) и т.п.
Задумываюсь над методом индукции.
ОтветитьУдалитьДля 1 голубоглазого на острове задача тривиальна (с учетом утверждения туриста).
Допустим, что нам известен алгоритм распознавания цвета глаз всех жителей острова для n голубоглазых островитян.
Пусть на острове N+1 голубоглазый островитянин. (n+1)ый голубоглазый рассуждает так - если бы глаза у меня были карие, то мы бы разобрались уже, какие у кого цвета глаза. но пока никто на Ад не уехал. Стало быть, задача сложнее, стало быть, у меня голубые глаза. После этого он уезжает на Ад, остается N голубоглазых, которые узнают свой цвет по известному алгоритму.
Как то все аляповато вышло и какие то дыры есть, но складно выходит.
Святослав.
Ага, теперь, кажется, понятно.
ОтветитьУдалить1. Пусть все множество островитян = P.
Оно состоит из двух подмножеств A и B, с A он встречался, с B нет. B тогда от американца новой информации не получает, они и так видели с кем он встречался, а вот A получает.
Обозначим голубоглазых г, а кареглазых к.
2. Рассмотрим крайний случай A=1.
Очевидно, что островитянин тогда уедет.
Пусть A=2.
если это к и г, то сначала уедет г (так как поймет, что он г), а потом уедет к (так как поймет, что раз г догадался раньше него о цвете своих глаз, то он сам не-г = к)
Вообще, последнее рассуждение верно для любого количества г и к: если вдруг все г поняли, что они г, а к еще не успели, то как только г уедут все к поймут, что они не-г = к и уедут на следующий день.
если же при A=2 это г и г, то в первый день они не уедут, но потом каждый из них поймет, что если бы он сам был к, то второй бы уехал, а так как он не уехал, то следовательно каждый из них не-к = г. Т.е. они уедут на второй день. По аналогии (или по ММИ) это рассуждение можно применить для любого количества г, просто чем их больше, тем больше дней пройдет до отъезда.
Интересно, что количество к в группе ни на что не влияет. группа из 100к и 2г на второй день лишится обоих г, а на третий всех к (которые всегда будут отставать на 1 день, так как они видят на 1 больше г перед собой и им нужен дополнительный день для анализа).
Таким образом, множество A лишится всех г на день, равный кол-ву г в A, а всех к на следующий.
Если множество A = P, то все то же самое.
Все г уедут на 111ый день, все к на 112ый.
Казалось бы, что возникает противоречие. Ведь если A = P, то американец не сообщил ничего нового, тогда откуда берется этот 111ый день?
Тут может быть несколько объяснений.
1. В условии ничего не сказано про историю острова. В принципе, если предположить, что одинаковые как роботы островитяне все в один прекрасный день приняли новую религию, то отсчет дней надо начинать именно с этой точки, а не с приезда американца. В этом случае на 111ый день после принятия религии г уедут.
2. С другой стороны, если островитяне, например, каким-то случайным образом появляются на острове и исчезают, то они не могут применить рассуждение из решения выше, так как решение исходит из посылки, что островитяне в A в начальный момент времени владеют одинаковой информацией о друг друге и ходе мыслей друг друга (в силу своей одинаковости).
А если это условие не выполняется, то и однозначное решение невозможно.
В этом случае приезд американца и его фраза действительно все меняет.
Если A = P, то американец своей фразой про глаза устанавливает точку отсчета. До этого момента такой точки не было, а обсуждать ее было невозможно, т.к. религия запрещает.
Американец эту точку создал. После этого участь островитян решена.
Хорощая задача и сайт у Вас хороший. (надо будет зарегистрироваться :) )
RK.
intro. "встретить человека с такими же голубыми глазами, как у меня". возможно американец имел ввиду оттенок, но предположим, что аборигены его недопоняли. в результате они думают, что на острове только ОДИН человек с голубыми глазами. ->
ОтветитьУдалитьДень №1. Все голубоглазые уезжают. Они видят другого голубоглазого, следовательно заключают, что их цвет - коричневый. В этот день коричневые видят, что голубоглазых больше одного, но по условию, не могут им об этом сказать.
День №2. Все коричневые уезжают, так как понимают логику голубоглазых из пункта 1.
День №3. В США появляется новый штат - Гаваи))
МК
Пусть на острове 1 голубоглазый, тогда он видит только кареглазых и валит в ад, после чего валят остальные.
ОтветитьУдалитьПусть на острове 2 голубоглазых. Тогда 2ой видит что первый не едет, а вокруг все кареглазые - все понимает и уежжает (за ним это делоют все остальные исходя из п.5 RK).
Пусть на острове 3 голубоглазых. Тогда 3ий видит 2их которые голубоглазые и не спешат в ад. Остальные кареглазые. Понимает и в ад со всеми.
Дальше так, как показал Святослав
а американец нужен для доказательства базы индукции (в случае одного голубоглазого сам он не определит цвет своих глаз)
ОтветитьУдалитьRK, спасибо за тёплые слова!
ОтветитьУдалитьДобавлю, что можно не делить островитян на поднможества, так как турист виделся со всеми.
ziyoumin, грамотно излагаете!
Но ведь все жители острова знали, что существуют голубоглазые сектанты (так как каждый видел их более сотни). Поэтому не ясно, как слова американца помогли в рассуждениях. Он же ничего нового не сказал :)
а турист точно правду сказал?
ОтветитьУдалитьЕсли предположить, что голубые глаза американца отличались от голубых глаз островитян, то, островитяне подумали, что есть только один человек, с такими голубыми глазами как у американца, а поскольку они именного таких голубых глаз не встречали, то, получается, каждый сделал вывод, что обладатель уникальных голубых глаз это он. Поэтому, всем надо собраться на пристани, для поезди в "АД".
ОтветитьУдалитьописанное выше равносильно примеру, если бы американец сказал - было здорово увидеть зеленоглазого человека. Поскольку никто из них зеленоглазых не встречал - каждый делает вывод - что зеленоглазый это он.
ОтветитьУдалитьwavezz, правду о том, что на острове есть хотя бы один голубоглазый сектант? Да, конечно. Так как на острове их 111.
ОтветитьУдалитьVictor Krasnov, по счастливой случайности турист вовсе не злодей. Он не хотел, чтобы все уехали, поэтому не заявлял, что видел среди островитян зеленоглазого :)
Он просто сказал, что видел хотя бы одного голубоглазого, будучи уверенным, что никого этим не удивит.
Еще есть предположение, что раз американец упомянул одного человека, а не всех, то островитяне захотят найти этого человека. Поэтому, в последующие дни они будут ходить по острову и спрашивать у островитян, а не тебя ли американец имел ввиду? Что приведет к вымиранию голубоглазых на острове.
ОтветитьУдалитьVictor Krasnov, турист видел 111 голубоглазых людей и 888 кареглазых. Но он не стал делиться с ними этими данными (чтобы не нарушить запрет ЮНЕСКО).
ОтветитьУдалитьОн только сказал, что ему приятно, что его цвет глаз тоже голубой. Ведь все островитяне знают, что на острове есть голубоглазые. Поэтому эти слова туриста не должны чего-то испортить, верно?
Раз американец цвет своих глаз знает - надо бы его в "Ад" и сослать =)
ОтветитьУдалитьесли б американец сказал - увидеть людей (а не человека), то слова не должны чего-либо испортить. А поскольку он выделил одного, то...
ОтветитьУдалитьНо, если это не существенно, то опустим этот момент, не будем додумывать за островитян.
Еще из нематематических версий. Американец ярко эмоционировал, радуясь встрече с людьми такого же цвета глаз. Возможно, и островитянам теперь захочется узнать собственный цвет глаз, раз это вызывает такую бурю эмоций.
Илья, а цифры 888 и 111 - здесь существенны? Либо они могут быть заменены на другие, отличные от 0-1-2.
spleaner, турист другой веры, ему нет разницы, о чьём цвете глаз знать.
ОтветитьУдалитьVictor Krasnov, он не выделил одного, а указал, что видел более нуля :)
Числа 888 и 111 не очень существенны. Но кареглазых должно быть заметно больше голубоглазых, а голубоглазых - больше сотни, например.
я немного не о том, а вдруг глаза у американца карие, а он преднамеренно, якобы для защиты аборигенов от самих себя сказал про голубые
ОтветитьУдалитьИмхо, ничего не случится.
ОтветитьУдалитьХоть он и видел всех, и, уезжая, сказал, что видел одного голубоглазого, то:
Каждый мог посмотреть на его глаза, запомнить цвет и сравнить с окружающими, и, таким образом, с первого взгляда определить, кто голубоглазый, а кто нет. Кроме него самого - ибо зеркал нет. И окружающим он тоже ничего сказать не может. В итоге все подвешивается в воздухе - все знают цвета глаз окружающих, кроме них самих, но при этом они никак друг другу этого сообщить не могут.
Но это в случае, если они не знают, сколько среди них всех голубоглазык и кареглазых. Если же это всем известно, то через некоторое время, не важно кто, хоть голубоглазый, хоть кареглазый, сосчитает количество увиденных им кареглазых и голубоглазых, и автоматом придет к выводу, какой у него цвет глаз. После этого все начнет идти по цепочке, пока на острове не останется никого.
согласен с постом RK от 20.01.10 9:36.
ОтветитьУдалитьЗадача симметрична, значит островитяне должны думать "синхронно" и уехать сначала все голубоглазые, а потом тут же следом кареглазые.
И индукция тут особо не нужна. Хотя, если хочется, то надо рассматривать её симметрично относительно всех жителей.
Заявление американца играет роль базы индукции.
Хотя, раз они умные, то все должны были уехать через 111 дней после того, как в первый раз все увидели всех и узнали об этом.
Заявление американца всего лишь говорит нам о том, что он голубоглазый.
ОтветитьУдалитьНе сразу понял, что имеет в виду RK. Попробую пояснить для тех, кто также не понял)
ОтветитьУдалитьПредположим, что в группе N голубоглазых (Г). Тогда в первый день никто не уедет(Каждый видит по крайней мере N-1 Г, и нет никакой информации о его собственных глазах). В N-1ый день каждый Г будет рассуждать так: я вижу N-1 Г, каждый из них видит либо N-2 Г (и тогда все Г уедут сегодня, а оставшиеся поймут, что они К),либо N-1 Г (значит, я Г, и уеду завтра). Каждый К рассуждает аналогично, но он видит на одного Г больше, поэтому ждет на один день дольше, чем Г. Таким образом, на N-ый день уедут все Г, на следующий - все К.
Проще всего это понять на примере 1, 2 и 3 голубоглазых.
Алексей.
wavezz, идея понятна. Тогда давайте считать, что турист в солнцезащитных очках, скрывающих цвет его глаз. Это несущественно.
ОтветитьУдалитьvayun, а почему первыми должны уехать голубоглазые? Каждый из них видит 110 других голубоглазых, поэтому слова туриста не сообщают новой информации. Верно?
Сан Саныч, заявление американца всего лишь говорит нам о том, что он видел хотя бы одного голубоглазого.
О, я понял, где ошибался! Оказывается, турист сообщил не только "на острове есть хотя бы один голубоглазый", но и кое-что еще.
ОтветитьУдалитьПусть утверждение 0 - "на острове есть хотя бы один голубоглазый".
Утверждение 1 - "все островитяне знают, что утверждение 0 верно"
...
Утверждение n - "все островитяне знают, что утверждение n-1 верно"
...
По индукции можно доказать, что до приезда туриста истинными были утверждения с нуля по 110 (число голубоглазых минус 1), остальные - ложными. После отъезда истинными стали все такие утверждения. Можно сказать, что он невольно сообщил островитянам все утверждения от 110 до бесконечности, о которых они и понятия не имели. То есть сообщил им не просто знание, а знание о знании о знании ... и так 110 и больше раз.
Илья, мы и так знаем, что американец видел всех, и что на острове есть голубоглазые. Островитяне тоже это знают. Поэтому американец мог не сообщать, что он видел по крайней мере одного голубоглазого, это и так все знают. Единственная новая информация, содержащаяся в его словах - что он сам голубоглазы (или прикидывается таковым).
ОтветитьУдалитьКажется, есть решение! (похоже, я был неправ насчет реплики американца)
ОтветитьУдалитьРассмотрим Случай 1, когда есть N кареглазых и 1 голубоглазый (N(К) и 1(Г)). Если сообщить им, что среди них есть по крайней мере один Г, то он тут же догадается (поскольку не видит других Г) и уедет.
(предположим, что реплика американца и все дальнейшие рассуждения происходят до отхода сегодняшнего парома)
Случай 2: N(К) и 2(Г). Сообщаем, что есть один Г. Тогда оба Г рассуждают так: "если бы я был К, тогда второй тут же понял бы, что он Г, и сегодня свалит". Когда на ближайшем пароме никто не уезжает, они оба понимают, что они Г, и уезжают на следующем пароме.
Случай 3: N(К) и 3(Г). Сообщаем, что есть один Г. Тогда трое Г рассуждают: "если я К, тогда оставшиеся двое Г завтра уедут (поскольку это будет случай 2)". Когда двое Г на следующие день не уезжают, то все трое понимают, что они Г, и уезжают на 3 день от начала.
Понятно, что для следующих случаев рассуждения аналогичные, то есть если на острове N(К) и S(Г), то все S голубоглазых уедут все вместе на S-ый день после реплики американца.
Надо заметить, что К рассуждают точно так же, но их предположение (о том, что они К) подтверждается, когда все Г дружно сваливают. Поэтому все К сваливают на следующий день после Г.
Голубоглазые уедут первые потому, что их меньше.
ОтветитьУдалитьПосле того, как все увидели друг друга и знают это + знают, что есть хотя бы один голубоглазый, начинают тикать часы.
1 день: если бы Г был только один, то он бы уехал сегодня
2 день: если бы Г было два, то они бы уехали сегодня
3 ... и тд
В этом смысле, визит американца играет роль запуска индукции в головах жителей. Новой информации он не сообщает, но позволяет подумать о шаге №1 "если Г один то все вокруг К".
после того, как американец произносит «Спасибо вам большое за тёплый и дружественный приём! Особенно приятно было в этом дивном месте встретить человека с такими же голубыми глазами, как у меня.», островитяне одновременно вздыхают "Глупец! Зачем ты дал нам базу индукции. Мы все отправимся в Ад." =)
ОтветитьУдалитьнепонятно!! оба решения очевидно правильны =) буду думать и надеяться на "неожиданное озарение щедро вознаграждает"
ОтветитьУдалитьСогласен с тем, что американец дал базу. Без его слов нет самого начала цепочки.
ОтветитьУдалитьНо несогласен с тем, что через день после голубых уедут все карие. Информацией о том, что на острове нет зеленоглазых, к примеру, островитянам недоступна. В условиях задачи это тоже не запрещено, так что после отбытия всех голубоглазых островитяне будут всего лишь уверены, что среди них не осталось голубоглазых.
Парадокс узника...
ОтветитьУдалитьМожет быть я торможу, так как мне работать вообще-то надо, но пробежав по комментариям я большинство просто не понял.
ОтветитьУдалитьЯ условие задачи понял следующим образом.
На острове есть 888 кареглазых и 111 голубоглазых сектантов. Это распределение самим островитянам не известно. Каждый островитянин встречался с другими, поэтому он знает, что на острове 999 человек (и голубоглазый турист). Рассмотрим островитянина, без ограничение общности, номер 1.
Если у него голубые глаза, то он видел 110 голубоглазых и 888 кареглазых.
Если у него карие глаза, то он видел 111 голубоглазых и 887 кареглазых.
В любом случае он видел как минимум одного голубоглазого.
Какие цвета у него глаза он не знает, до прибытия туриста. Турист сказал, что на острове существует один голубоглазый. Вопрос, может ли хоть кто-то догадаться о цвете своих глаз?
Я не вижу какую новую информацию сообщил турист...
Меня в условии задачи больше всего поразило действующие метро с одной станцией. Может подвох тут? :-)
Вобщем решение насчет индукции и уезда на N+- день разжевали. Насчет того, что изменил американец - попробую сформулировать - он дал отсчет того дня, когда бы уехал голубоглазый, будь он один. А дальше по индукции.
ОтветитьУдалитьНо можно и другое решение предолжить: если островитяне, как сказано в условии, умны - с одной стороны и не хотят уезжать - с другой, то не уедут в день M, а подождут немного, в надежде что другие тоже умны и поступят так же. В результате, основа для расчета собьется и никто никуда не уедет.
Давайте упростим ситуацию: на острове только два человека и они голубоглазые. К ним подходит турист и говорит: "Эй, парни, а ведь среди вас есть голубоглазый!". Если рассуждать как в решении по индукции, то оба они на следующий день должны свалить в ад. По-моему, полный бред. Эти двое и раньше знали, что среди них есть голубоглазый.
ОтветитьУдалитьЕсть следующая мысль: есть вещи, о которых математики предпочитают не распространяться (типа множества всех множеств), может и здесь что-то подобное, например, нельзя рассуждать о том, как рассуждают другие.
2 анонимный: как раз с 2 голубоглазыми отъезд обоих уж точно не "полный бред".
ОтветитьУдалитьЕсли бы один был голубоглазым а другой кареглазым - то голубоглазый бы уехал в первый день. Если он не уехал - значит оба голубоглазые. Других вариантов просто нет.
В том и вопрос, где ошибка в этих рассуждениях. Если они верны для такого простого случая, то верны и для большего числа.
ОтветитьУдалитьААААААААААААА! Я все понял! Важно не то, что турист им сообщил, а то что все слышали, как он всем это сообщил!
ОтветитьУдалить"Давайте упростим ситуацию: на острове только два человека и они голубоглазые. К ним подходит турист и говорит: "Эй, парни, а ведь среди вас есть голубоглазый!". Если рассуждать как в решении по индукции, то оба они на следующий день должны свалить в ад. По-моему, полный бред. Эти двое и раньше знали, что среди них есть голубоглазый."
ОтветитьУдалитьДа они не знали, что другой голубоглазый это знал.
Повторю, ошибка заключается в допущении, будто турист просто сообщил уже известную информацию. Подробнее см. мой пост выше.
ОтветитьУдалитьРешение для общего случая(!):
ОтветитьУдалитьНикто не уедет (либо уедет один, если он единственный, чей цвет был назван), если они должны быть точно уверены в цвете своих глаз (предположим, что пока есть шанс, что они ошибаются в догадках, то они не уезжают, т.к. не хотят), а никто не может быть точно уверенным, если он собрался уезжать один, а заранее известно, что уехать должны более одного человека, т.к. один сразу бы точно знал, что он один и уехал — такое было бы возможно только в случае, если бы ему сообщили, что есть уникальный цвет глаз, которого он не видит, а такого не было.
Но вот если достаточно лишь догадываться о цвете своих глаз, то тут логика такая: если у меня цвет глаз, как у группы А, то мы сваливаем через интервал времени в t*x, где x — количество, которое я наблюдаю в группе А. Если в группе А все думают также и я принадлежу группе А, то мы свалим в один день, если я ошибаюсь, то размерность А на один меньше, и один из группы А попробует свалить раньше и вместе с ним свалит вся группа А. Если я не в группе А, а группой А будем считать самую малочисленную группу, то я в группе Б, которая больше группы А, а значит группа А уже свалит в день Х и к тому времени я уже буду знать, что я не в группе А. После того как группы А не станет будем считать группой А группу Б и повторим рассуждение. Если есть две одинаковые группы, каждый будет знать, что он именно из той группы, о которой подумал, т.к. для всех других групп в случае, если бы он им принадлежал день сбора был бы следующим днём. t примем равным самому удобному для подсчёта интервалу времени, который одинаковый для всех. (тут мы основываемся на том, что для человека таких интервалов не будет два — например одинаково удобно считать восходы и заходы солнца, если оба они происходят в период бодрствования всех, причём можно считать только восходы или заходы, либо считать и то и другое, что приводит к рассинхронизации алгоритма и нельзя сказать, что более малочисленная группа уже свалила с острова, а это нужно, чтобы ошибиться и не свалить раньше времени)
Как можно заметить тут не имеет значения сколько всего цветов, главное чтобы кто-то дал точку отсчёта. Уедут все, у кого есть парный цвет или его цвет был назван.
Поправка: у кого есть два парных цвета, т.к. это минимально необходимое количество, чтобы свалить и не должно быть уникальных цветов, кроме названного, а также "близнецов" — т.к. обладатели таких цветов будут думать, что у них цвет из минимально наблюдаемой группы, но подтвердить свою ошибку они не смогут.
ОтветитьУдалитьВ общем, никто не должен видеть всего один цвет, если это не названный. Если всё-таки такой есть, то использовать вышеприведённый алгоритм нельзя.
ОтветитьУдалитьХотя возможен такой вариант: все парные и уникальные собираются и тот, кто видит два цвета по одному уходит — остаётся группа с парным цветом, потом снова все собираются пока никто не станет уходить. Оставшиеся имеют уникальный цвет и остаются.
ОтветитьУдалитьПредлагаю продолжить обсуждение этой задачи в следующей заметке.
ОтветитьУдалитьУфф, прочитала 2 раза и ничего не поняла
ОтветитьУдалитьVika Moo, предлагаю обсудить эту задачку с друзьями, это способствует пониманию. И рекомендую прочитать комментарии к следующей заметке, там всё разобрано.
ОтветитьУдалитьИлья, я в вас разочарован :) Первоначальный пост не содержал никакого решения, подло и изподтяжка подталкивал к придумыванию сложного и НЕПРАВИЛЬНОГО решения через матиндукцию, хотя ответ был очевиден. Ну это как если бы вы спросили сколько будет 2х2? и что-то туманно намекнули про комплексные числа (с их помощью можно "доказать", что будет 5) и про то, что кто-то счтитает как-то хитро, не дав ни "ответа", ни "решения". Это не ваш уровень :) В этом посте уже лучше, но тоже как-то слабо и неинтересно.
ОтветитьУдалитьПо поводу задачи: жители - тупые компьютеры, любой алгоритм - это переработка входной информации в выходную и для применения матиндукции вы должны были бы доказать, что на каждом шаге индукции ничего не меняется во входной информации, кроме k. Могу на пальцах показать, что ситуации с k=1 и k>1 не имеют ничего общего.
Вот вам упрощенная формулировка этой задачи: есть большое число N жителей острова. Каждый житель сегодня покончит с собой в предощущении одиночества, если будет уверен, что завтра останется 1. "Ответ": все жители покончат с собой в один день. Можно ввести какого-нибудь туриста для отвода глаз, который ничего не делает, чтобы читатели не задумывались в КАКОЙ день? Для N=1 решение очевидно. Допустим, что решение верно для k жителей, тогда оно верно для k+1 жителей, поскольку k+1 будет точно знать, что завтра останется 1. Так можно доказать все, что угодно.
Alex.
Уважаемый аноним, Вы повторили этот вопрос в комментариях к следующей заметке, поэтому я опубликовал ответ именно там (ссылка).
ОтветитьУдалить