Петя задумал целое число от 1 до 16. Вася может задавать Пете любые вопросы, на которые можно ответить «Да» или «Нет».
а) (2 балла) Как Васе узнать Петино число, задав не более 4 вопросов, если Петя отвечает правдиво?
б) (4 балла) Известно, что, отвечая на вопросы, Петя может один раз соврать (но неизвестно, когда; а может и не врать). Как Васе узнать Петино число, задав не более 7 вопросов?

Решение

а) Как узнать число за 4 вопроса, если Петя всегда говорит правду?

Всего Петя мог загадать 16 различных чисел. Каждый вопрос, на который можно ответить только «Да» или «Нет», позволяет разделить оставшиеся варианты на две группы.

Поэтому Вася может каждый раз делить множество возможных чисел пополам.

Первый вопрос: «Твоё число больше 8?»

• Если «Да», то число находится среди 9, 10, ..., 16.

• Если «Нет», то число находится среди 1, 2, ..., 8.

После первого вопроса остаётся 8 вариантов.

Второй вопрос: Вася снова делит оставшиеся числа пополам. Например, если число от 1 до 8, он спрашивает: «Твоё число больше 4?»

После второго вопроса остаётся 4 варианта.

Третий вопрос: Вася опять делит оставшиеся числа пополам. Остаётся 2 варианта.

Четвёртый вопрос: Вася спрашивает, какое из двух оставшихся чисел задумал Петя.

Таким образом, после четырёх вопросов Вася точно узнает число.

Это можно представить так:

Ответ к пункту а): достаточно 4 вопросов, каждый раз делящих оставшиеся варианты пополам.

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

Здесь предыдущий способ уже не подходит, потому что один неправильный ответ может направить Васю по неверному пути.

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

Шаг 1. Запишем число в двоичном виде.

Вася мысленно вычитает из Петиного числа единицу. Полученное число от 0 до 15 можно записать четырьмя двоичными цифрами:

где каждая цифра равна 0 или 1.

Например, если Петя загадал 11, то

Значит, $x_1=1,\ x_2=0,\ x_3=1,\ x_4=0$.

Шаг 2. Вася задаёт 7 вопросов.

Первые четыре вопроса позволяют узнать двоичные цифры:

1. Равна ли $x_1$ единице?

2. Равна ли $x_2$ единице?

3. Равна ли $x_3$ единице?

4. Равна ли $x_4$ единице?

Следующие три вопроса нужны для проверки ответов:

5. Является ли сумма $x_1+x_2+x_4$ нечётной?

6. Является ли сумма $x_1+x_3+x_4$ нечётной?

7. Является ли сумма $x_2+x_3+x_4$ нечётной?

Все эти вопросы допускают ответы «Да» или «Нет».

Шаг 3. Проверим ответы и найдём возможную ложь.

Обозначим каждый ответ цифрой: «Да» — 1, «Нет» — 0.

Пусть Вася получил ответы $a_1,a_2,\ldots,a_7$.

Он выполняет три проверки: