Угадай, что я задумал

Обычно в подобных задачах стараются задавать «вопросы-сравнения», то есть «Верно ли, что твоё число меньше такого-то» (или «больше такого-то»). Однако Саше совершенно незачем ограничивать себя именно такими вопросами. Более общий тип вопросов выглядит так: Саша записывает любое множество чисел (в которое входят какие-то из чисел от 1 до 2013) и спрашивает Костю: «Верно ли, что ты задумал одно из этих чисел?».

Если бы Костя не мог ошибаться, то Саше хватило бы 11 вопросов (подумайте, почему). Значит, у Саши есть четыре вопроса «в запасе», и он должен постараться задавать вопросы так, чтобы если в какой-то момент ответы Кости стали противоречить друг другу, то дальше можно было угадывать число K стандартным образом, каждый раз деля пополам количество оставшихся вариантов.

Попробуйте придумать множества для первых 11 вопросов Саши так, чтобы после ответов на них Саша мог оставить в «списке подозрительных» только 12 чисел — одно при условии, что Костя ещё не ошибался, и ещё по одному числу на каждую возможную ошибку Кости.

Сначала сделаем то, что было предложено в подсказке 3.

Проще всего для этого воспользоваться двоичной системой. Поскольку 2013 меньше, чем 2¹¹ = 2048, то двоичная запись любого из возможных задуманных чисел содержит не более 11 разрядов. Поскольку цифра в каждом разряде — это 0 или 1, то Саша может первыми вопросами непосредственно спрашивать: «Верно ли, что цифра в i-м (справа) разряде двоичной записи задуманного числа равна 1?», последовательно перебирая все i от 1 до 11.

Если Костя не ошибётся в ответах ни на один из этих вопросов, то Саша выяснит все разряды задуманного числа, то есть узнает число K (правда, поскольку он не знает, ошибался ли Костя, то он не может сделать вывод о том, что он знает задуманное число). Если же Костя ошибётся в ответе на какой-то вопрос, это будет значить, что задуманное число K отличается от данных Костей ответов в каком-то одном разряде. Но такое число тоже только одно — и так как ошибка могла быть сделана в любом из 11 разрядов, то имеется ещё ровно 11 подозрительных чисел.

Обозначим 12 чисел из полученного списка K₀, K₁, ..., K₁₁ (первое — при отсутствии ошибок, остальные — при ошибке в ответе на соответствующий вопрос).

Как теперь должен действовать Саша? Если он задаст следующий вопрос (см. подсказку 1 о структуре вопросов) про множество из d чисел (всё равно каких, но не включающих K₀; например, K₁, ..., K_d) и получит ответ «да», это может означать одно из двух: либо загадано действительно одно из этих d чисел, либо Костя ошибся в ответе на этот вопрос. Но если Костя ошибся, то он мог загадать только K₀, потому что остальные варианты K_d+1, ..., K₁₁ означают, что Костя уже ошибался в ответе на какой-то из предыдущих вопросов, а второй ошибки он допустить не может! Значит, при ответе «да» у Саши остаётся ровно d + 1 вариантов, причём он точно понимает, что в одном из предыдущих ответов Костя ошибся. Поскольку после этого вопроса у Саши остаются в запасе ещё 3 вопроса, он сможет угадать задуманное число из 8 вариантов. Поэтому можно положить d + 1 = 8, то есть d = 7, и рассмотреть только ответ «нет» на 12-й вопрос.

Ответ «нет» означает, что Костя действительно не мог задумать числа K₁, ..., K₇ (иначе это было бы второй его ошибкой). Значит, после такого ответа список подозрительных чисел уменьшился до 5: K₀, K₈, K₉, K₁₀, K₁₁. Рассуждая так же, как выше, убедимся, что 13-м вопросом Саша может спрашивать про числа K₈, K₉, K₁₀: в случае ответа «да» он должен будет угадать одно из четырёх чисел K₀, K₈, K₉, K₁₀, для чего ему хватит двух оставшихся вопросов, а в случае ответа «нет» в списке подозрительных останутся только K₀ и K₁₁.

Теперь (14-м вопросом) достаточно спросить про одно число K₁₁. Как и в разобранных выше ситуациях, ответ «да» будет означать, что Костя уже точно ошибался, — и тогда Саша угадает одно из двух чисел за последний, 15-й, вопрос. Ну а после ответа «нет» 15-го вопроса можно уже и не задавать — Саша может сразу сделать вывод о том, что Костя задумал K = K₀.

1. Можно ли было обойтись без применения двоичной системы? Да, несомненно.

