Испытания для барона М.

Квант 2025, №5-06 с. 39-42 Тег YMZW

МАТЕМАТИЧЕСКИЙ КРУЖОК

К.КНОП

ВСАМОМ СТАНДАРТНОМ СЮЖЕТЕ задач о взвешиваниях есть весы (или иной прибор) и задана какая-то информация о неизвестных объектах (монетах). Например, говорится, сколько среди них «фальшивых» монет, а также сообщается, легче ли они, чем настоящие монеты (или сказано, что могут быть не только легче, но и тяжелее). Однако есть отдельный класс задач, в котором ко всему этому прибавляется мощнейший инструмент – честнейший эксперт барон М., который знает все необходимое про все монеты. Главная трудность – барон должен строго доказать всю известную ему информацию с помощью взвешиваний. А так как весы – традиционный символ Фемиды, то второй персонаж в таких задачах – судья. Судье известна часть информации из условия задачи, но не вся информация, известная эксперту. Какие же испытания предстоят барону в таких доказательных упражнениях? Какая математика стоит за этим? Не претендуя на полный охват всех возможных задач, остановимся на некоторых из них.

DOI: https://doi.org/10.4213/kvant20250504

Испытание 1. Неинтересное У барона М. имеются 12 монет. Половина из них имеет массу 4 г, а другая половина – 5 г. Судья знает эту информацию, но не знает, какие именно монеты сколько весят. Сможет ли барон за одно взвешивание доказать судье массу каждой монеты? Указание. Все легкие монеты вместе весят 24 г, а пять тяжелых – 25 г. Испытание 2. Малоинтересное У барона М. имеются 6 монет по 4 г, 5 монет по 5 г и 4 монеты по 6 г. Как ему доказать судье массу каждой монеты за одно взвешивание? Указание. На каждую чашу весов нужно положить ровно по 24 г. Испытание 3. Восемь гирь, одно взвешивание Барон предъявил суду 8 гирь. Он знает массу каждой гири, а судья знает только то, что массы гирь – последовательные целые числа от 1 до 8. Барону разрешено продемонстрировать всего одно взвешивание. Как ему доказать судье массу какойнибудь одной гири? Предоставим слово эксперту – барону М. – Ваша честь, я кладу на левую чашу весов 5 гирь, а на правую – две. Вы видите, что весы в равновесии? Значит, масса моих 5 гирь такая же, как у других двух. Но масса любых двух гирь из имеющихся не более 7 + 8 = 15 г, а любых пяти гирь – не менее 1 + 2 + 3 + 4 + + 5 = 15 г, значит, равенство возможно, только когда на каждой чаше ровно 15 г, т.е. на

МАТЕМАТИЧЕСКИЙ

левой чаше действительно лежат гири массой от 1 до 5 г, а на правой – гири 7 и 8 г. А это значит, что единственная невзвешенная гиря должна иметь массу 6 г! Испытание 4. Шесть гирь, два взвешивания Барон предъявил суду 6 гирь. Он знает массу каждой гири, а судья знает только то, что массы гирь – последовательные целые числа от 1 до 6. Как барону следует проделать два взвешивания, чтобы доказать судье массу каждой гири? Барон предложил такие два взвешивания: 1 + 2 + 3 = 6, 1 + 6 < 3 + 5. Почему результаты этих двух взвешиваний являются доказательством? На месте судьи мы должны убедиться, что никакая нетождественная перестановка чисел 1, 2, 3, 4, 5, 6 не может дать такие же два результата. Давайте анализировать. Первое взвешивание говорит, что масса какой-то из гирь такая же, как у других трех гирь вместе. Но ведь масса трех самых маленьких гирь не меньше 1 + 2 + 3 г, а самой большой гири – не больше 6 г. Равенство достигается, только когда на правой чаше лежит гиря 6 г, а на левой – гири 1, 2, 3 г в каком-то порядке. Тем самым, итог этого взвешивания позволяет судье распределить все гирьки на три множества {1, 2, 3}, {6} и остаток {4,5}. Перестановки теперь возможны только внутри каждого множества, но не между множествами. А что происходит во втором взвешивании? На левой чаше весов – гиря 6 г (уже определенная) и одна из гирь первого множества, а на правой – по одной гире из первого и последнего множеств. Левая чаша легче. И что? Будем перебирать все оставшиеся варианты? Нет. Снова применим анализ, основанный на неравенствах: на левой чаше не менее 7 г, потому что там сумма масс гири 6 и одной из гирь 1–3. На правой чаше не более 8 г, потому что на ней сумма масс одной из гирь 4–5 и одной из гирь 1–3. Значит, правая чаша может быть тяжелее левой только в том случае, когда на ней 8 г, а на левой 7 г. Иначе говоря, масса неизвестной гирьки на левой чаше 1 г, а массы гирек на правой чаше 3 г и 5 г (понятно, у какой какая масса, потому что они из разных множеств!). Значит, массы гирек 1, 3, 5 уже доказаны. Но тогда

