"Да" и "нет" не говорите
АрхивНынешние времена кардинально изменили досуг детей. Раньше несколько младших школьников, собравшись вместе на какой-нибудь домашний праздник, почти наверняка начинали рассказывать друг другу страшилки, анекдоты, играть в настольные игры или демонстрировать нехитрые фокусы, которым их научили родители. Теперь же дети норовят усесться поближе к видику или компьютеру. А меня тянет рассказать о задачах, некоторые из которых я узнал еще в детском возрасте и был поражен ими настолько, что помню до сих пор. Может быть, они пригодятся и нынешним родителям: "Братья Пилоты" - это, конечно, хорошо, но в меру…
Задача 1
Я задумал число: единицу, двойку или тройку. Попробуйте угадать его, задав мне только один вопрос и получив от меня ответ "да" или "нет".
- Но это же невозможно, - скажете вы.
- Правильно, невозможно. А почему?
Пока вы задумались над этим "почему", прочтите другую историю.
Задача 2
У одного человека был подвал, освещавшийся тремя электрическими лампочками. Выключатели этих лампочек находились вне подвала, так что, включив любой из выключателей, хозяин должен был спуститься в подвал, чтобы увидеть, какая именно лампочка зажглась. Однажды он придумал способ, как определить для каждого выключателя, какую именно лампочку он включает, сходив в подвал ровно один раз.
- Но это тоже невозможно! - скажете вы… и ошибетесь.
Способ такой: включить один из выключателей, подождать несколько минут, выключить его, тут же включить другой и спуститься в подвал. Из трех ламп горела, конечно, одна - соответствующая второму выключателю. Но одна из двух остальных ламп нагрелась!
Почему же то, что было невозможным в математической задаче, оказалось осуществимым в "физическом эксперименте" - в задаче с лампочками? Удивительно, но факт: ответ на этот вопрос дает не физика и не классическая математика, а теория информации.
Оба решения - и доказательство невозможности угадывания в первой задаче, и идею решения второй задачи - можно получить из очень простого равенства: 1 бит информации = 2 варианта.
Мой ответ "да" или "нет" на ваш вопрос - это один бит, один "квант" информации. Как бы вы ни построили свой вопрос, но два варианта ответа на него делят множество "подозреваемых" чисел на две части. Одна из этих частей будет благодаря моему ответу отброшена. Но оставшаяся часть может содержать два числа, которые при этом оказываются неразличимыми!
А что произошло в эксперименте с лампочками? Один спуск в подвал мог дать хозяину только один бит информации ("горит"/"не горит"), а ему было нужно распознать три возможных случая. Иначе говоря, две негорящие лампочки были для него неразличимыми. Хозяин, воспользовавшись физикой, нашел второй бит информации - "теплая"/"холодная". Теперь теоретически возможны 4 случая, а на практике - 3 (не бывает горящей, но холодной электрической лампочки накаливания), что и решило проблему.
Задача 3
У вас есть четыре гири и двухчашечные весы без стрелки. Сколько всего различных по весу грузов можно точно взвесить этими гирями?
Ответ на эту задачку зависит от того, разрешается ли класть гири на обе чашки весов. Если нет, то можно взвесить 16 разных грузов, если да - то 40.
Почему так? Давайте снова разбираться в этом, привлекая биты.
В первом случае, чтобы определить вес груза, уравновешенного гирями, для каждой гири надо знать ровно один бит информации - лежит она на весах или нет. А для четырех гирь - 4 бита, то есть 16 вариантов. Значит, каковы бы ни были гири, больше 16 грузов взвесить все равно нельзя. Осталась самая малость - понять, можно ли найти такие гири, которые позволят взвесить именно 16 вариантов. К счастью, таких наборов гирь очень много. Самый известный из них - 1, 2, 4 и 8 (например, килограммов).
Теперь можно разобраться и со вторым случаем. Сколько существует вариантов, если гири разрешается класть на обе чаши весов? Для каждой гири теперь имеется ровно три варианта: "положить на левую чашу", "положить на правую чашу", "не класть ни на одну из чаш".
Соответственно, для четырех гирь - 81 вариант. Откуда же берется ответ "40"? Во-первых, один вариант надо сразу отмести: если ни одна гиря на весах не лежит, то ничего и не взвешивается. (Если хотите, можно считать, что взвешен нулевой груз, хотя это и звучит странно.)
Во-вторых, все остальные варианты дублируются: ведь от перемены мест всех гирь на весах (если переложить гири с левой чаши на правую и наоборот) равенство на весах не изменяется.
Таким образом, оставшиеся восемьдесят вариантов соответствуют именно сорока различным грузам.
А теперь попробуйте такой орешек.
Задача 4
Я задумал число: 1, 2 или 3. Вы задаете мне один вопрос, на который я могу ответить "да", "нет" или "не знаю". Сможете ли вы угадать число, задав всего один вопрос?
Поразительно, но трудность этой задачи совершенно не зависит ни от возраста решающего, ни от его образования. Я видел маленьких детей, которые щелкали ее за пару минут, и наблюдал совсем неглупых взрослых, которые так и не смогли справиться с нею…
Вот один из возможных вопросов: "Представь, Константин, что я тоже задумал одно из этих трех чисел, причем не то, которое задумал ты. Мое число больше твоего?"
Если я задумал единицу, то непременно отвечу "да". Если я задумал тройку, то отвечу "нет". А если мною задумана двойка, то я вынужден сказать "не знаю", потому что действительно не знаю ответа!
Задача 5
Я задумал число от 1 до 200. За какое наименьшее число вопросов вы сможете его отгадать, если я отвечаю на каждый вопрос только "да" или "нет"?
Ответ: восемь. За меньшее число вопросов угадать не удастся, потому что семь вопросов позволяют различить только 128 вариантов. Ну, а способ отгадывания числа за восемь вопросов достаточно банален и известен.
Первый вопрос может быть, например, таким: "задуманное число больше ста?"
Задача 6
Я задумал число от 1 до 200. За какое наименьшее число вопросов вы сможете его отгадать, если я отвечаю на каждый вопрос "да", "нет" или "не знаю"?
Можно угадать за пять вопросов, хотя способ угадывания здесь намного более сложен, чем в предыдущей задаче.
В конце сюжета, как обычно, привожу еще пару задач без решений. Это, так сказать, закуска для гурманов.
Задача 7
Как и раньше, задумывается число от 1 до 200, а загадавший отвечает на вопросы "да" или "нет". При этом ровно один раз (за все ответы) он имеет право соврать. Сколько теперь понадобится вопросов для того, чтобы отгадать задуманное число?
Можно, конечно, каждый вопрос задавать дважды, и если ответы не совпали, то повторить этот же вопрос в третий раз. Этот способ требует 8х2+1=17 вопросов. Сможете ли вы придумать более экономный способ?
Задача 8
На постоялом дворе остановился путешественник, и хозяин согласился в качестве уплаты за проживание брать кольца золотой цепочки, которую тот носил на руке. Но при этом поставил условие, чтобы оплата была ежедневной: каждый день должно быть отдано ровно на одно кольцо больше, чем в предыдущий день. Цепочка содержала 11 колец, а путешественник собирался прожить ровно 11 дней, поэтому он согласился. Какое наименьшее число колец он должен распилить, чтобы иметь возможность платить хозяину?
Пишите мне по адресу kk@knop.spb.ru. Я постараюсь ответить на все пришедшие письма.
