Question

У Мистера Фокса есть 2021 монета. За одно взвешивание он может узнать суммарный вес любых двух монет. За какое наименьшее число взвешиваний Мистер Фокс может узнать суммарный вес всех монет?​

Answer 1

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 - уже получится.

Answer 2

Предположим, что все монеты имеют одинаковый вес. Если у нас есть 2021 монета, наименьшее число взвешиваний, которое понадобится Мистеру Фоксу, чтобы узнать суммарный вес всех монет, будет равно 10.

Пояснение:

1. Разделим 2021 монету на 2 группы: 1000 монет и 1021 монета.
2. Взвесим эти две группы.
   • Если одна из групп весит больше, то мы знаем, что суммарный вес находится в этой группе. Таким образом, нам потребуется еще 9 взвешиваний, чтобы узнать суммарный вес 1000 монет.
   • Если вес обеих групп одинаков, то мы знаем, что суммарный вес находится в оставшихся 21 монете. В этом случае нам потребуется еще 1 взвешивание, чтобы узнать суммарный вес этих 21 монеты.

Таким образом, общее количество взвешиваний будет равно 10, что является наименьшим числом взвешиваний, чтобы узнать суммарный вес всех 2021 монеты.