От 1 до 16

*

Сложность: 

За какое наименьшее число вопросов можно угадать задуманное число между 1 и 16, если один раз отвечающий имеет право соврать? (Вопросы должны предполагать лишь ответы «да или «нет».)

Решение

Задуманное число можно угадать за 7 вопросов. Сделать это можно, например, следующим образом. Запишем числа от 1 до 16 в двоичной системе исчисления, приписав, если это необходимо, спереди несколько нулей, чтобы получилось четырёхзначное число. Числу же 16 поставим в соответствие четвёрку нулей.

Пусть загадано число abcd, где каждая буква обозначает 0 или 1. Зададим сначала 4 вопроса, выясняющие чётность соответствующей цифры. Пятым сформулируем следующий вопрос: чётна ли сумма первых трёх цифр?

Если ответ совпадает с уже известным нам значением, то вранья ещё не было, все эти три цифры верны, и за оставшиеся два вопроса мы с гарантией уточним значение четвёртой цифры.

Если же ответ разойдётся, то один из ответов ложен. Тогда мы выясним чётность суммы первых двух цифр. При совпадении уточняем цифру c. При расхождении (при этом ясно, что обман произошёл, когда мы выясняли одну из этих первых двух цифр), задаётся вопрос о чётности первой цифры.

Покажем, что за 6 вопросов угадать задуманное число нельзя. После 6 вопросов мы получаем последовательность из шести «да» и «нет», то есть всего 64 различные комбинации. Каждой такой комбинации соответствует одно из чисел от 1 до 16. При этом каждому такому числу соответствует 7 наборов (одна «правдивая» комбинация, и шесть «лживых», содержащих один неправильный ответ). Но 16 × 7 > 64, то есть существуют комбинации, соответствующие сразу нескольким числам. Это означает, что шести вопросов недостаточно для однозначного угадывания числа.




Комментарии

Что за ерунда? зачем так сложно и так долго? легко и за 4 хода=)

my sisters actually get better tips when they do little things like draw a happy face on the bill. It makes it more pezronalised and people tend to tip better.

Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.