Проблема общего знания. Часть 1

Задача о дне рождения Шерил

Несколько лет назад эта логическая задача с Сингапурской математической олимпиады стала невероятно популярной в интернете и поставила в тупик миллионы людей по всему миру. Сможем ли мы ее решить? Вот условие:

Альберт и Бернард дружат с Шерил и хотят узнать, когда у нее день рождения. Шерил дает им список из 10 возможных дат:

15 мая, 17 июня, 14 июля, 14 августа

16 мая, 18 июня, 16 июля, 15 августа

19 мая, 17 августа

Затем Шерил по отдельности сообщает Альберту месяц своего рождения, а Бернарду - число. После этого происходит следующий разговор.

Альберт: Я не знаю, когда у Шерил день рождения, но знаю, что Бернард тоже этого не знает.
Бернард: Сначала я не знал, когда у Шерил день рождения, но теперь знаю.
Альберт: Тогда теперь и я знаю, когда у Шерил день рождения.

Когда у Шерил день рождения? Попробуйте решить задачу самостоятельно, прежде чем читать дальше. Десятки тысяч людей в интернете уже справились с ней, и я уверен, что, хорошенько поразмыслив, вы тоже сможете ее решить. Уделите ей достаточно времени и внимания - задача того стоит.

Отступление

С возвращением. Удалось решить задачу?

Объясню, как я сам о ней рассуждаю. Сначала Альберт знает только месяц, а Бернард - только число. И чтобы явно проговорить то, что подразумевается: будем считать, что это является общим знанием между ними. Альберт начинает с того, что говорит, что не знает, когда у Шерил день рождения. Что ж, разумеется, он этого не знает, ведь изначально ему известен только месяц, а в каждом месяце в списке есть несколько возможных дат.

Но затем Альберт говорит нечто интересное: он также знает, что Бернард тоже не знает дату рождения. Если посмотреть на таблицу возможных дат, то Бернард мог бы сразу точно определить день рождения только в том случае, если бы ему назвали число 18 или 19, поскольку каждое из этих чисел встречается в списке лишь один раз. Все остальные числа встречаются в нескольких датах. Поэтому, когда Альберт говорит, что знает, что Бернард не знает ответа, это означает, что информация Альберта несовместима с тем, чтобы Бернарду сообщили 18 или 19. Следовательно, Альберту не могли сообщить май или июнь. Значит, он знает, что месяц - либо июль, либо август.

Бернард говорит, что сначала не знал, когда у Шерил день рождения, но теперь знает. Значит, число не может быть 14, потому что в таком случае Бернард по-прежнему не смог бы определить дату: 14-е встречается и в июле, и в августе. Поэтому остаются только 16 июля, 15 августа или 17 августа, и Бернард знает ответ, потому что ему сообщили одно из этих чисел.

Наконец, Альберт говорит, что теперь тоже знает дату рождения Шерил. Отсюда следует, что ему не могли сообщить август, потому что тогда он не смог бы понять, идет ли речь о 15 августа или о 17 августа. Значит, Альберту сообщили июль, а следовательно, день рождения Шерил - 16 июля. На этом задача решена.

Вариация задачи о дне рождения Шерил

Рассмотрим придуманную мной вариацию этой задачи. На следующих выходных Альберт, Бернард и Шерил снова встречаются, чтобы продолжить беседу. Шерил по секрету сообщает Альберту и Бернарду по одному положительному целому числу из множества 1, 2, 3 и так далее.

Шерил: Я дала каждому из вас разные положительные целые числа. У кого число больше?
Альберт: Я не знаю.
Бернард: Я тоже не знаю.
Альберт: Я по-прежнему не знаю, у кого число больше.
Бернард: Увы, я все еще не знаю.
Альберт: А, вот теперь, после твоих слов, я вдруг понял, у кого число больше!
Бернард: Правда? Тогда я знаю оба числа!
Альберт: А теперь и я знаю оба числа.
Какие числа дала им Шерил?

Отступление