Заметим, что в каждый момент «игры» между Костей и Сашей ситуация («состояние игры») полностью описывается двумя числами [a; b]: a — количество чисел, которые мог загадать Костя при условии, что он ещё не делал ошибок, а b — количество чисел, которые Костя мог загадать при условии, что он допустил уже ошибку в одном из предыдущих ответов. Игра начинается из состояния [2013; 0], а закончиться должна в тот момент, когда «подозреваемое» число осталось единственным — то есть либо на состоянии [1; 0], либо на [0; 1].

Пусть первый вопрос Саши относился ко множеству из d чисел. Тогда после ответа «да» новым состоянием игры стало [d; 2013 – d], а после ответа «нет» — [2013 – d; d] (подумайте, почему это так). Если Саша разделит множество из 2013 чисел на две почти равных части, то он получит одно из состояний [1007; 1006] и [1006; 1007]. Вторым вопросом он может разделить пополам каждую из этих частей — и получить либо [504; 1006], либо [503; 1007] (здесь 1007 чисел получаются следующим образом: во-первых, это те 504 числа из b = 1007, которые Саша включил в своё множество, а во-вторых, это те 503 чисел из a = 1006, которые он во множество не включил — но если Костя допустил ошибку при ответе на этот вопрос, то эти числа могли быть им загаданы).

Продолжая задавать вопросы таким же образом, получаем последовательно

[504; 1006] → [252; 755] → [126; 504] → [63; 315] → [32; 189] → [16; 111] → [8; 64] → [4; 36] → [2; 20] → [1; 11]

(или [503; 1007] → [251; 755], что меньше, чем в вышеприведенной цепочке. Еще несколько аналогичных вариантов в этой цепочке я сразу позволил себе опустить.)

Таким образом, к описанной в нашем решении ситуации «1 + 11» можно было прийти и безо всяких упоминаний двоичной системы. Ну а дальше [1; 11] → ([1; 4] или [0; 8]) → ([1; 1] или [0; 4]) → ([1; 0] или [0; 2]) → [0; 1].

2. Наше решение демонстрирует, что вместо чисел от 1 до 2013 Саша мог позволить Косте загадывать числа от 0 до 2047, и всё равно уложиться с угадыванием за 15 вопросов. Однако оно оставляет без ответа очень естественный обобщающий вопрос. Пусть Саше разрешено задавать не 15, а N вопросов. В каком диапазоне (от 0 до M) он может разрешить Косте загадывать числа, чтобы этих вопросов хватило для гарантированного угадывания?

Полный ответ на этот вопрос (точнее, доказательство верности этого ответа) далеко не так прост, как кажется на первый взгляд. Его можно записать так: если (здесь [x] — целая часть числа x, то есть наибольшее целое число, не превосходящее x) чётно, то M = s, а если s нечётно, то M = s – 1. Небезынтересно и то, что от момента постановки задачи до получения полного её решения прошло более 20 лет!

По-видимому, впервые задачу угадывания с возможностью совершать ошибки в ответах сформулировал замечательный венгерский математик Альфред Реньи в статье 1961 года на венгерском языке. Спустя несколько лет (в своей автобиографии «Приключения математика») её популяризовал американский математик Станислав Улам.

«Мы с Хокинсом [Дэвид Хокинс, философ, впоследствии автор замечательной научно-популярной книги «Язык природы». — Прим. авт.] размышляли над следующей связанной с этим задачей: вариация игры «Двадцать вопросов». Один человек задумывает число в интервале от единицы до одного миллиона (который как раз меньше, чем 2²⁰). Другому человеку позволяется задать до двадцати вопросов, на каждый из которых первый участник должен отвечать только «да» или «нет». Очевидно, что число можно угадать, если сначала спросить: это число в первой половине миллиона? В следующем вопросе опять ополовинить получившийся интервал чисел и так далее. В конечном итоге, число можно угадать менее чем за log₂1000000 раз. Предположим теперь, что участник имеет право солгать один или два раза. Сколько вопросов потребуется, чтобы получить верный ответ? Ясно, что для того, чтобы угадать одно из 2ⁿ чисел, требуется более n вопросов, поскольку о том, когда была сказана ложь, неизвестно. В общем виде эта задача не решена».

Полное решение задачи Улама для случая одной ошибки было получено Анджеем Пельцем в 1986 году, а для двух ошибок — в 1990 году. Еще через 10 лет математикам удалось полностью решить задачу для «права на три ошибки». Для задач с большим числом ошибок решены только отдельные частные случаи, а полных решений пока не найдено.