КРУЖОК

доказаны и массы двух остальных, так как они остались единственными неопознанными в своих множествах. Задача 1. Как за два взвешивания доказать суду правильность масс для такого набора из восьми гирь: 10, 20, 25, 30, 35, 201, 203, 207 г? Испытание 5. Девять гирек, два взвешивания. Оценка В этот раз у барона целых 9 гирек, массы которых ему известны. Существует ли такой набор гирь, про который он сможет доказать судье их массы за два взвешивания? Речь барона в суде надолго запомнится всем любителям логических рассуждений. – Ваша честь! Вы поставили меня не просто перед трудной задачей – нет, она не трудна. Она неразрешима! Давайте мысленно представим, что я мог бы сейчас сделать? Вот я кладу какие-то гири на весы, взвешиваю, мы с вами смотрим результат. Потом делаем то же с другим набором гирь. Иначе говоря, каждой из гирь я присваиваю двузначную «метку» от 00 до 22, показывающую, в каком взвешивании я клал ее на левую чашу (1), на правую (2) или не использовал (0). Чтобы результаты взвешиваний доказали массу каждой гири, все метки должны быть различными – ведь две гири с одинаковыми метками неразличимы. Итак, мои взвешивания обязаны быть такими (я указываю метки гирь, а не их массы!): 10 11 12? 20 21 22, 01 11 21? 02 12 22. Но давайте посмотрим на возможные результаты. Если результатом взвешиваний будут два равновесия – то при парном обмене гирь 10 с 01, 20 с 02 и 12 с 21 первое взвешивание «перейдет» во второе, и наоборот. Иначе говоря, мы не сможем однозначно выяснить, какая гиря соответствует какой из меток. Тот же обмен гирь с сохранением результатов будет и при двух одинаковых неравновесиях. Далее, если получились два разных неравенства, то можно рассмотреть парный обмен 01 с 20, 10 с 02 и 11 с 22 – оба неравенства сохранятся, и мы снова не сможем опознать массу. Если в первом взвешивании было равенство, а во втором – одно из неравенств, то аналогичный эффект даст обмен 10 с 20, 11 с 21 и 12 с 22. И, наконец, если равновесие было только во втором взвешивании, то

КВАНТ 2025/№5–6

