Недавно я предложил своим студентам STEP задачу из нашего старого вступительного теста PRIMES 2014 года.
Головоломка. Тайное число Джона находится в диапазоне от 1 до 216 включительно, и вы можете задавать ему вопросы, на которые он отвечает «да» или «нет», но он может солгать в ответ на один из вопросов. Объясните, как определить его число за 21 вопрос.
Стандартное решение. Мы начинаем с того, что просим Джона перевести его число в двоичную систему и добавить нули в начале, если это необходимо, чтобы результат стал двоичной строкой длиной 16. Для первых 15 вопросов мы делаем следующее: для вопроса i мы спрашиваем: «Является ли i-я цифра вашей строки нулём?» Для вопроса 16 мы спрашиваем: «Вы лгали в ответ на предыдущий вопрос?»
Если он лгал на предыдущий вопрос, он должен сказать «ДА». Если нет, он может солгать на вопрос 16 и также сказать «ДА». В любом случае, если ответ «НЕТ», он не лгал на первые 15 вопросов, и мы знаем первые 15 цифр числа. Затем мы спрашиваем о последней цифре три раза, и ответ, данный хотя бы дважды, является правильным, так что мы знаем число.
Если ответ на вопрос 16 — «ДА», то он солгал на один из вопросов 1–16. С этого момента он должен говорить правду, поскольку уже солгал. Мы используем бинарный поиск (4 вопроса), чтобы определить, на какой вопрос он солгал. Это сообщит нам первые 15 цифр, и мы можем использовать 21-й вопрос, чтобы найти последнюю цифру.
Нестандартные решения
Один из моих студентов, Таниш, придумал оригинальное решение, которое использует 18 вопросов. Идея состоит в том, чтобы заставить Джона солгать в первых двух вопросах, а затем безопасно провести бинарный поиск.
Он предложил задать следующие два вопроса: «Собираешься ли ты ответить «НЕТ» на следующий вопрос?» и «Ты ответил «ДА» на предыдущий вопрос?» Читатель может проверить, что, как бы Джон ни ответил, он вынужден солгать ровно один раз.
Другой студент, Вивек, предложил похожую идею, но использовал только один вопрос, чтобы заставить Джона солгать: «Скажешь ли ты «НЕТ» на этот вопрос?» 🧠