avva | завещание калибана (решение и обсуждение, многобукв)

Я раскрыл все комментарии к задачке "Завещание Калибана". Там есть много правильных решений, но все же неправильных намного больше, хоть они чаще всего и приходят к правильному ответу (порядок ACB). Спасибо всем, кто ответил и обсуждал. В этой записи я хочу обсудить решение, почему мне так понравилась эта задача и откуда она взялась.

Изюминка этой задачи состоит в том, что для ее решения необходимо использовать не только то, что мы знаем, но представить себе гипотетических A,B,C (назову их "молодые A,B,C"), которые знали все упомянутые в задаче факты (кто видел в галстуке, был ли B в Оксфорде, кто одалживал зонтик, кто первый влюбился) и смогли ее решить. Причем мы предполагаем, что задача составлена покойным Калибаном так, что они действительно смогли бы ее решить, и при этом ни одно условие не было - для них! - лишним. Вот это понятие "лишнего условия" многих подкосило, и его часто применяли неверно, о чем я писал подробно в комментариях к предыдущей записи. Для того, чтобы его понять верно, нужно просто представить себе явственно этих "молодых A,B,C", и как им читают все условия, кроме такого-то: что они смогут понять, в чем смогут разобраться? Если такое представить - например, посмотреть, как молодые A,B,C читают условия 1) и 2), но без 3) - то сразу становится понятно, что это сильно зависит от фактов, которые они помнят: если такие-то видели в галстуке и такие-то одалживали зонтик, то они легко разберутся и без 3), но тогда 3) действительно лишнее, и поэтому именно такой вариант фактов невозможен. Без разбора возможных и невозможных вариантов фактов (про галстук, зонтик итд.) эта задача не решается.

Другая интересная ошибка, которая была у очень многих: из второго условия "Если B не был в Оксфорде в марте 1920 года, то тот, кто выбирает первый, никогда не одалживал мне зонтик" выводили "B не первый". Я долго не мог понять, почему, пока наконец до меня не дошло. Людям свойственно читать в конструкции "если X, то Y" очевидную логическую связь между X и Y, потому что так это работает в обычной жизни и речи. Если B не был в Оксфорде, значит, видимо, имеется в виду, что кто-то другой, кто был в Оксфорде, это первый и он не одалживал мне зонтик. Иначе зачем вообще упоминать B и "первого" вместе? Но по правилам чистой логики, которые применяются в логических головоломках, это конечно не так. Если B не был в Оксфорде, то вся остальная часть условия истинна, но она при этом может говорить про луну из сыра или Мики Мауса и вообще не иметь никакого отношения к B. Я настолько привык к такому "чисто логическому" прочтению, что искренне не мог понять, почему мне столько людей снова и снова пишут "B не первый". Наверное, из этого следует, что второе условие составлено плохо, и его надо переделать (в третьем условии такой проблемы нет, потому что обе части говорят про порядок, так что интуитивная связь есть). Эта формулировка второго условия не моя, она совпадает с тем, как эта головоломка опубликована и по-английски, и в русском переводе (о нем см. ниже).

Теперь я приведу еще раз условия, и после них полное решение, в том виде, как я его нашел.

"1) Видевшие меня в зеленом галстуке не могут выбрать раньше A.
2) Если B не был в Оксфорде в марте 1920 года, то тот, кто выбирает первый, никогда не одалживал мне зонтик.
3) Если B или C выбирает вторым, то C выбирает раньше того, кто первым влюбился."

1. Обозначим ГАЛСТУК тех, кто видел Калибана в зеленом галстуке (например ГАЛСТУК=AB означет, что A,B видели, а C нет), ЗОНТИК тех, кто одалживал ему зонтик, а ВЛЮБИЛСЯ того, кто из них первый влюбился. Все время держим в уме, что "молодые A,B,C", которые решают задачу, знают в точности, кто из них ГАЛСТУК, ЗОНТИК и ВЛЮБИЛСЯ.

2. Если ГАЛСТУК это никто или все трое или только A, то первое условие лишнее, поэтому такого не может быть. Если ГАЛСТУК=BC, то из 1) неизбежно следует, что A первый, и тогда 2) не может дать дополнительной информации, т.е. лишнее. Значит, в ГАЛСТУК есть либо B, либо C (а также возможно A, но это ни на что не влияет).

3. Из 1) следует, что A не может быть последним, и это оставляет только четыре варианта: ABC, ACB, BAC, CAB. Вариант ABC противоречит 3), т.к. если B второй, то C не может быть последний. Остаются три варианта: ACB, BAC, CAB. Из них два с A на втором месте, один с A на первом месте. Мы еще никак не использовали 2) (для отброса вариантов порядка! Мы использовали 2) для рассуждений о ГАЛСТУК, но это не считается, потому что мы смотрим на ситуацию с точки зрения молодых A,B,C, которые уже знают ГАЛСТУК и теперь думают об условиях и пытаются найти порядок).

4. Понятно, что B не был в Оксфорде, потому что иначе 2) не дает никакой информации молодым A,B,C и является лишним. Теперь мы пытаемся понять, что могло быть в ЗОНТИК, чтобы молодые A,B,C могли с помощью знания ЗОНТИК выбрать ровно один вариант из оставшихся трех, но при этом не могли решить задачу, не используя 1) или 3). Тут проще становится, если помнить, что молодые A,B,C знают ГАЛСТУК, и поэтому им нужно только понять, на первом месте A или на втором. Если они знают, что на втором, то хотя для нас это оставляет два варианта CAB и BAC, для них есть только один, потому что они знают, в ГАЛСТУК B или C.

5. ЗОНТИК не может быть пустым или включать всех троих, потому что тогда условие лишнее. Если в ЗОНТИК есть A (и кто угодно еще), то A не первый, но тогда нам не нужно 3), которое мы использовали только для отвергания ABC. Мы и без него знаем, что A второй. Значит, в ЗОНТИК нет A. Если ЗОНТИК=BC, то A первый, но тогда из 3) сразу следует ACB и 1) лишнее. Остаются только две возможности: ЗОНТИК=B или ЗОНТИК=C.

6. Обратим внимание, что оба эти варианта оставляют в силе ACB, но ЗОНТИК=B отвергает BAC (потому что B не первый), а ЗОНТИК=C отвергает CAB. С другой стороны, ГАЛСТУК=B отвергает BAC (потому что B должен быть после A), а ГАЛСТУК=C отвергает CAB. Получается симметричная ситуация. Если ЗОНТИК и ГАЛСТУК это один и тот же человек, то из двух вариантов с A на втором месте они отвергают только один, и остается второй вариант плюс ACB. Если ЗОНТИК и ГАЛСТУК это разные люди, то вдвоем они отвергают оба варианта с A на втором месте, и остается только ACB.

7. Поскольку мы считаем, что задача составлена так, что молодые A,B,C могли ее решить, зная все факты, и поскольку мы использовали все условия, то ситуация, в которой ЗОНТИК и ГАЛСТУК один и тот же человек, не подходит: у них остаются два варианта и они не могут решить. Значит, ЗОНТИК и ГАЛСТУК это разные люди, и окончательный ответ ACB. При этом остается неясным, ЗОНТИК=B и ГАЛСТУК=C, или, наоборот, ЗОНТИК=C и ГАЛСТУК=B. Из условий задачи это невозможно выяснить. Зато из ответа ACB и 3) сразу ясно, что ВЛЮБИЛСЯ это B.

Без разбора возможных и невозможных вариантов фактов (про галстук, зонтик итд.) эта задача не решается. В этом ее главная прелесть и то, почему она мне так понравилась. В этом смысле она напоминает мне известную числовую задачу про возраста детей. Наверняка ее почти все знают, но напомню условие:

Страховой агент приходит к женщине и предлагает застраховать определенные предметы быта. Та отвечает, что у нее и без того слишком много денег уходит на трех дочерей, да и зарабатывает она не так много. После недлительных переговоров женщина все же соглашается застраховать несколько предметов при условии, что страховой агент разгадает возрасты всех ее трех дочерей. Первая подсказка: произведение возрастов всех трех дочерей равно 36. Вторая подсказка: сумма возрастов дочерей равна номеру дома, в котором живет женщина. Услышав вторую подсказку, страховой агент задумался и спустя несколько секунд попросил третью подсказку, так как предоставленной информации для него оказалось недостаточно. Третья подсказка: самая старшая дочь умеет играть на пианино. Каков возраст дочерей?

Я не буду давать решение - если вы не знаете эту задачу, очень советую подумать над ней, она тоже замечательная. Отмечу только, что тут тоже для решения задачи нужно вникнуть в ход мыслей человека, который знает больше, чем знаем мы. Страховой агент знает номер дома, а мы нет; но используя данные о том, когда он мог и не мог решить задачу, мы тоже ее решаем. Страховой агент в этой задаче - аналог "молодых A,B,C" в задаче про завещание Калибана. Но задача про Калибана еще более запутана и вывернута, потому что - благодаря "нет лишних условий" - нам нужно рассматривать больше разных версий "молодых A,B,C": не только таких, в которых они знают разные факты, но и таких, в которых они читают только условие 1+2, итд.

Мне кажется, что эта задачка заслуживает большей известности. Она интереснее и глубже всех типичных задач на "что следует из чего и кто говорит правду" - например, ста тысяч разных задач про расспрашивание жителей страны, которые всегда говорят правду или всегда лгут итд. - материала тысяч книг Смаллиана. Не то чтобы я не любил книги Смаллиана, нет, "Принцесса и тигр" была одной из любимых книг детства. Просто эта задачка заслуживает большей известности, по-моему.