применяется обмен 01 с 02, 11 с 12 и 21 с 22. Таким образом, для всех возможных исходов у нас нет возможности гарантированно опознать все девять монет. Задача 2. Если бы вместо чашечных весов у барона М. были весы со стрелкой, смог ли бы барон М. доказать суду массу каждой гири за три взвешивания? Испытание 6. Сорок пять гирек, два взвешивания. «Разделяй и властвуй» На следующем заседании судья был обескуражен: барон М. притащил целый ящик с гирями. В описи ящика, заверенной секретарем суда, значилось, что там есть одна гиря массой 9 г, две гири массой по 8 г, три гири массой по 7 г, …, девять гирь по 1 г. «Сколько же взвешиваний вам нужно, чтобы все это доказать?» – спросил судья. – «Всего два», – с достоинством дворянина ответил барон М. Как ему действовать? Секрет манипуляций барона очень прост: k гирек массой по (10 – k) г равны по массе (10 – k) гирькам массой по k г. Поэтому если на одну чашу весов положить 9 + 8 + 7 самых легких гирек, а на другую 1 + 2 + 3 самых тяжелых, то на весах будет равновесие – и оно позволит барону разделить все гирьки на три множества {1, 2, 3}, {4, 5, 6} и {7, 8, 9}. Аналогично, если вторым взвешиванием взвесить 9 + 6 + 3 гири масс 1, 4 и 7 г с 7 + 4 + 1 гирями масс 3, 6 и 9 г соответственно, то равенство в этом взвешивании позволит установить точно массы всех гирь внутри всех множеств (2, 5 и 8 установятся методом исключения, аналогично тому, как 2 и 4 определялись в задаче о шести гирьках). Задача 3. Существует ли набор из еще большего числа гирек, для которого барон М. смог бы доказать судье массы всех гирек за два взвешивания? Испытание 7. Три взвешивания, 19 гирек. Транснеравенство Когда судья и барон встретились в следующий раз, у барона в руках был целый набор гирь, опись к которому удостоверяла, что тут находятся гирьки массой от 1 до 19 г, по одной каждой массы. «Даю вам всего три взвешивания, дорогой барон!» – провозгласил судья, ударяя по столу своим молоточком. Барон молча написал на каждой гирьке число от 1 до 19 (которое, вероятнее всего,

должно было означать ее массу), положил перед собой листок, на котором были написаны числа 12, 7 и 3, поклонился и приступил к взвешиваниям:

1 + 2 + 3 + 4 + 5 + 7 + 8 + 10 + 13 = = 16 + 18 + 19,

1 + 2 + 3 + 6 + 9 + 11 + 16 = = 8 + 10 + 13 + 17,

1 + 4 + 6 + 8 + 12 + 18 = = 3 + 7 + 11 + 13 + 15. Судья и все остальные присутствующие смотрели на барона, затаив дыхание, но ничегошеньки не понимали. Наконец, судья не выдержал: – Что вы делаете, барон? До сих пор вы хотя бы выглядели разумным человеком – клали самые тяжелые гири на одну чашу весов, самые легкие на другую. Как вы собираетесь что-то доказать нам? – Ваша честь! Давайте доведем опыт до конца. Для этого, – тут барон перевел взгляд на листок, – умножим все числа в первом равенстве на 12, во втором на 7, а в третьем на 3 и сложим все это вместе. – Сказав это, барон стал медленно выписывать выражение

$22 m_{1} 19 m_{2} 16 m_{3} 15 m_{4} 12 m_{5} 10 m_{6} 9 m_{7} 8 m_{8} 7 m_{9}^{5} m_{10}^{4} m_{11} 3 m_{12} 2 m_{13}^{3m} 15 5 m_{16} 7 m_{17} 9 m_{18} 12 m_{19}$ .

– Вы, разумеется, не можете знать массу гирьки, которую я назвал «1», равно как и все остальные массы. Но вы видите, что в левой части равенства коэффициенты монотонно убывают. Согласно $транснеравенству^{1}$ , наименьшее возможное значение левой части равно

22 1 19 2 16 3 15 4 12 5 10 6 9 7 8 8 7 9 5 10 4 11 3 12 2 13 634.

1 Подробнее о транснеравенстве (rearrangement inequality) можно узнать, например, из книги А.В.Арбита «Неравенства и основные способы их доказательства» (приложение к журналу «Квант» №3 за 2016 г.) или из книги «Элементы математики в задачах. Через олимпиады и кружки – к профессии» под редакцией А.А.Заславского и др.

МАТЕМАТИЧЕСКИЙ

Однако в правой части коэффициенты монотонно возрастают, поэтому наибольшее возможное значение ее равно

12 19 9 18 7 17 5 16 3 15

Как и в предыдущих задачах, равенство означает, что одновременно достигаются все равенства $m_{i} i$ . – Да, вижу, что вы снова правы, дорогой барон! Задача 4. Массы скольких гирек барон М. смог бы доказать, если разрешить не три, а четыре взвешивания? Следующие три испытания барону достались в одном и том же деле, поэтому мы не стали их нумеровать по-разному. Испытание $8-1.^{2}$ Восемнадцать монет двух масс. Система неравенств Казалось, никакие фокусы со взвешиваниями уже не могут удивить судью. Но… барон предъявил 18 монет, про которые судья знал только то, что массы некоторых из них по 10 г, а остальные – по 11 г, и брался доказать это всего за три взвешивания. – Но как, барон?! Ладно, за одно взвешивание вам удастся доказать мне одну тяжелую монету и одну легкую. За следующее взвешивание – если вы добавите на легкую чашу две тяжелые, а на чашу с тяжелой монетой – две легкие, то результат взвешивания изменится, а значит, вы сможете доказать массу еще 2 тяжелых и 2 легких монет. За третье взвешивание – еще 4 + 4, итого 7 тяжелых и 7 легких. Но у вас ведь их не по 7, а по 9 штук каждого вида! – Здесь нет ничего невозможного, ваша честь! Давайте только сначала разложим монеты по кучкам. В две первые кучки я положу по 2 монеты и буду доказывать, что в одной из них лежат 2 тяжелые, а в другой 2 легкие (обозначу их «2т» и «2л»). В две следующие – по 3 монеты («3т» и «3л»), а в две последние – по 4 («4т» и «4л») и сделаю следующие взвешивания: 2т + 3л < 2л + 3т, 3т + 4л < 3л + 4т, 4т + 2л + 3л < 4л + 2т + 3т.

2 В простом случае 14 монет эта задача предлагалась на VII Всесоюзной олимпиаде, а также была помещена в «Задачник «Кванта» (М212). Автор задачи про 18 монет и следующей задачи про 12 + 12 монет – С.Токарев.

КРУЖОК

– Да, барон, я вижу результаты взвешиваний. Но что именно они доказывают? – Вы слишком нетерпеливы, ваша честь. Мне будет нужно совсем немножко алгебры. Пусть x – разница в массах между кучками «2т» и «2л», а y и z – разницы между кучками «3т» и «3л» и «4т» и «4л» соответственно. Это ведь не слишком сложно? – Нет. Продолжайте! – Далее, x, y, z – целые числа. Первое взвешивание показало, что x < y, второе – что y < z, а третье – что z < x + y. Понятно, почему? – Да. – Давайте заменим строгие неравенства между целыми числами на нестрогие: x 1 d y, y 1 d z, z 1 d x y. Я хочу вывести из этого, что x = 2, y = 3, z = 4. Как только это будет доказано, станет понятно, что масса каждой кучки ровно такая, как я утверждаю, – ведь разность между массами пары монет не превышает 1, а значит, для двух пар разность всегда не больше 2, для трех пар – не больше 3, а для четырех – не больше 4, и равенства достигаются лишь в том случае, если в одних кучках только тяжелые монеты, а в других только легкие. Верно? – Согласен. – Ну, давайте умножим первое неравенство на 2, второе на 4, третье на 3 – и сложим все. Получим 9 d x y z. Это фактически означает одновременное выполнение равенств x = 2, y = 3, z = 4. У меня все, ваша честь! Испытание 8-2. Две дюжины монет. Еще одна система неравенств Про очередные 24 монеты, предъявленные бароном, судье было известно, что массы 12 из них по 10 г, а остальных 12 – по 11 г. Однако неугомонный барон снова доказал массы каждой монеты всего за три взвешивания! Как? Проследим аккуратно за рассуждениями барона из предыдущего решения. Вначале он раскладывал монетки в кучки, а затем рассматривал разность масс между кучками, доказывая, что для каждой кучки эта разность равна количеству монет в ней. Отсюда, конечно, следует все необходимое. Поэтому давайте сразу посмотрим, что поменяется в значениях величин x, y, z, если общее количество монет теперь равно 24, а неравенства

