Чашечные весы и Теория информации

Для подавляющего большинства школьных задач существуют подробные алгоритмы решения: корни квадратного уравнения можно посчитать по готовым формулам, неравенства с модулем распадаются на две системы, а для операции дифференцирования существуют целые таблицы производных. Может показаться, что именно этим отличаются олимпиадные задачи от тех, которые решаются в классе: часто решение приходится подбирать с нуля для каждой «задачи повышенной сложности». Но так ли это на самом деле?

Наверное, многие из вас помнят еще с начальной школы задачи про чашечные весы. В самом простом варианте на весах не было делений, и нужно было определить один или несколько предметов, отличающихся по весу, за ограниченное количество взвешиваний. Или доказать, что это невозможно. А еще можно было найти минимальное число измерений, которые нужно провести, чтобы вне зависимости от результата каждого получить ответ на вопрос. Столько возможностей – и при этом оказывается, что ко всем поставленным задачам есть единый подход! Конечно, вывести формулу, сразу указывающую, например, на фальшивую монету, нам не удастся, но что, если мы посмотрим на задачу с точки зрения Теории информации?

Если нам даны весы без делений и гирь, то каждое взвешивание даст строго один из трех вариантов развития событий: предметы на левой чаше весов тяжелее, легче или равны по весу предметам на правой чаше. Говорят, что полученная информация сокращает неопределенность в три раза: это можно сравнить с тем, что мы узнали один разряд числа в троичной системе счисления. Например, невозможно за два взвешивания найти фальшивую среди десяти монет, ведь проведя два измерения мы сможем различить только 3 * 3 = 9 различных конфигураций, а вариантов ответа 10 – фальшивой может оказаться любая монета. Итак, способ доказывать утверждения вида «это невозможно» мы уже нашли!

Перейдем теперь от теории к практике. Допустим, для испытаний нам предоставлено 12 монет. Возможно, одна из них фальшивая – в этом случае ее нужно найти. Очевидно, что обойтись двумя взвешиваниями не получится, но возможно ли найти ответ за три измерения? На самом деле, возможных наборов выданных нам монет не так уж много: фальшивая монета может быть тяжелее или легче остальных, может идти под любым номером, и может вообще отсутствовать. Получится всего 2*12 + 1 = 25 возможных состояний, а благодаря трем измерениям мы можем различить 3*3*3 = 27 различных исходов. Теоретически, задача решаема, теперь нужно привести алгоритм поиска фальшивой монеты.

Давайте опишем его в виде таблицы: для каждой монеты и каждого взвешивания отметим 0 – если монеты на весах не было, 1 – если она оказалась на левой чаше весов и 2 – если на правой. Сразу отметим, что каждый раз на чашах и вне весов должно быть по 4 монеты – треть всего количества.

Для каждой монеты последовательность трех цифр должна быть уникальной: именно по ней мы будем искать монету, отличающуюся по весу. Спрашивается, а как же тройку значений «больше/меньше/равно», полученных измерениями, перевести в «код» монеты? Очень просто! Во-первых, если весы остались в равновесии, то в этом взвешивании фальшивая монета не участвовала – код 0. Во-вторых, рассмотрим два варианта: фальшивая монета может быть легче или тяжелее оставшихся. В первом случае перевес левой чаши весов будет кодироваться двойкой, а правой – единицей, и во втором случае – наоборот. Какой же вариант выбрать? Присмотритесь к таблице: кодов, полученных инвертированием единиц и двоек, в ней нет! Из двух полученных «переводов» в таблице окажется только один – так мы сможем узнать и то, в какую сторону отклоняется вес фальшивой монеты. Пусть первые два раза перевесила левая чаша, а в третий раз весы остались в равновесии: код 1-1-0 в таблице отсутствует, а значит монета номер 6 с кодом 2-2-0 – фальшивая, и она легче остальных. Алгоритм решения найден!

Точно таким же образом можно построить решение и для других параметров условия. Например, если нам не нужно находить относительный вес фальшивой монеты, то за k взвешиваний обнаружить подделку можно среди не более чем (3^k – 1) / 2 монет, а для (3^k – 3) / 2 монет получится выяснить еще и легче или тяжелее она окажется. Проверьте себя: среди какого количества монет удастся определить фальшивую, если она заведомо более легкая? Вот так и получается, что при решении математических задач будет полезен любой раздел науки, и теория информации – яркий этому пример.