Я обнаружил ее совершенно случайно, просматривая архив ее автора, умершего полвека назад математика Макса Ньюмана. В архив я зашел из чистого любопытства, а Ньюманом интересовался, потому что хотел найти цифровую копию его книги "Elements of the topology of plane sets of points" (не нашел). В архиве оказалась копия отпечатанного на машинке условия и решения задачи в формулировке Ньюмана, а также фрагменты переписки с Губертом Филлипсом, известным сочинителем и коллекционером задач, который опубликовал "Завещание Калибана" сначала в своей колонке в газете, а потом в сборнике "Caliban's Problem Book", который есть, кстати, в пиратских библиотеках.

Есть два интересных обстоятельства в формулировке самого автора (Ньюмана). Во-первых, он формулирует второе и третье условие не в виде "Если X, то Y", а в виде "Либо не-X, либо Y". Например, второе условие у него выглядит "Либо B был в Оксфорде тогда-то, либо выбирающий первым никогда не одалживал мне зонтик". Проблема, однако, в том, что под "либо то, либо это" Ньюман подразумевает "либо то, либо это, ЛИБО И ТО И ДРУГОЕ" - этого требует логика задачи. Но в обычном использовании фразы "либо... либо..." или "either... or..." по-английски, люди это так не понимают. Поэтому у Ньюмана есть примечание в том духе, что "или" следует понимать как включающее в себя возможность "и то и другое". Филлипс, когда готовил задачу Ньюмана к публикации, изменил формулировку на "если... то..." и на мой взгляд поступил правильно (хотя ненароком, очевидно, создал другую проблему с пониманием второго условия, о которой я написал выше). Филлипс также заменил A,B,C на имена/клички, выбранные наугад: какие-то Low, Y.Y. и 'Critic'. Мне это не понравилось и я оставил A,B,C в своей записи, следуя Ньюману.

Второ обстоятельство, более интересное, состоит в том, что сам Ньюман ошибочно считал, что из условий задачи можно определить ЗОНТИК, т.е. кто в точности одолжил зонтик Калибану, B или C. В его формулировке есть два вопроса: о порядке и о зонтике. В таком виде это было напечатано, и в газете и в книге, т.е. Филлипс не увидел ошибки у Ньюмана. Вы можете сами прочитать решение Ньюмана и убедиться в том, что в самом конце, когда он отвергает один из вариантов ЗОНТИКа, он неправ. Я ломал над этим голову добрый час, потому что все-таки он автор, да? Но в итоге убедил себя, что он неправ, и изменил вопрос на "кто влюбился" - у него есть точный ответ. Если вы не согласны и хотите обсудить этот вопрос подробнее, то я с удовольствием. Одно из немногих мест, где по-английски обсуждается эта головоломка в сети - страница Ричарда Хартера, ценителя головоломок. Он согласен со мной в том, что невозможно определить ЗОНТИК из условий задачи.

Наконец, после того, как я написал запись с задачей, мне сообщили, что в научно-популярной книге для детей "Волшебный двурог" (1949, автор Сергей Бобров, эта книга тоже есть в пиратских библиотеках) есть эта головоломка в русском переводе. По-видимому, многие в детстве читали эту книгу, но я должен признаться, что и не слышал о ней вообще до вчерашнего дня. В "Двуроге" изменили обстоятельства, перенесли действие в Испанию 18 века, вместо A,B,C дали звучные имена дон Альваро, дон Бенито и дон Висенте, итд. Но самое любопытное - слегла изменили условие, причем непонятно, специально или нет. Если перевести имена и обстоятельства из "Волшебного двурога" обратно в термины "Завещания Калибана", то в их варианте в условии номер 3) вместо "если B или C выбирает вторым", написано "если A или C выбирает вторым". Оказывается, что это приводит во-первых к другому ответу (ABC), а во-вторых дает однозначные ответы на все вопросы: кто одалживал зонтик, кто видел в галстуке итд. В книге дается подробный разбор решения (условие стр. 112, решение стр. 163 в издании 1967 года). Так что может и правильно это, что чуть изменили условие, и может действительно специально, чтобы получить недвусмысленные ответы на все вопросы. Но то, что нигде и намека нет на автора задачи, это не так уж хорошо, по-моему.

Flat | Top-Level Comments Only

From:

ivan-semushin.livejournal.com

Вопрос, который меня мучает: почему автор задачи назвал её героя Калибаном?

From:

avva.livejournal.com

Я хотел это упомянуть, но забыл, спасибo. "Калибан" было псевдонимом Губерта Филлипса, под которым он публиковал задачи и головоломки много лет в разных газетах. Очевидно, Ньюман назвал так задачу, потому что послал ее Филлипсу для публикации в его колонке. Поэтому и сборник, в котором Филлипс опубликовал задачу Ньюмана (и сотню других), называется "Caliban's Problem Book".

(...)

завещание калибана (решение и обсуждение, многобукв)

Page Summary

Style Credit

Expand Cut Tags