3. Если не требовать оптимальных решений и минимального числа вопросов, то всё становится намного проще. Так, в 1991 году на Всесоюзной олимпиаде по математике предлагалась следующая задача (авторы — А. Анджанс, И. Соловьев, В. Слитинский.)

Следователь придумал план допроса свидетеля, гарантирующий раскрытие преступления. Он собирается задавать вопросы, на которые возможны только ответы «да» или «нет» (то, какой вопрос будет задан, может зависеть от ответов на предыдущие). Следователь считает, что все ответы будут верными, он подсчитал, что при любом варианте ответов придётся задать не более 91 вопроса. Докажите, что следователь может составить план не более чем со 105 вопросами, гарантирующий раскрытие преступления и в случае, если на один вопрос может быть дан неверный ответ (но может быть, что все ответы верные).

Решение этой задачи было основано на другой идее: как можно модифицировать исходный план вопросов, добавляя в него «контрольные вопросы». Сначала следователь задаёт первые 13 вопросов первоначального плана, а потом задаёт 14-й вопрос «Солгали ли Вы в предыдущей серии вопросов?». Получив ответ «нет», он может продолжать задавать серии из 12, 11, 10, ..., 1 вопросов плана, повторяя контрольный вопрос после каждой серии (подумайте, почему ответ «нет» на контрольный вопрос гарантирует, что ответы на вопросы серии действительно были верными). Если же на какой-то из контрольных вопросов получен ответ «да», то повторяется вся предыдущая серия, при этом больше контрольных вопросов можно не задавать. Если ответ «да» получен на k-й контрольный вопрос, то сверх исходного плана придётся задать k + (14 – k) = 14 вопросов. Отметим, что ложь могла быть и в ответе на контрольный вопрос — в этом случае ответы на повторно заданную серию будут точно такими же, как и в первый раз.

Почему «модификация плана» не является оптимальной стратегией и не гарантирует минимальности числа заданных вопросов? Например, потому, что исходная задача следователя была равносильна угадыванию задуманного числа из диапазона от 0 до 2⁹¹ – 1. Но для этого, как мы уже знаем, хватает не 105, а всего 98 вопросов: 2⁹⁸/99 > 2⁹⁸/2⁷ = 2⁹¹. Тем не менее предложенная в олимпиадной задаче модификация увеличивает длину плана из N(N – 1)/2 вопросов не более чем на N, то есть на величину порядка квадратного корня из удвоенной исходной длины. Что, в общем, тоже не так и плохо.

4. Почему серьёзные математики вообще занимаются такими «игрушечными» задачками? Дело в том, что эта задача очень близка к классическим задачам теории кодирования и тесно связана с ними (см.: Обнаружение и исправление ошибок, Код Хэмминга). Действительно, в описанной нами игре Костя и Саша могут заранее (до выбора Костей задуманного числа) договориться о списке задаваемых вопросов (в том числе — договориться о том, какой вопрос будет задан вторым при ответе «да» на первый вопрос, а какой — при ответе «нет», и аналогично договориться про следующие вопросы). Это означает, что Костя может просто послать Саше последовательность из 15 ответов — или, если угодно, последовательность из 15 символов «0» и «1». По каждой такой последовательности Саша сможет отгадать («реконструировать») задуманное Костей число, а значит — определить, в ответе на какой вопрос Костя ошибся. Это и есть код Хэмминга, исправляющий одну ошибку.

Статья Р. Хэмминга «Коды, обнаруживающие и исправляющие ошибки» была опубликована в 1950 году (оригинал можно увидеть, например, здесь, PDF, 3,1 Мб). В то время исходные данные в компьютеры загружались с помощью перфокарт, и устройства ввода перфокарт были настолько ненадёжными, что практически никакая достаточно толстая колода не считывалась без ошибок. Запуск программы, содержащей ошибку, приводил в лучшем случае к сбою, после которого вычисления останавливались и колоду приходилось считывать ещё раз, а в худшем — к полной остановке машины. Придуманные Хэммингом коды позволяли не только обнаруживать ошибки, но и автоматически исправлять их. Это была настоящая революция!

С тех пор, конечно, надёжность компьютерных систем возросла многократно, однако коды, исправляющие ошибки, не стали от этого менее востребованными: ныне они составляют основу протоколов передачи сигналов по линиям связи. Когда-нибудь наверняка линии связи тоже усовершенствуются, однако необходимость в корректирующих кодах вряд ли когда-нибудь исчезнет: ошибки — вечные спутники любой человеческой деятельности.