КВАНТ 2025/№5–6

x < y, y < z, z < x + y будут доказаны с помощью взвешиваний? Ясно, что в этой задаче x y z d 12, и целью барона является доказать равенство в последнем неравенстве. Если точнее, барону следует показать, что x = 3, y = 4, z = 5, т.е. разбить монетки на кучки именно таких размеров. К сожалению, приведенная система неравенств имеет неединственное решение – например, годится также z = 5, y = 4, z = 2 с суммой 11. Как же мог действовать барон, если его предыдущее решение не срабатывает? Оказывается, все равно барон действует точно так же! Ведь если общая масса всех монет четная, то и величина x + y + z должна быть четной, а значит, не может быть равна 11. Например, можно действовать в духе предыдущей замены строгих неравенств нестрогими: x 1 d y, y 1 d z, z 2 d x y. В последнем неравенстве появилась 2 вместо 1, потому что в нем на весах выложены все монеты с четной общей массой 12 11 10, и если одна чаша перевесила, то разность между чашами не менее 2. Ну а теперь если умножить первое на 2, второе на 4, а третье на 3, то после суммирования получим x y z t 12, что и требовалось. Испытание 8-3. Два раза по тридцать монет, 4 взвешивания Сколько монет удалось бы предъявить барону (с доказательством), если разрешить ему делать четыре взвешивания вместо трех? Ясно, например, что из предыдущих решений немедленно следует способ для 20 + 20 монет: четвертым взвешиванием барон кладет на одну чашу весов 9 уже опознанных как легкие и 11 неизвестных, а на другую – 9 опознанных тяжелых и 11 неизвестных. Если первая чаша оказывается тяжелее, то 11 неизвестных монет на ней должны быть тяжелыми, а 11 неизвестных монет с другой чаши – легкими, потому что неизвестных тяжелых монет всего 20 – 9 = 11, и если бы они разложились на разные чаши, то весы бы оказались в равновесии. Можно ли больше? Да, вполне. Покажем способ для 30 + 30 монет, для которого их необходимо разбить на кучки 3 + 3, 7 + 7, 9 + 9 и 11 + 11. Каждая пара кучек с одинаковым количеством раскладывается на разные чаши весов, и если разности их масс

равны x, y, z, t, то проводятся взвешивания, демонстрирующие выполнение системы неравенств z < x + y, x + y < t, t < x + z, x + t < y + z. Аналогично рассуждениям из предыдущих задач, строгие неравенства здесь можно заменить нестрогими, причем в последнем неравенстве минимально возможная разность частей будет равна 2: x y z t 1, t x z t 1, x z t t 1, y z x t t 2. Если теперь первое умножить на 8, второе на 10, третье на 6, четвертое на 3 и сложить все – получим неравенство x y z t t 30, которое и доказывает все необходимое. Замечание. Последовательность значений (10 + 10 и 30 + 30), найденная бароном в испытаниях 8-1 и 8-3, разумеется, не заканчивается на четырех взвешиваниях. Известно (доказано компьютерным перебором), что она продолжается: 114 + 114 – для пяти взвешиваний и 454 + 454 – для шести (https: oeis.org A280432). Эта последовательность тесно связана с такой алгебраической конструкцией, как матрицы Адамара. Как мы увидели на примерах, задачи о взвешиваниях, в которых участвует эксперт, намного менее комбинаторны (по духу и содержанию) и намного более алгебраичны, чем классические задачи об отыскании фальшивых монет. Зато в них гораздо больше нераскрытых секретов – например, почти ни для каких сложных задач из последних испытаний пока не удается беспереборно доказать не только точные (верхние) оценки, но и такие, которые бы были близки к точным.