У Мистера Фокса есть 2021 монета. За одно взвешивание он может узнать суммарный вес любых двух монет. За какое наименьшее число взвешиваний Мистер Фокс может узнать суммарный вес всех монет?
Ответы
1) За 1012 взвешивания Мистер Фокс сможет гарантированно узнать суммарный вес монет.
Он, к примеру, сначала взвесит 1009 "не пересекающихся" пар монет. И узнает их суммарный вес.
Останется еще 3 монеты (по причине того, что 2021 - 1009 · 2 = 3). Первая будет взвешена по очереди со второй и с третьей, а дальше на весах появятся вторая и третья монета.
Результатом таких взвешиваний будут три числа. Если мы их сложим, то получим удвоенный вес первой, второй и третьей монет. Если разделим на два, то получим вес всех трех оставшихся монет.
И прибавим его к весу 1009 пар взвешенных ранее 1009 пар монет. Получим суммарный вес всех монет.
2) Меньше, чем за 1012 взвешиваний, в общем случае суммарный вес монет не удастся узнать.
Почему? Очевидно, что при взвешиваниях каждая монета должна побывать на весах. Поэтому взвешиваний должно быть уже не меньше 1011 (2021 : 2 = 1010 пар монет, и 1 в остатке дает 1011-ое взвешивание).
Несложно понять, что если нам удалось за 1011 взвешиваний узнать суммарный вес монет, то: 1) все монеты побывали на весах; 2) ровно одна монета (обозначим ее буквой М) побывала на весах два раза, во второй раз - с монетой Л, образовавшей в результате остатка при делении на 2 числа 2021.
Суммарный вес всех монет, кроме М нам известен. Следовательно, задача решится, если мы найдем Л. А чтобы найти Л, нужно найти М. Но М как из первого взвешивания, так и из второго найти нельзя.
Так как получается что-то наподобие системы из двух линейных уравнений с тремя неизвестными (X + M = a, M + L = b).
Таким образом, за 1011 (и меньше) взвешиваний узнать суммарный вес всех монет не удастся. А за 1012 - уже получится.