Проверка подписей на монетах — олимпиадная задача по теории алгоритмов

Для обозначения монет будем использовать надписи, которые сделаны на них. Первое взвешивание:сравним $1 + 2 + 2 + 3 + 3 + 3$ и $5 + 5 + 5$. Минимальный возможный вес монет на первой чаше равен 14 г, а максимальный на правой — 15 г. Поэтому если левая чаша легче, то ней именно такой набор монет (возможно, с перепутанными надписями), а на правой — три монеты массой 5 г. Второе взвешивание:сравним $1 + 4 + 4 + 4 + 5^$и$3 + 3 + 3 + 5 + 5$, где$5^$— монета, про которую уже известно, что она весит 5 г, а$5$ — монета про которую мы этого не знаем. Минимальный возможный вес монет на первой чаше — 18 г, а максимальный на правой — 19 г. Значит, если левая чаша легче, то на всех монетах на весах надписи сделаны верно. Тогда на оставшихся монетах 2, 2 и 4 надписи также правильные. Если хоть одно из взвешиваний даст другой результат, то среди надписей есть ошибочные.