Question

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

Answer 1

1) За 1017 взвешиваний Мистер Фокс сможет гарантированно узнать суммарный вес всех монет.

Он, к примеру, сначала взвесит 1014 "не пересекающихся" пар монет. И узнает их суммарный вес.

Останется еще 3 монеты (по причине того, что  2031 - 1014 · 2 = 3). Первая будет взвешена по очереди со второй и с третьей, а дальше на весах появятся вторая и третья монета.

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

И прибавим его к весу взвешенных ранее 1014 пар монет. Получим суммарный вес всех монет.

2) Меньше, чем за 1017 взвешиваний, в общем случае суммарный вес монет не удастся узнать.

Почему? Очевидно, что при взвешиваниях каждая монета должна побывать на весах. Поэтому взвешиваний должно быть уже не меньше 1016 (2031 : 2 = 1015 пар монет, и 1 в остатке дает 1016-ое взвешивание).

Несложно понять, что если нам удалось за 1016 (или меньше) взвешиваний узнать суммарный вес монет, то: 1) все монеты побывали на весах; 2) ровно одна монета (обозначим ее буквой М) побывала на весах два раза, во второй раз - с монетой Л, образовавшейся в результате остатка при делении на 2 числа 2031.

Суммарный вес всех монет, кроме М нам известен. Следовательно, задача решится, если мы найдем Л. А чтобы найти Л, нужно найти М. Но М как из первого взвешивания, так и из второго найти нельзя.

Можно сказать, что получается что-то наподобие системы из двух линейных уравнений с тремя неизвестными (X + M = a, M + L = b).

Таким образом, за 1016 (и меньше) взвешиваний узнать суммарный вес всех монет не удастся. А за 1017 - уже получится.

Answer 2

Для решения этой задачи, нам нужно найти наименьшее количество взвешиваний, при котором Мистер Фокс сможет определить суммарный вес всех 2031 монет.

Давайте рассмотрим возможные варианты:

1. Если Мистер Фокс взвешивает две монеты, он получает суммарный вес только этих двух монет.
2. Если Мистер Фокс взвешивает три монеты, он получает суммарный вес только этих трех монет.
3. Если Мистер Фокс взвешивает четыре монеты, он получает суммарный вес только этих четырех монет.

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

Чтобы решить эту задачу оптимальным образом, Мистер Фокс может использовать двоичное кодирование суммарного веса монет. В двоичном коде каждая позиция соответствует одной монете, и значение 1 указывает, что монета на этой позиции должна быть взвешена. Тогда Мистер Фокс может взвесить монеты, соответствующие позициям с единицами в двоичном коде.

Для 2031 монет потребуется логарифм по основанию 2 от ближайшего большего целого числа, которое составляет или превышает 2031. В данном случае, это будет 11 (2^11 = 2048).

Таким образом, Мистер Фоксу потребуется наименьшее число взвешиваний, равное 11, чтобы узнать суммарный вес всех 2031 монет.