Давайте решим эту задачу вместе. У Альберта и Бернарда разные положительные целые числа - 1, 2, 3 и так далее, причем числа могут быть сколь угодно большими. Кроме того, оба знают это условие, знают, что другой тоже его знает, и так далее, поскольку Шерил объявила его достаточно ясно, то есть оно является общим знанием.

Когда Альберт начинает с того, что говорит, что не знает, у кого число больше, это означает, что у него не 1. Ведь если бы у него была 1, он сразу знал бы, что число Бернарда больше. Но, по сути, это все, что мы пока можем заключить о его числе: если бы у него было любое число, отличное от 1, он не мог бы знать, меньше или больше число Бернарда.

Когда Бернард отвечает, что он тоже не знает, аналогичным образом следует, что у Бернарда не 1. Более того, у него не может быть и 2, поскольку он уже знает, что у Альберта не 1.

Затем Альберт говорит, что по-прежнему не знает, у кого число больше. Это означает, что у Альберта не может быть ни 2, ни 3, поскольку в этих случаях он уже смог бы определить ответ. А после того как Бернард объявляет, что все еще остается в неведении, мы заключаем, что у Бернарда не может быть ни 3, ни 4.

И вот теперь Альберт внезапно заявляет, что знает, у кого число больше. Как он мог это узнать? У него должно быть либо 4, либо 5. В самом деле, имея одно из этих чисел, он понимает, что число Бернарда больше, поскольку варианты 1, 2, 3 и 4 для Бернарда уже исключены. Но если бы у Альберта было число больше 5, он не мог бы знать, что у Бернарда не 5, и потому по-прежнему не знал бы, у кого число больше. Итак, у Альберта либо 4, либо 5, хотя пока мы не знаем, какое именно.

Наконец, Бернард говорит, что теперь знает оба числа. Чтобы это стало возможным, у него должно быть одно из чисел 4 или 5, чтобы тем самым исключить его как возможное число Альберта. Но мы уже установили, что у Бернарда не может быть 4. Следовательно, у него 5. Значит, у Альберта 4, а у Бернарда 5. Когда Альберт говорит, что теперь тоже знает оба числа, он просто проводит то же рассуждение, которое только что провели мы.

Вариация с обратными величинами

Предположим, что Алисе и Бобу дают по одной различной дроби вида 1/n, где n - положительное целое число. При этом для них является общим знанием, что каждый знает только свое число и что эти числа различны. После этого происходит следующий разговор.

Д. Хэмкинс: Я по отдельности дал каждому из вас разные рациональные числа вида 1/n. У кого число больше?
Алиса: Я не знаю.
Боб: Я тоже не знаю.
Алиса: Я все еще не знаю.
Боб: А вот теперь я вдруг понял, у кого число больше.
Алиса: В таком случае я знаю оба числа.

Какие числа им дали?

Когда Алиса в своей первой реплике говорит, что не знает ответа, это означает ровно то, что у нее не 1/1, поскольку только в этом случае она могла бы знать, у кого число больше. Когда после этого Боб отвечает, что тоже не знает, отсюда следует, что у него также не 1/1, но, кроме того, у него не 1/2. Ведь в любом из этих двух случаев он знал бы, что именно у него большее число, тогда как при любом другом числе он не мог бы быть в этом уверен.

Алиса отвечает, что все еще не знает. Содержание этой реплики состоит в том, что у нее нет ни 1/2, ни 1/3, поскольку именно в этих случаях, и только в них, она уже могла бы определить, у кого число больше.

Боб отвечает, что теперь внезапно знает, у кого число больше. Это возможно только в том случае, если у него либо 1/3, либо 1/4, поскольку в обоих случаях именно его число было бы больше. Но пока мы еще не можем определить, какое именно из этих двух чисел у него.

Однако когда Алиса говорит, что теперь знает оба числа, это должно означать, что имеющаяся у нее информация позволяет различить две оставшиеся возможности для числа Боба. Если бы у нее было 1/5 или меньше, она не смогла бы различить эти два варианта. Следовательно, у нее должно быть 1/4, поскольку 1/3 для нее уже исключено нашим предыдущим рассуждением.

Итак, у Алисы 1/4, а у Боба 1/3.

Проблема общего знания. Часть 2