Задача 7. Честный ювелир

Что видит покупатель и что значит «доказать»

Назовём однограммовую монету $A$, а её вес, каким его представляет себе покупатель, — $x$. Покупатель знает только, что все сто весов — это числа $1, 2, \ldots, 100$ в каком-то порядке. Во время взвешивания он видит, какие монеты легли на каждую чашу, а весы показывают лишь одно из трёх: левая чаша тяжелее, правая тяжелее или равновесие.

Назовём раскладкой любой способ приписать монетам веса $1, \ldots, 100$ по одному разу. После двух взвешиваний покупатель мысленно перебирает все раскладки и оставляет только те, при которых весы оба раза показали бы ровно то, что он видел. Настоящая раскладка среди них точно есть.

Теперь требования задачи звучат так:

• доказать, что $A$ весит $1$ г — значит, во всех оставшихся раскладках $x=1$;

• не раскрыть вес других монет — значит, для каждой другой монеты среди оставшихся раскладок есть хотя бы две, в которых её вес разный.

В модели с девятью монетами покупатель именно так и действует: перебирает все $9!=362\,880$ раскладок. Со ста монетами перебор невозможен, поэтому покупателю нужны оценки — и ювелир должен подобрать взвешивания, из которых такие оценки следуют.

Много лёгких монет против нескольких тяжёлых

Что покупатель может вывести из одного взвешивания? Только оценки. Любые $k$ различных монет весят не меньше $1+2+\ldots+k$ г — столько весят $k$ самых лёгких. Любые $m$ монет весят не больше суммы $m$ самых тяжёлых весов: $100+99+\ldots+(101-m)$.

Пусть на одной чаше $k$ монет, на другой $m$ монет, и чаша с $k$ монетами оказалась легче. Если при этом наименьший возможный вес $k$ монет почти равен наибольшему возможному весу $m$ монет, покупателю некуда деваться: $k$ монет — почти самые лёгкие, $m$ монет — почти самые тяжёлые.

Подберём такую пару. Перебираем $m=1, 2, 3, \ldots$ и для каждого $m$ берём наибольшее $k$, при котором сумма $k$ самых лёгких весов ещё меньше суммы $m$ самых тяжёлых:

• $m=1$: $100$; $k=13$: $1+\ldots+13=91$ — запас $9$;

• $m=2$: $99+100=199$; $k=19$: $1+\ldots+19=190$ — запас $9$;

• $m=9$: $92+93+\ldots+100=864$; $k=41$: $1+2+\ldots+41=\dfrac{41\cdot 42}{2}=861$ — запас всего $3$.

Пара $41$ и $9$ даёт нужный маленький запас (рисунок ниже). Если $41$ монета легче $9$ монет, то $41$ монета весит не больше $863$ г: это монеты $1, \ldots, 41$ с точностью до замены одной-двух из них на чуть более тяжёлые, а $9$ монет весят не меньше $862$ г.

Но одного такого взвешивания мало: покупатель узнаёт, что монета $A$ лежит среди $41$ почти самых лёгких, а какая из них весит $1$ г — нет. Запас в $3$ г позволяет ему думать, что $A$ весит $2$ или $3$ г. Нужно, чтобы монета $A$ входила в оценку особым образом, — и для этого её можно положить на лёгкую чашу дважды.

Два взвешивания с монетой $A$ на лёгкой чаше

Разделим монеты $2, 3, \ldots, 41$ на две части и монеты $92, \ldots, 100$ тоже на две части, а монету $A$ положим на лёгкую чашу оба раза:

• Взвешивание 1. Левая чаша: $A$ и монеты $2, 3, \ldots, 27$ — всего $1+(2+3+\ldots+27)=1+377=378$ г. Правая чаша: монеты $92$, $93$, $94$, $100$ — $379$ г. Левая чаша легче на $1$ г.

• Взвешивание 2. Левая чаша: $A$ и монеты $28, 29, \ldots, 41$ — всего $1+(28+\ldots+41)=1+483=484$ г. Правая чаша: монеты $95$, $96$, $97$, $98$, $99$ — $485$ г. Левая чаша снова легче на $1$ г.

Проверим подсчёт: $2+\ldots+27=\dfrac{27\cdot 28}{2}-1=377$, $28+\ldots+41=861-378=483$, $92+93+94+100=379$, $95+96+97+98+99=485$. Все $49$ монет на чашах, кроме $A$, разные, а остальные $50$ монет ($42, \ldots, 91$) на весы не попадают (рисунок ниже).

Как подобрать такое разбиение: каждая правая чаша должна быть тяжелее своей левой ровно на $1$ г, то есть на $2$ г тяжелее монет, лежащих рядом с $A$. Берём на правую чашу четыре монеты — $92+93+94+100=379$ — и добираем слева монеты $2, \ldots, 27$ с суммой $377$; оставшиеся монеты сами складываются во второе взвешивание: $483$ против $485$.

Складываем оба взвешивания: $A$ весит 1 г

Посмотрим на эти два взвешивания глазами покупателя. Он видит: оба раза чаша с монетой $A$ была строго легче. Обозначим веса левых чаш $L_1$ и $L_2$, правых — $R_1$ и $R_2$. Веса целые, поэтому $L_1\le R_1-1$ и $L_2\le R_2-1$. Сложим:

Теперь оценим обе части, не зная весов.

Правые чаши вместе — это $4+5=9$ различных монет. Их вес не больше $92+93+\ldots+100=864$.

Левые чаши вместе — это монета $A$ дважды и ещё $26+14=40$ различных монет. Иначе говоря, это $41$ различная монета (среди них $A$) и ещё раз монета $A$. Любые $41$ различные монеты весят не меньше $1+2+\ldots+41=861$, значит $L_1+L_2\ge 861+x$.

Подставляем: $861+x\le 864-2=862$, откуда $x\le 1$. А веса — целые числа, не меньшие $1$, поэтому $x=1$. Покупатель убедился: монета $A$ весит ровно $1$ г (рисунок ниже).

Заодно видно, что весь запас в $3$ г потрачен без остатка: единица ушла на то, что $A$ посчитана дважды, и по единице — на каждое строгое «легче». Если бы хоть раз весы показали равновесие, получилось бы лишь $x\le 2$, и доказательства бы не было.

Почему покупатель не узнаёт больше ничего

Осталось проверить второе требование: ни про одну другую монету покупатель не может сказать, сколько она весит. Разобьём все монеты, кроме $A$, на пять групп:

• $26$ монет $2, \ldots, 27$ — лежали слева в первом взвешивании;

• $14$ монет $28, \ldots, 41$ — лежали слева во втором;

• $4$ монеты $92$, $93$, $94$, $100$ — справа в первом;

• $5$ монет $95, \ldots, 99$ — справа во втором;

• $50$ монет $42, \ldots, 91$ — на весы не попадали.

Представим другую раскладку: внутри каждой группы веса сдвигаются по кругу — каждая монета получает вес следующей монеты своей группы, а последняя — вес первой (рисунок ниже). Монета $A$ остаётся с весом $1$. Вес каждой чаши при этом не меняется: чаша целиком состоит из $A$ и целых групп, а сумма весов группы при сдвиге по кругу та же. Значит, оба взвешивания показали бы ровно то же самое, и покупатель не может отличить эту раскладку от настоящей.

Но в каждой группе хотя бы две монеты, поэтому при сдвиге по кругу вес каждой монеты, кроме $A$, изменился. Для любой монеты, кроме $A$, у покупателя есть две подходящие раскладки с разными весами — определить вес он не может. Оба требования выполнены.