Детские психологи выделяют момент в развитии мышления ребёнка, когда он может отличать своё знание об объекте от знания другого человека об этом же объекте. Представьте себе, что ребёнок видел, как кто-то убрал машинку с пола в шкаф. Когда приходит второй малыш, который ищет эту машинку, то наблюдатель может как осознавать, что второй не знает, где машина, так и не осознавать этого (выяснить это можно, спросив наблюдателя, где же будет искать машинку второй ребёнок). Есть и более сложные конструкции, выявляющие момент перехода ребёнка из состояния «есть только мой разум» в состояние «есть много других людей, которые видят и думают совсем иначе».
В более взрослом возрасте имеет смысл разобраться с классической задачей о трёх мудрецах. Ну а поскольку в комментариях к продолжению задачи о голубоглазых на острове возникла дискуссия на тему корректности некоторых переходов, то я слегка переформулирую эту классику, сохранив суть.Задача: Три островитянина праздновали день рождения одного из них, поедая торт с кремовыми розочками. Они так увлеклись беседой, а торт был таким вкусным, что все трое основательно перепачкали лица. Проходящий мимо человек сказал: «Крем на щеках!». Они так и не поняли, к кому обращался прохожий, но точно поняли, что хотя бы у одного из них лицо грязное.
Что было дальше? Как вы понимаете, каждый из них видел, что перед ним есть ровно два островитянина с перепачканными лицами. И никаких зеркал вокруг нет, так как они на острове Беззеркалья, поэтому себя увидеть нельзя. Осознав это, они разом замолчали, уставившись друг на друга.
Вопрос: как каждому из них удалось догадаться, что у него тоже грязное лицо?
Подсказка: легко понять, что раз каждый из них видел двух соседей с перепачканными кремом лицами, то фраза прохожего вроде бы ничего нового не добавила.
Итак, скоро вы убедитесь, что наши островитяне вытрутся салфетками, широко улыбнутся и продолжат беседу. Эта задача очень легко решается, но, похоже, является необходимой ступенькой на пути к пониманию хитросплетений огромного острова, на котором живут очень умные сектанты. Если ранее задача об острове вам не поддалась, то приглашаю обдумать всё ещё раз - теперь должно быть легче.
Хорошего дня!
Мне кажется, что поняли по взглядам. Каждый смотрел на других двух и удивлялся, почему они не вытираются.
ОтветитьУдалить@Мудрец
ОтветитьУдалитьНе удивлялся, а понимал, что те двое тоже уставились, потому как каждый увидел двух грязнуль и пытается понять, кому же была адресована фраза прохожего.
Каждый из них видит картину 2 грязных смотрят в ожидании что кто-то вытрется.
ОтветитьУдалитьЭто можно представить так.
1 2 3
1 0 Х Х
2 Х 0 Х
3 Х Х 0
Если никто не начинает вытираться - означает что все видят двух грязных.
А значит грязнули - все.
Следовательно надо вытереться.
Правильно?)
Они потрогали лицо руками и поняли что они грязные.
ОтветитьУдалитьАнонимный:
ОтветитьУдалитьОни потрогали лицо руками и поняли что они грязные.
Так кроме лица еще и руки испачкали :)
Каждый заметил, что два других грязнули, глядя на третьего не вытераются, как и он сам. Значит, и третий сразу понимает, почему они не вытераются. А потому все сразу начнуть вытираться.
ОтветитьУдалитьПомню эту задачку - почему-то не люблю задачи данного типа. Кстати, если бы мудрецов было не три, а стопицот, то так просто она не решалась бы - потребовалось бы дискретное время (как в задаче о неверных женах/мужьях).
ОтветитьУдалитьPS. Какой-то странный тут OpenID - не опенидный совсем. При отправке каждого нового коммента приходится заново представляться и заново вводить капчу. Права как у анонима.
Можно более или менее реалистично формализовать задачу и с непрерывным временем, избежав парадокса одновременности причины и следствия. Пусть островитяне видят и мыслят мгновенно, а вот действия производят с задержкой - каждый раз случайной и не превышающей одной секунды. Причем этот факт является у островитян общим знанием. Тогда, подсказывает мне интуиция, не раньше, чем через две и не позже, чем через три секунды после сообщения все островитяне начнут вытирать щеки.
ОтветитьУдалитьdarth-sauber, странно, что OpenID глючит. Я им пользуюсь иногда - воспроизвести проблемы не удавалось. Не знаю, как лечить (
ОтветитьУдалитьНа самом деле, осознанием цепочек "он знает, что другой знает, что третий знает и.т.д." развитие не останавливается. Далее можно приходить к счетным цепочкам: "он знает, что для любого n, цепочка "другой знает, что все знают, что все знают, и.т.д. n раз верна" а потом и к любому вполне упорядоченному множеству.
ОтветитьУдалитьТут дело в том, что невозможна ситуация, когда каждый видит одного грязного — если бы так было, то грязный бы видел только чистых и понял бы, что надо бы вытереться. Если я вижу двух грязных, но я чистый, то они бы видели одного грязного, что невозможно — значит, я тоже грязный.
ОтветитьУдалитьВот если бы в задаче был четвёртый, то это не было бы уже так очевидно.
ОтветитьУдалитьСмотрите:
ОтветитьУдалить1) Четвёртый чистый: трое грязных понимают, что они грязные и вытираются, т.к. каждый из них видит двух грязных.
2) Четвёртый грязный: каждый видит трёх грязных и не знает, все грязные или только те трое. Чтобы это определить нужно дождаться момента, когда те трое не смогут себя определить — когда наступит этот момент? Проще сразу вытереться, если будешь ждать и сидеть грязным — станешь выглядеть дураком. Если трое догадаются раньше, то ты чистый и не успеешь зря вытереться.
Решение задачи в неочевидном случае вероятностное, оно основывается на том факте, что благоприятный исход более вероятен, чем неблагоприятный. Если четвёртый чистый ошибается, то все оставшиеся это видят и их шансы на решение возрастают до 100%. Для группы в целом в этом случае выгоднее сразу сказать решение, чем ждать.
ОтветитьУдалитьДа, забыл сказать — для простоты я принял время вытирания равным нулю, если это не так, то алгоритм более сложный.
ОтветитьУдалитьА теперь о голубоглазых островитянах: Если голубоглазые примут вероятность, что они голубоглазые как Х=количество видимых голубоглазых, а кареглазые как Y=количество видимых голубоглазых, то Y будет больше, чем X на 1. Далее если одну единицу принять за день отъезда, то голубоглазые, уехав на день X, во-первых, будут абсолютно правы и, во-вторых, дадут информацию кареглазым, что они не голубоглазые. После чего кареглазые конечно-же тоже уедут, поэтому лучше им такой информации не давать, а значит никто не уедет с острова, пусть даже они знали, что уехав в день Х они будут абсолютно правы насчёт цвета своих глаз.
ОтветитьУдалитьЕщё про голубоглазых: по условию для отъезда голубоглазые должны знать свой цвет, но до отъезда они его не знают, а лишь на 100% догадываются — в чём разница? Догадка со 100% вероятностью это ещё не знание, но в любых действиях ею можно оперировать также, как и знанием.
ОтветитьУдалитьQuark Fusion:
ОтветитьУдалитьголубоглазые, уехав на день X, во-первых, будут абсолютно правы
Вот тут, пожалуйста, поподробнее. Самое интересное здесь - почему они вдруг уедут. Правила-то жесткие: если островитянин логически вычислил цвет своих глаз, он однозначно уезжает, пока же он имеет право предполагать о себе два варианта, он однозначно остается.
поэтому лучше им такой информации не давать, а значит никто не уедет с острова
Они не могут в этом вопросе руководствоваться целью кого-либо дезинформировать. Вычислил - уехал, недовычислил - считает дальше.
для отъезда голубоглазые должны знать свой цвет, но до отъезда они его не знают...
Пока не знают - не уезжают. Чтобы уехать, надо именно до отъезда сначала узнать.
...а лишь на 100% догадываются
Вообще-то, задача не вероятностная, но интересны подробности расчетов, дающих эту цифру.
Догадка со 100% вероятностью это ещё не знание, но в любых действиях ею можно оперировать также, как и знанием.
Все-таки не в любых. Чтобы уехать с острова, надо именно знать. Узнать у них только один путь - логически вычислить.
После слов туриста они сначала вычисляют и уже со знанием уезжают. Вы утверждаете, что они и без туриста могут вычислить. Опубликуйте уже эти вычисления.
Внимание, данный комментарий претендует на отдельный топик! (Но у меня нет возможости его сделать и связать с этим)
ОтветитьУдалитьВот, кстати, рекомендую почитать статью о принятии решений людьми: http://www.diggreader.ru/2010/03/12/v-obhod-nepryamoy-put-k-uspehu/
Отрывок про непрямой подход:
________
Никакой науки принятия решений нет и не будет. Мы не решаем проблемы так, как это подразумевается в концепции научного метода принятия решений, просто потому, что не можем. Потому что наши цели, как правило, неточны и многогранны, и меняются по мере приближения к ним. Наши решения зависят от реакции окружающих, и от того, какую реакцию мы от них ожидаем. Мир — это сложная и недостаточно познанная нами вещь, наше знание о нем неполно, и так будет всегда, сколько бы мы его ни изучали, и как бы ни анализировали все, что нас окружает.
Тот, кто действует по принципу непрямого подхода, решает проблемы, природа которых проявляется только по мере их решения. Как во всех хороших приключениях: мы узнаем характер своих целей и средств их достижения путем экспериментов и открытий, которые нам приходится совершать по ходу дела. Принцип непрямого подхода — это адаптация и импровизация по мере продвижения.
¯¯¯¯¯¯¯¯
Задача человека сводится к тому, чтобы разными методами найти возможный ответ (среди них метод вывода через доказательства), а потом найти подтверждение правильности этого ответа.
Метод, основанный на выводе последующих действий через доказательства неприемлем для некоторых задач со сложной структурой. Например: пользователю объясняется, как в компьютерной программе сделать определённое действие, но программа может находится в разных состояниях и путей сделать то же самое действие множество, пользователь не может вывести доказательство правильности его действий (поскольку оно слишком длинное, большое и сложное, должно учесть массу факторов, не известных пользователю, без которых доказательство не будет абсолютным), но может определить, когда метод больше не дееспособен. Имея несколько вариантов решения, пользователь способен переключиться на более подходящий, поэтому в компьютерных программах правильная инструкция должна указыватть несколько путей, покрывающих все возможные состояния программы и давать алгоритм выбора между путями, однако подобный способ окажется всё ещё слишком сложным (хотя это и есть самый простой способ с гарантированным результатом), поэтому пользователю даётся ещё более простой способ с негарантированным, но высоковероятным успехом — в итоге мы имеем массу "леммингов", которые с большой вероятностью могут решить задачу и прийти к результату быстрее, чем несколько умных людей, имеющих гарантированное решение и способных его понять, однако неспособных действовать в непредвиденной ситуации. С другой стороны, если человек способен понять универсальный алгоритм, это ещё не гарантирует того, что он сможет осилить непредвиденную ситуацию — ближе к этой гарантии, в большей степени, оказывается тот, кто сам вывел более универсальный способ решения.
Это всё к тому, что человечество не должно оперировать ситуацией, в которой все люди равны, поскольку в реальности это не так (и почти все об этом догадываются на 100%). {Все ли знают, что все знают, что не все люди равны? — Нет! Но важно ли это? Решение возможно и без этого знания.}
Quark Fusion, конечно все люди разные, а реальный мир значительно сложнее и интереснее математических задачек.
ОтветитьУдалитьРечь о том, что
1) умение отличить правильное решение логической задачи от ошибочного словесного потока - очень полезный навык (и не только для руководителей),
2) процесс чистого решения математических проблем является очень хорошим массажем для головы.
Никто и не надеется, что прямое приложение математических навыков часто требуется в реальной жизни. Но умение отличать правдоподобное от правильного часто выручает. И один из способов натренировать в себе способность это отличать - решать математические задачки.
Дмитрий, учитывая жёсткость условий, я утверждаю, что они не уедут, вероятность того, что на острове мог быть один голубоглазый и что турист в этом случае сказал бы тоже самое — бесконечно близка к нулю. Тут нельзя действовать без учёта вероятности.
ОтветитьУдалитьЯ утверждаю, что нет такого решения, в котором островитяне будут находится в состоянии "вычислил" до момента отъезда. Здесь момент вычисления совпадает с моментом отъезда, и если отъезд не происходит, то и успеха вычисления тоже нет. А если происходит, то он сам гарантирует успех решения.
Нельзя это узнать до отъезда — можно только во время. До отъезда можно только догадаться, но не быть уверенным. Уверенность даст сам отъезд.
Подробности прихода к 100% вероятности я пока не могу выразить на словах — особенность мышления. Почитайте мой предыдущий комментарий и статью, на которую я ссылаюсь, чтобы понять почему такой подход более "правильный" в реальном мире.
Да — не в любых, здесь парадокс и он в том, что чтобы уехать надо узнать, но чтобы узнать надо уехать.
Я утверждаю что со словами туриста вероятность угадывания цвета глаз такая же, как и без туриста. Именно знания своего цвета глаз это не даёт, поскольку ситуация с одним голубоглазым и туристом, упоминающем голубоглазого — невозможна (вероятность этого очень сильно мала или ноль). Вот если бы в задаче было известно, что, приехав на остров с одним голубоглазым, турист сказал бы то же самое и не сказал бы этого, если голубоглазых было ноль — вот тогда ещё можно что-то мутить, но об этом ничего не говорится.
Опубликовал в комментарии от 13.03.10 0:47, на более подробное меня пока не хватает.
Илья Весенний, я утверждаю, что эту задачу нельзя решить "чисто".
ОтветитьУдалитьПервое возможно только в простом случае. Со вторым согласен, но решение задачи в чистом виде, когда это невозможно — это плохой "массаж".
А как отличить правдоподобное практически на 100% с правильным? Разве многие научные теории не считались сперва "правдопобными", а потом оказывались правильными и наоборот? Как отличить те, что в будущем окажутся правильными от тех, что нет?
Строго говоря, аналогии нет. Хотя теперь я понял позицию тех, кто утверждает, что все уедут с острова. Хотя по-прежнему с ней не согласен.
ОтветитьУдалитьРоль прохожего и туриста не совсем одинакова. Прохожий задаёт абсурдность: если я вижу, что как минмиум двое грязны, а обращение было к одному лицу, при том что вытираются оба грязнули, то, значит, ни один из них не видит только одного грязного; значит, я грязный. Но эту логику уже озвучили; в реальной жизни она, конечно, работать не будет.
Турист сообщил: а среди вас есть один голубоглазый. Абсурдность не задана; ибо эта информация и так была известна. Или я не до конца понимаю матиндукцию (не исключаю такого), либо она неприменима к глазам :) Нет смысла предполагать «если бы голубоглазый был один, то…», ибо их точное количество минус ноль или минус один известно каждому изначально. Островитянин с голубыми глазами не может предположить: «каждый голубоглазый видит или 110, или 109 глоубоглазых», потому что так думает каждый из них. Если я вижу вокруг себя 110 голубоглазых, то это означает, что я или голубоглазый, или кареглазый. Отсюда однозначный вывод сделать нельзя.
Поэтому, до тех пор, пока не доказано обратное, надо предполагать имеющиеся знания верными — в случае с голубоглазыми островитянами предположение о том, что их ровно столько, сколько видно верно до тех пор, пока не доказано обратное. Поэтому если на острове нет голубоглазых, до любой, знающий о их возможном наличии просто уезжает и доказывает это всем остальным. Да, он ошибётся, но этот вариант более правилен для человека, чем сидеть и ждать и он не приводит к таким пародоксам. Проблема задачи в том, что поведение человека не задано — в таком случае условие задачи недостаточно определено для возможности её решения. Замените человека на компьютер с жёстко заданной программой и решение у задачи будет однозначное.
ОтветитьУдалитьПростите, ради бога. Островитянин с голубыми глазами может предположить...
ОтветитьУдалитьiuris, тут нельзя применять индукцию, потому что её база и переход не доказаны. Доказательство базы предполагает возможность одного голубоглазого и невозможность нуля, а переход — что видящие голубоглазого будет действовать по схеме не видящего.
ОтветитьУдалитьУчёт абсурдности интересен — почему он не будет работать в реальных условиях? Да, с туристом нет абурдности и этот метод нельзя применить, но можно его учесть.
ОтветитьУдалитьQuark Fusion, что значит «вероятность того, что на острове мог быть один голубоглазый и что турист в этом случае сказал бы тоже самое — бесконечно близка к нулю»?
ОтветитьУдалитьНа острове 111 голубоглазых, поэтому говорить о вероятности наличия одного голубоглазого странно - тут точно нулевая вероятность. А высказывание туриста задано условием задачи, поэтому тоже нет смысла обсуждать вероятность этого высказывания.
iuris, Вы пишете: «Роль прохожего и туриста не совсем одинакова. Прохожий задаёт абсурдность: если я вижу, что как минмиум двое грязны, а обращение было к одному лицу...». Но мы не знаем, кого из них видел прохожий. Возможно, он видел только одного из празднующих, поэтому и обратился только к одному. Это не лингвистическая задачка, поэтому искать такой смысл не стоит.
iuris, я тут говорил, что можно действовать на основе неоднозначного вывода — думаю сложно логически это доказать. Но это применимо только, если результат действий желаем — это так в задаче про мудрецов и испачканных, но не так в задаче о голубоглазых. Получается, что в задаче о голубоглазых ни один метод из озвученных не применим, и скорее всего абсолютно применимого метода и нет, поэтому островитяне уезжать не станут.
ОтветитьУдалитьИлья, вы вот говорите, что вероятность одного голубоглазого точно ноль, но решение об отъезде основывается на ненулевой вероятности наличия одного островитянина — вот вам противоречие. Противоречие обычно означает неправильность вывода.
ОтветитьУдалитьВ случае нуля голубоглазых верность высказывания туриста под вопросом. Без определённости верности этого высказывания единственный голубоглазый уезжать не станет, потому как он может предположить, что он кареглазый, а турист прикалывается.
iuris не прав насчёт разницы между прохожем и туристом, но прав насчёт идеи абсурдности.
Илья, может быть, чтобы в задаче не усматривался "лингвистический подвох", стоит убрать обращение "Уважаемый"? Останется неопределенность - обращение на Вы или множественное число. Т.е. от 1 до 3.
ОтветитьУдалитьQuark Fusion, Вы пишете: «тут нельзя применять индукцию, потому что её база и переход не доказаны». Математики обычно указывают в приведённом доказательстве номер конкретную цитату, с которой начинается ошибка в доказательстве оппонента. А политики просто голословно объявляют всё доказательство неверным. После этой итерации оппонент имеет возможность исправить обнаруженную ошибку (и это часто бывает), а инициатор после этого может найти следующую. Рано или поздно процесс "сойдётся".
ОтветитьУдалитьПо поводу Вашего высказывания «вы вот говорите, что вероятность одного голубоглазого точно ноль, но решение об отъезде основывается на ненулевой вероятности наличия одного островитянина — вот вам противоречие» мой ответ такой:
1) Решение не основывается на ненулевой вероятности наличия одного голубоглазого островитянина! (Оно вообще не основано на вероятностных соображениях)
2) Если на острове голубоглазых заведомо больше сотни (это видит каждый), то почему рассуждение, в котором обдумывается наличие на острове только одного голубоглазого, является противоречивым? В чём противоречие? Это допустимо и корректно!
Дмитрий, да, это хорошая идея.
Quark Fusion:
ОтветитьУдалитьНо это применимо только, если результат действий желаем
...
он может предположить, что он кареглазый, а турист прикалывается
На эту тему уже давно был комментарий colog: тогда уж единственный голубоглазый может сказать себе "А я ничего не слышал".
Но это все нематематические соображения. И задача-то не о поведенческих реакциях и не о принятии решений в условиях неопределенности, а собственно о наличии или отсутствии информации. Вот по этому признаку и произошло разделение на три группы:
1. Турист привнес информацию.
2. Информации как было недостаточно, так и турист не добавил
3. И без всякого туриста информации было достаточно.
В конце концов, можно применить метод, рекомендованный Ильей - "качание условий". Вас смущает нежеланность результата? В исходной задаче позитивная мотивация заменена природной честностью и религиозностью. Но давайте видоизменим. Пусть они уезжают не на худший, а на лучший остров. Это что-то меняет? Именно в том смысле, что турист либо дал, либо не дал информацию.
Илья, с моей точки зрения рассуждение об одном не корректно потому, что невозможна в реальности такая ситуация (когда один видит 998 кареглазых, в рассуждении должно быть: он видит 888/887 кареглазых и еще сотню с непонятным цветом)
ОтветитьУдалитьПо (1): вы принимаете вариант как однозначный тогда, когда эта однозначность не доказана.
Я не указал цитату из-за лени, но тут всё банально просто — неверно утверждение "если для одного верно, до и для 1+N тоже верно". Я переосмыслю это, когда будет опровергнута теорема Ферма, потому что моя теорема похожа — для N>2 утверждение уже не верно. А доказать это мне сложно примерно настолько, как и ту теорему Ферма.
Да, Дмитрий, эта задача математически решается только при особых допущениях, о которых не говорится и возможность этих допущений не доказана.
Да, если остров лучший, то это всё меняет — все уедут через Х дней после первого общего сбора.
Среди указанных вами групп в этой задаче 2 сложно отличить 3. Первое уж точно не верно.
Ой, в последнем моём предложении говорится не о туристе — это всё меняет независимо от туриста.
ОтветитьУдалитьЧто значит «неверно утверждение "если для одного верно, до и для 1+N тоже верно"»? У меня нет такой фразы.
ОтветитьУдалитьQuark Fusion:
ОтветитьУдалитьСреди указанных вами групп в этой задаче 2 сложно отличить 3
Отличие существенное:
1. До приезда туриста островитяне не могли узнать цвет своих глаз. А после его отъезда смогут.
2. До приезда туриста островитяне не могли узнать цвет своих глаз. И после его отъезда не смогут.
3. Даже если турист не приедет, они все равно могут вычислить цвет своих глаз.
Да, если остров лучший, то это всё меняет — все уедут через Х дней после первого общего сбора
Таким образом, Вы придерживаетесь варианта 3.
Вот эту мысль давайте развивать. Условие дополним так: пропуском на паром является заявление о цвете своих глаз. Он же его вычислил - значит, может назвать. Но если он называет неправильно, то его сильно наказывают. Суровость наказания не позволяет им проявлять даже малейший риск, пытаясь угадать, т.е. "на авось" никто не действует. Подсмотреть по-прежнему негде, только вычислить. Разговоры на эту тему также по-прежнему исключены. Чего им еще не хватает? Общего сигнала к действию? Ну я уже предлагал: если это необходимо, пусть вместо туриста приедет дирижер и даст отмашку.
Ответ на комментарий Ильи:
ОтветитьУдалитьБез этого утверждения нельзя применять индукцию. То есть я оспариваю само применение индукции как верное. У вас нет такой фразы потому, что Вы не обосновали чётко индукцию и я переосмыслил Ваши слова так, чтобы было чёткое обоснование — здесь я мог Вас неправильно понять и/или допустить ошибку в переосмысливании.
Как я понял индукцию:
1) База: (цитирую)
________
пусть на острове есть один голубоглазый и много кареглазых сектантов. Получив подсказку от туриста, голубоглазый всё понимает: раз он видит вокруг только кареглазых, а хотя бы один голубоглазый на острове есть, то это именно он.
¯¯¯¯¯¯¯¯
Моё понимание: при N=1 сомневающийся уедет с отсрова.
2) Переход: если первый не уехал, то второй понял, что вариант N=1 неверен, а верен вариант N+1 (почему он верен?, а если он не верен (а он будет неверен на следующем шаге), то он его предположил, но это же вероятностный подход!)
База(1) индукции неверна, потому что такой вариант невозможен. Как мне это доказать? Она также будет неверна, если возможен вариант N=0.
Да, Дмитрий, я не придерживаюсь (1) и (2), а (3) я допускаю как возможный вариант, возможный в том случае, если они хотят на 100% угадать цвет своих глаз.
ОтветитьУдалитьИх риск бесконечно мал = ноль, так как при отсутствии опровержения до высказывания цвета вероятность стремится к бесконечности (то есть к 100%), а после высказывания становится определённо в какой группе находится невысказывшийся, а в какой высказывшийся и это совпадает с действительностью. (Вот почему оно совпадает и интересно)
Да, нехватает сигнала — таким сигналом может быть как дирижёр, так и падение метеорита или просто общий сбор.
(Я написал этот комментарий до двух предыдущих)
ОтветитьУдалитьОпять не по теме (или по теме?)… Почему я упоминаю теорему Ферма (из Википедии):
________
Простота формулировки теоремы Ферма (доступная в понимании даже школьнику), а также сложность единственного известного доказательства (или неведение о его существовании), вдохновляют многих на попытки найти другое, более простое доказательство. Людей, вопреки здравому смыслу пытающихся доказать теорему Ферма элементарными методами, называют «ферматистами» или «ферматиками».[6] Ферматисты зачастую не владеют основами математической культуры и допускают ошибки в арифметических действиях или логических выводах, хотя некоторые представляют весьма изощренные «доказательства», в которых трудно найти ошибку.
¯¯¯¯¯¯¯¯
На мой взгляд, существует доказательство моей теории, но оно настолько сложное, что сам я не могу его сформулировать. А доказательство с туристом одно из таких, в которых трудно найти ошибку, особенно усложняет это наличие самого туриста и непонятность того, какое влияние он оказывает.
Ещё больше усложняет то, что моя теорема основывается на невозможности варианта с одним голубоглазым и принимает возможность его продолжения из-за невозможности начала, потому, что начало опровергает возможность продолжения (о как сказал — уверен, что почти никто ничего из этого не понял).
Quark Fusion, я кажется понял, почему Вы оспариваете применение метода математический индукции.
ОтветитьУдалитьПопробую объяснить: иногда очень сложно доказать какое-то утверждение для конкретного k=111, но оказывается легко доказать для всех k>0, вроде бы усложнив задачу (кстати, я об этом писал полгода назад).
Если я правильно понимаю, Вы требуете, чтобы я сразу доказал для k=111, а не начинал длинный разговор со слов "предположим, k=1, тогда...".
Но я доказываю следующие две вещи:
1) утверждение верно для k=1,
2) если утверждение верно для k=m, то оно верно и для k=m+1.
(это и есть база и шаг индукции)
Если доказать эти два пункта, то утверждение будет верно для всех k>0.
У Вас есть критика к этим формулировкам? Если да, то сформулируйте, какая. Если нет, то поясните, пожалуйста, с чем конкретно Вы не согласны в исходном доказательстве (лучше точную цитату, чтобы не путаться).
Нет Илья, я говорю о том, что если утверждение верно для N=1 и для N=2, то это еще не значит, что оно верно для N=3.
ОтветитьУдалитьУ меня нет критики к формулировкам, я утверждаю, что то, что ваше утверждение "верно для любых m" — не доказано, т.е. увеличить m на 1 нельзя.
Я не согласен с цитатой:
________
Получив подсказку от туриста, голубоглазый всё понимает
¯¯¯¯¯¯¯¯
особенно для случая, когда голубоглазый всего один. Особенно, когда верность этого высказывания не доказана. А что для случая N=0?
Чтобы меня лучше понять рекомендую еще раз прочитать статью про непрямой подход с пропуском всех абазцев про бизнес. Вот ещё цитата:
ОтветитьУдалить________
Прямой подход к решению проблем требует, чтобы мы знали метод решения до того, как начнем действовать. Даже если допустить возможность такого метода, он часто неэффективен. Действуя по принципу непрямого подхода, мы изучаем структуру проблемы в процессе ее решения. Таким образом, когда перед вами встает приводящая в уныние задача или кажущийся сложным проект, начните с того, что сделайте что-нибудь. Выберите небольшой компонент, который имеет отношение к задаче. Несмотря на то, что, кажется, что сначала нужно составить подробный план, обычно это не получается: цели определены недостаточно четко, суть проблемы постоянно меняется, она слишком сложна и у вас не хватает информации. Прямой подход просто невозможен.
¯¯¯¯¯¯¯¯
Илья, Вы писали:
ОтветитьУдалитьДля квадрата со стороной 2^k, из которого вырезали одну клетку в произвольном месте, существует покрытие г-образными триминошками.
Так вот, это неверно для k=0 — получается квадрат из клетки без одной клетки.
Там тоже индукция идёт в обратную сторону: если известно N-1 — легко дойти до случая N-1=0, когда вариант уже не будет верным. Надо мне пополнить знания об индукии, что-то я не припомню метода N-1, помню только N+1.
У меня нет критики к формулировкам, я утверждаю, что то, что ваше утверждение "верно для любых m" — не доказано, т.е. увеличить m на 1 нельзя.
ОтветитьУдалитьСначала я для понятности наглядно разобрал первые несколько шагов, чтобы было легче понять строгий переход (это было необязательно). А потом доказал и переход от m к m+1 (читайте со слов «Теперь сделаем этот шаг строго.» в исходной заметке).
Для квадрата со стороной 2^k, из которого вырезали одну клетку в произвольном месте, существует покрытие г-образными триминошками.
Так вот, это неверно для k=0 — получается квадрат из клетки без одной клетки.
А для k=0 мне это и не нужно доказывать. База может начинаться где угодно. Мне достаточно иметь её для k=1.
Там тоже индукция идёт в обратную сторону
Сначала там идут пояснения, а потом уже чёткое доказательство (со слов «Пришло время для изящного решения»).
Надо мне пополнить знания об индукии
Да, это должно снять многие вопросы. Рекомендую "Знакомство с методом математической индукции" - это вполне неплохой текст.
Илья, я по-прежнему не вижу доказательства базы индукции — я ведь тоже предполагаю, что на день N они уедут, только моя база строится на наличии голубоглазых де-факто — ну нельзя видеть более двух голубоглазых, если на острове их всего два, когда возможна ситуация, когда голубоглазый видит одного.
ОтветитьУдалитьВам "достаточно иметь её" — она должна быть доказана для начального случая, индукция гарантирует её верность для всех последующих, но не для предыдущих.
Что-то я не пойму, по вашей ссылке говорится, что доказывать базу индукции не надо и ещё есть такой текст:
________
Вообразим очередь, где первой стоит женщина, за ней снова женщина, а за ней снова женщина. Верно ли, что все стоящие в очереди — женщины?
Конечно, верно! Раз первые три человека в очереди — женщины, то, скорее всего, это очередь за косметикой, или за чем-нибудь таким, в чём нуждаются и разбираются исключительно женщины, и мужчин в этой очереди нет.
¯¯¯¯¯¯¯¯
Тут что, доказывается наличие в очереди только женщин? Я тоже дезодорант покупаю, а я мужчина, или я тоже женщина?
Ну да, строчкой далее говорится, что это не ММИ. Далее: "пусть первое утверждение Y1 верно и мы умеем доказать, что из верности утверждения Yk следует верность Yk + 1. Тогда все утверждения в этой последовательности верны." — предполагается Y1 верно, а Y1 вообще возможно?
Цитата:
________
(Аксиома индукции) Если какое-либо предложение доказано для 1 (база индукции) и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за n натурального числа (индукционное предположение), то это предложение верно для всех натуральных чисел.
¯¯¯¯¯¯¯¯
— Верно, только если доказано для 1! Значит доказывать базу надо! То есть в вашем решении должно быть доказательство того, что турист мог приехать на остров с одним голубоглазым и это сказать. Туристу разве не запретели называть цвет глаз кому-то конкретно?
В моём случае вариант, что кареглазый видит трёх голубоглазых принимается как база (три островитянина уедут на день 3, да вообще не важно на какой — это база, можно предположить, что это минимум и принять день отъезда = 0), а всё остальное доказывается по ММИ. Надо мне доказывать базу? В условии говорится, что есть хотя бы один голубоглазый? А он знает условие? Почему он не может предположить, что турист приехал на остров с нулём голубоглазых и это сказал?
Викикнига оставляет желать лучшего.
индукция гарантирует её верность для всех последующих, но не для предыдущих
ОтветитьУдалитьКонечно, мы про предыдущие и не доказываем ничего. Если мне надо доказать для n=248, то я могу
1) взять базу n=53 (т.е. проверить, что при n=53 утверждение верно),
2) доказать, что если верно при n=k, то верно и при n=k+1.
И тогда метод математической индукции гарантирует мне, что при всех n>53 утверждение тоже будет верно. Тем самым я получу доказательство того, что утверждение верно при n=248.
Тут что, доказывается наличие в очереди только женщин? Я тоже дезодорант покупаю, а я мужчина, или я тоже женщина?
Я правильно понял, что Вы высмеиваете текст, который написан для пояснения, почему нужно уметь доказывать чётко и формально, а не размышлять бытовым образом?
предполагается Y1 верно, а Y1 вообще возможно?
А как можно проверить истинность утверждения, которое невозможно? Когда мы проверяем истинность базы, то мы проверяем истинность утверждения Y1. Если оно истинно, то оно, конечно, возможно.
В моём случае вариант, что кареглазый видит трёх голубоглазых принимается как база
Хорошо, давайте начнём с базы "на острове трое голубоглазых". Это ничего не изменит. Вы ведь согласны с индукционным переходом? А это значит, что Вы согласны с выводом индукции для любого количества голубоглазых большего трёх (так как Ваша база проверена при n=3). И это значит, что вывод верен и при n=111, что нам и требуется.
Действительно непонятно, как же удается методу полной индукции обойтись без доказательства базы.
ОтветитьУдалитьДокажем, что 2x2=5. Пусть все утверждения совпадают и равны 2х2=5. Шаг индукции очевиден: из утверждений 1, 2, ..., n (2x2=5, 2х2=5 и 2х2=5) следует утверждение n+1 (2x2=5). А больше ничего не нужно, считает автор викиучебника, - теорема доказана.
Вот Илья, о том речь, что возможность одного островитянина не доказана — все знают, что один есть и если бы он сам это знал и был правда один, то уже бы уехал без всякого туриста.
ОтветитьУдалитьТекст про женщин был без пояснения сарказма, так что я не понял для чего он там вообще. Он ничего не объясняет. Его там как-то доказывают, ссылаются на другие нипонятные (ошибка специально) вещи — в общем, непосвящённому человеку там ничего не понятно, да — я его высмеиваю и имеено потому, что там не говорится для чего он. Что-то я не вижу в том тексте, что метод про женщин не верен — скорее наоборот.
colog, там же ясно написано:
ОтветитьУдалить«И пусть мы умеем доказать, что из верности утверждения Y1, Y2, Y3, ..., Yk следует верность Yk+1». Но мы это не умеем доказать, оперируя с Y1='2x2=5', так как это утверждение просто неверно. Поэтому данный принцип не применим с таким Y1.
Quark Fusion,
ОтветитьУдалитьответ на о том речь, что возможность одного островитянина не доказана
Как можно доказать существование чего-то? Предъявить мысленное построение (мы же говорим про мысленный эксперимент, верно?). Я его предъявляю:
Представьте себе остров, на котором есть один голубоглазый и 998 кареглазых сектантов. Все они знают по условию, что люди бывают только голубоглазыми или кареглазыми, но не знают, оба ли цвета представлены на острове (это первый пункт условия задачи). И живут они в мире и согласии: кареглазые видят одного голубоглазого, но каждый из них не знает цвет своих глаз, а голубоглазый видит только кареглазых - и тоже не знает цвет своих глаз. Как им из этой ситуации догадаться? Дождаться туриста, который скажет, что на острове есть голубоглазый. А как без туриста? Предложите свою версию их размышлений.
Да никак не догадаться, турист им наврал, что на острове есть зелёноглазый — все поверили и уехали. То, что он на самом деле сказал "голубоглазый", а не "зелёноглазый" — всего лишь совпадение. Где доказана правдивость туриста?
ОтветитьУдалитьЯ же мысленно представляю, что на острове есть четыре голубоглазых, каждый из них видит троих, понимает, что каждый из тех троих видит двоих + его, догадывается до решения уехать на день N и уезжает, если все этого хотят. Его решение основывается лишь на вероятности правильного решения, которое всегда будет правильно, если отбросить случаи N=0, N=1 и N=2, а он их отбросил, потому как видит N=3.
Представьте, что на острове нет голубоглазых, каждый из кареглазых видит только кареглазых, знает, что голубоглазые в принципе возможны, и тут призжает турист и заявляет "среди вас есть голубоглазый" — что произойдёт?
Илья, так мы же умеем доказывать. Каково бы ни было утверждение X, из его верности следует верность утверждения X - это очевидно. Более того, если оно ложно, то из его верности следует вообще любое утверждение - "если 2x2=5, то существуют ведьмы", гласит известный логический афоризм.
ОтветитьУдалитьА может быть, прежде чем применять полную математическую индукцию, следует сначала проверить первое утверждение на истинность? Но тогда это и будет доказательством базы.
Quark Fusion, сомнений в словах туриста быть не должно, так как по условию он сказал правду. И сказал он именно о голубоглазых.
ОтветитьУдалитьПро Ваш мысленный эксперимент: я правильно понял, что Вы согласны, что я предложил корректную базу при n=1, но хотите, чтобы я сделал это же для n=4?
Представьте, что на острове нет голубоглазых
Это противоречит условию, так как турист сделал правдивое заявление о том, что голубоглазый есть.
colog, конечно, истинность Y1 тут необходима. Просто при применении метода полной математической индукции не говорят о базе и переходе, а говорят только о переходе. Но в проверку перехода включена и проверка истинности Y1 (как я выше написал... видимо, не очень ясно).
Каково бы ни было утверждение X, из его верности следует верность утверждения X - это очевидно.
Если X ложно, то мы не можем из истинности X что-то доказать. Потому что X ложно.
Короче, вопрос сугубо лингвистический и формальный.
Илья, так я же спросил, известно ли самим островитянам условие правдивости туриста? Но в любом случае не доказано, что островитяне применят именно этот метод, а не другой — зачем им вообще его применять? Вот запрётся островитянин в хижине и не узнает, уехали ли другие островитяне, а без этого знания ему нет необходимости уезжать. Или не будет смотреть в глаза другим, чтобы не понять, тот ли цвет уехал и сколько островитян вообще осталось.
ОтветитьУдалитьВобщем, приняв изворотливость островитян можно только утверждать, что они сделают, что хотят — если все хотят уехать, то уедут будучи правы без доказательства, а если не хотят — то без того же доказательства не уедут.
Разумеется, вопрос сугубо формальный — каковы условия, таков и ответ.
Про противоречие условию: если вы говорите, что нельзя представить ноль голубоглазых, то и одного голубоглазого представить нельзя, т.к. по условию их 111 — чисто формальная придирка. Зато можно представить 111 голубоглазых и мой метод работает в этом случае (с оговоркой, что им будут пользоваться).
ОтветитьУдалитьВот последняя цитата про непрямой подход, наглядно иллюстрирует:
ОтветитьУдалить________
Принцип непрямого подхода — лучший подход в ситуациях со сложными меняющимися системами в неопределенной среде и когда эффективность наших действий зависит от реакции на них других людей. Прямой подход хорош тогда и только тогда, когда имеется устойчивая среда, одномерные и прозрачные цели, и когда существует возможность точно определить, что эти цели достигнуты.
¯¯¯¯¯¯¯¯
Quark Fusion, конечно, если не хочется решать математическую задачку, то можно выдумывать и изворотливость, и ложные высказывания туриста, которых не было в условии, и зеленоглазость, которая тоже запрещена по условию, и житейские трудности, которые не имеют отношения к этой задаче. Тут я Вас останавливать не имею никакого права и желания.
ОтветитьУдалитьПока у Вас были математические вопросы, я старался на них отвечать. Если они ещё возникнут, я буду рад ответить вновь.
Quark Fusion:
ОтветитьУдалитьэта задача математически решается только при особых допущениях, о которых не говорится и возможность этих допущений не доказана
Но это же не повод лишаться радости решения интересной задачи. Допущения можно и оговорить, поварьировать условия задачи.
я не придерживаюсь (1) и (2), а (3) я допускаю как возможный вариант, возможный в том случае, если они хотят на 100% угадать цвет своих глаз
Вот из этого и будем исходить. Представьте себе, что Вы участвуете в игре. Пусть участников будет поменьше, всего 10. Они собираются в закрытой комнате без отражающих поверхностей. Каждому доктор вставляет контактные линзы таким образом, что участник не знает, какого цвета. Он знает только, что они выбраны из коробки, которая предварительно всем показана. Каждый заранее убедился, что в наличии всего два цвета: голубой и карий. За игрой наблюдает солидная комиссия из международных журналистов, так что доктор из рукава зеленые не достанет. Участник, правильно назвавший свой цвет, получает хороший приз. Назвавший неправильно платит большой штраф. В остальном условия прежние: все друг друга видят, разговоры исключены, все абсолютно умные и знают об этом. Дается удар гонга, по которому все дружно начинают думать. И далее этот гонг звучит каждую минуту, которой таким умным людям вполне достаточно, чтобы сделать любые выводы, какие только возможно. Нашедший решение дожидается очередного удара гонга и тогда о нем объявляет. Итак, Вы видите перед собой 3 голубых и 6 карих пар глаз. Какие у Вас? На каком ударе гонга Вы придете к этому решению?
Если Вы находите, что я предложил некорректные числа, то замените их любыми другими, наиболее Вам удобными.
Тут опять проблема в условии — ничего не говорится о том, кто участвует. Я изменяю Ваше условие так, что там участвуют мои клоны.
ОтветитьУдалитьК минимуму я еще не пришёл — пока будем решать без него. В вашей задаче, Дмитрий, я назову голубой цвет на четвёртом, если на третьем его не назовут, а если назовут — то карий вслед за ними. Будем считать, что это четвёртый удар. Разумеется, я предполагаю, что другие руководствуются тем же алгоритмом (мои клоны).
colog про метод полной математической индукции в ту статью вставил я. :-) Можете убедиться посмотрев историю правок.
ОтветитьУдалитьВ принципе, вам Илья Весенний объяснил уже. Я об этом первый раз услышал в классе 9 от учительницы математики, потом в университете. Более того, я знаю доказательство эквивалентности принципа математической индукции, принципа полной математической индукции и аксиомы существования минимума и его даже хотел написать (см. в самом конце Приложение B), но потом забыл (написать).
Илья Весенний, colog, у меня к вам просьба, посмотрите мой пост Рав как - непрозрачность использования эрех цавур, проверьте мои вычисления, а то я один раз уже сел в лужу. Не пугайтесь только непонятных слов, это слова ни иврите из контекста ясно, что они обозначают.
ОтветитьУдалитьQuark Fusion, хорошо, пусть это будут Ваши клоны. И пусть они действуют по Вашему алгоритму. На чем базируется уверенность в том, что в случае Вашей кареглазости те трое действительно уйдут на третьем ударе гонга? Видимо, на том, что они, как клоны, будут применять этот же алгоритм. Но тогда каждый из них будет принимать решение по результатам двух ударов гонга. На чем тогда основана уверенность в том, что в случае кареглазости третьего двое уйдут на втором ударе? На том, что в случае единственного голубоглазого, он уйдет с первым же ударом. А это не так. У единственного никаких шансов понять свой цвет, значит, он в любом случае остается. Тогда в случае двух голубоглазых никто из них не может однозначно интерпретировать неуход другого. Тогда третий не может понять, почему те двое не уходят. Значит, и трое не уйдут. Согласно алгоритму, Вы из этого делаете вывод, что у Вас голубые глаза, независимо от того, какие на самом деле Вам достались.
ОтветитьУдалитьА что предписывает алгоритм в случае, когда всего участников 7, и Вы видите 3 голубоглазых и 3 кареглазых?
Алгоритм основывается на уверенности в том, что не будет ситуации, когда один видит всех одного цвета — в этом случае он просто уходит независимо от своего цвета. Есть у каждого участника такая уверенность? — В данном случае есть.
ОтветитьУдалитьВ случае 3+3 из 7 меня будут видеть остальные 6, они выберут наименьший по количеству цвет и будут действовать по этому цвету. До принятия решения мной дело не дойдёт. Меньшая группа назовёт свой цвет и это будет не мой. (Ясно же, что мой цвет в большей группе.)
Алгоритм предназначен для большого количества участников одного цвета — в малом случае он не определён. Так же как и триминошку нельзя засунуть в квадрат из одной клетки, особенно когда эту клетку из него убрали.
Я знаю, что алгоритм будет давать верные результаты для любого N>2. При N=3 применение алгоритма под вопросом, поэтому применяю его только, если возможна ситуация N=4. Для N=4 вероятность провала уже невозможна. Вообще, вероятность провала равна тому, что кто-то не применит алгоритм. Эта вероятность стремительно падает при переходе от N=3 к N=4.
Тут ситуация как с кодами Рида-Соломона — альтернативный алгоритм работает существенно быстрее, но для M=N не гарантирует результат, зато для M=N+1 веротность уже близка к 100%, а для M=N+2 уже совсем близка.
Человек способен оценить эту вероятность и для действия ему не требуется точно 100%. Если все соглашатся действовать при близкой, но не равной 100% вероятности, то вероятность успеха автоматически становится равна 100%.
Вообще, надо оценивать не вероятность успеха, а вероятность ошибки — для людей она никогда не будет равна нулю.
Для оценки действия сообщества людей прямой подход просто не работает — нужно оценивать вероятность и действовать по ней, сам факт действия изменяет вероятность и результат будет получен уже по этой новой вероятности. Если мы принимаем, что участники рискнули и начали действовать, то в данном случае успешный результат гарантирован.
Quark Fusion:
ОтветитьУдалитьАлгоритм основывается на уверенности в том, что не будет ситуации, когда один видит всех одного цвета— в этом случае он просто уходит независимо от своего цвета.
Он не может просто молча уйти. Уходя, он обязан назвать свой цвет. Для этого он должен его как-то узнать. Подсказки ждать неоткуда - только путем умозаключений.
алгоритм будет давать верные результаты для любого N>2. При N=3 применение алгоритма под вопросом, поэтому применяю его только, если возможна ситуация N=4.
Итак, при N<3 алгоритм не применим, при N=3 под вопросом. При N=3 сами-то игроки не знают, 2 или 3. Т.е. алгоритм либо заведомо неприменим, либо под вопросом. При N=4 игроки не знают, 3 или 4, т.е. либо под вопросом, либо применим. При N=5 игроки не знают, 5 или 4, т.е. либо применим, либо "либо под вопросом, либо применим". Продолжать можно долго.
Рассмотрим 11 задач (при том, что мы условились, что общее количество игроков 10):
Задача номер N: Существует ли алгоритм действий для каждого игрока, позволяющий ему наверняка, т.е. исключая сомнения (в смысле полностью исключая), путем только собственных умозаключений узнать свой цвет в условиях, что количество голубоглазых оказалось равным N?
Число N изменяется от 0 до 10.
Задачи 6-10 симметричны 0-4, можно ограничиться 0-5.
В задачах 0,1,2 ответ отрицательный, тут мнения сходятся. Значит, при N<3 никто не уйдет, т.к. наверняка вычислить не сможет.
При N=3 у каждого два варианта: если я голубоглазый, то эти двое не уйдут, т.к. будут вместе со мной ждать следующего удара гонга; если же я кареглазый, то эти двое не уйдут, т.к. мы уже знаем, что задача 2 дает отрицательный ответ. Т.е. они не уйдут в любом случае. Значит, нельзя сделать однозначного вывода о причине их неухода. Значит, в задаче 3 ответ отрицательный.
При N=4 у каждого два варианта: если я голубоглазый, то эти трое не уйдут, т.к. будут вместе со мной ждать следующего удара гонга; если же я кареглазый, то эти трое не уйдут, т.к. мы уже знаем, что задача 3 дает отрицательный ответ. Т.е. они не уйдут в любом случае. Значит, нельзя сделать однозначного вывода о причине их неухода. Значит, в задаче 4 ответ отрицательный.
Возвращаясь к примеру, из того, что те трое, которых Вы видите, не ушли с третьим ударом, Вы делаете вывод, что Ваш цвет также голубой. Т.е. уверены в том, что был бы карий - они ушли бы. Для этого они должны как-то понять, что их трое. Как?
Представьте себе, что, приводя этот пример, я загадал для Вас какой-то определенный цвет. Вот Вы видите, что те трое сидят и не уходят. Из этого можно как-то понять, что именно я загадал?
________
ОтветитьУдалитьЗадача номер N: Существует ли алгоритм действий для каждого игрока, позволяющий ему наверняка, т.е. исключая сомнения (в смысле полностью исключая), путем только собственных умозаключений узнать свой цвет в условиях, что количество голубоглазых оказалось равным N?
¯¯¯¯¯¯¯¯
Нет, не существует в смысле "полностью исключая" для любого N.
________
Представьте себе, что, приводя этот пример, я загадал для Вас какой-то определенный цвет. Вот Вы видите, что те трое сидят и не уходят. Из этого можно как-то понять, что именно я загадал?
¯¯¯¯¯¯¯¯
Я предполагаю, что те трое — мои клоны, следовательно они используют алгоритм, следовательно не уйти они не могут, если N=3, а значит — N=4. Если N=3, а они не ушли — они не мои клоны, а я в обломе. В реальности то, что они не мои клоны известно наверняка, так же известно, что 95% людей сами знаете какие и всё это делает алгоритм недействительным.
Тут весь вопрос в мотивации — решить большинству или никому не ошибиться.
________
При N=5 игроки не знают, 5 или 4, т.е. либо применим, либо "либо под вопросом, либо применим". Продолжать можно долго.
¯¯¯¯¯¯¯¯
Ну так почему вы не продолжили, а перешли на другое рассуждение, которое не может дать вам положительный ответ?
При N=5 вероятность "под вопросом" = 1/3, при N=111 она будет = 1/109. Теперь сложность вопроса возрастает до сложности рассуждений о бесконечностях: это вероятность, что один не применит алгоритм, а к провалу приводит случай, когда все остальные не применяют алгоритм.
________
Он не может просто молча уйти. Уходя, он обязан назвать свой цвет. Для этого он должен его как-то узнать. Подсказки ждать неоткуда - только путем умозаключений.
¯¯¯¯¯¯¯¯
Ну конечно он не молча уходит, а называет цвет — причём, по теории вероятности, в случае N=1 ему выгодней назвать тот, которого он больше видит. (Хороший вопрос о том, равна эта вероятность 50% или 1/[общее количество участников].) Это гарантирует решение для второго этапа, причём если первый кареглазый, то остальные тоже называют карий цвет — если бы он видел голубого, то назвался бы не на первом этапе, а на втором (при N=2 все кареглазые назовутся на третьем после того, как голубоглазые назовутся на втором, потому что на первом никто не назвался).
Quark Fusion:
ОтветитьУдалитьТут весь вопрос в мотивации — решить большинству или никому не ошибиться.
Остается только констатировать, что просто-напросто решались разные задачи. Вы решали задачу "минимизировать вероятность проигрыша". В исходной постановке предполагалось именно "без права на ошибку".
Ну так почему вы не продолжили
Именно потому, что рассматривал задачу как чисто логическую, а не вероятностную. А сколько ни продолжай, все равно будет оставаться "под вопросом".
в случае N=1 ему выгодней назвать тот, которого он больше видит. (Хороший вопрос о том, равна эта вероятность 50% или 1/[общее количество участников].)
Вероятность здесь неизвестно, чему равна, т.к. определяется неизвестным игроку распределением. У каждого глаза того цвета, "как доктор прописал", а это неизвестное распределение.
если первый кареглазый, то остальные тоже называют карий цвет
Тогда уж наоборот, им следует назвать противоположный цвет. Они же видят, кто ушел. Значит, они другие. Кстати, в такой модели, при N=0 все сразу уйдут, отвечая наугад.
А теперь вернемся к тому, в чем была основная суть исходной задачи. Если перед первый ударом гонга кто-то скажет участникам во всеуслышанье: "Среди вас есть хотя бы один голубоглазый", то Ваша задача превращается из вероятностной в чисто логическую. Т.е. такое публичное заявление несет в себе информацию.
Quark Fusion, а ведь тогда получается, что даже не при N>3, а при N>1 Ваш алгоритм работает. За счет того, что Вы дополнили условие относительно их модели поведения: если участник видит только один цвет, он просто уходит. В таком случае, если сразу все не ушли по первому же сигналу, значит, в наличии оба цвета. Следовательно, есть хотя бы один голубоглазый. Та самая информация, которую в исходной задаче давал турист. Здесь просто был перенесен источник этой информации. Но в исходной задаче такая модель поведения при малых N не подходит. Там уж если можешь вычислить свой цвет - обязан идти на паром, не можешь - однозначно остаешься.
ОтветитьУдалитьВ итоге получается, что в обоих случаях гарантированно верный вывод обеспечивается одной и той же информацией.
________
ОтветитьУдалитьОстается только констатировать, что просто-напросто решались разные задачи. Вы решали задачу "минимизировать вероятность проигрыша". В исходной постановке предполагалось именно "без права на ошибку".
¯¯¯¯¯¯¯¯
Да, так и есть — иногда верно принять такой метод для решения задачи, иначе есть неразрешимые случаи.
По поводу распределения: можно предположить, что решка выпадает в 50% случаев, но если мы видим, что подряд выпало 10 орлов — то что-то не так с методом выбора и вероятность не 50%, а значит она в среднем около 1/11 или стремится к 0. Конечно, подобная мысль не выглядит достоверно, но это естественная мысль для человек, а мы рассматриваем людей.
________
Тогда уж наоборот, им следует назвать противоположный цвет. Они же видят, кто ушел. Значит, они другие. Кстати, в такой модели, при N=0 все сразу уйдут, отвечая наугад.
¯¯¯¯¯¯¯¯
Почему это? Они видят, что тот, кто ушёл не знал свой цвет, но назвал их — теперь они знают свой цвет. При N=0 они не отвечают наугад — они называют цвет, который видят, а это их цвет — все оказываются правы.
Если есть гарантия верности заявления и не применяется указанный мною алгоритм, то заявление является "триггером" — другой информации оно не несёт, у всех должно быть соглашение, что они принимают метод через воображаемых, когда последний не знает реальности вообще. Кстати это заявление устраняет первичную неопределённость в моём алгоритме и делает его на 100% верным. Какой смысл основываться на менее верном алгоритме, в том смысле, что он даёт решение только при определённых условиях и в этом случае фактически равнозначен вероятностному алгоритму?
Да, мой алгоритм работает при N>1, но уточнение что делать при N<4 было дано позже. Уход при N=1 это не дополнение условия, а часть алгоритма.
Задача слишком неопределённа. Утверждать, что островитяне станут считать и догадаются — нельзя, считать их никто не обязывает (как и выходить из хижины каждый день и пересчитывать всех островитян). До алгоритма они еще могут догадаться, но применять его это уже не мыслительный процесс, а физический — наблюдение.
В итоге мы приходим к психологии островитян и неопределённости условия, в таком наборе ответ — нет решений из-за неопределённости условия.
В итоге мой алгоритм может дать ошибку только для одного островитянина при N=1, для остальных островитян он ошибку уже не даст, также он не даст ошибку для всех островитян при N=0 и при N>1. Уж не знаю как доказать, но если ты видишь >100 голубоглазых, то очевидно, что голубоглазых не 1 для всех островитян и алгоритм применим. Уходить в рекурсию с отбрасыванием неопределённости относительно того, кто тебя вообразил — неправильно, по условию задачи нет такого человека, который тебя не видит.
ОтветитьУдалитьЯ, кажется, нашёл доказательнство, что в случае N=4 N=1 невозможно, т.е. способ доказательства для островитянина того, что другие островитяне также докажут это. [Но если сейчас начну расписывать и думать как выразить мысли в буквах, то опоздаю на работу — попробую вернуться к этому вечером.]
ОтветитьУдалитьСказали друг другу что им нужно умыться :)
ОтветитьУдалить