За какое наименьшее число взвешиваний Трамфин может узнать суммарный вес всех своих монет?

Это задача на разделяй и властвуй.

Пусть у нас есть n монет. Сначала взвесим монеты 1 и 2. Затем взвесим монеты 3 и 4, и так далее. Если n нечетное, то последнюю монету не взвешиваем.

После этого у нас есть примерно n/2 пар монет. Снова взвешиваем пары пар, и так далее.

Количество взвешиваний можно оценить как log₂(n!). Однако, если посмотреть на задачу под другим углом, то можно заметить, что достаточно 2000 взвешиваний. Алгоритм простой: взвешиваем попарно все монеты, кроме одной. Далее берем одну из взвешенных монет, и взвешиваем со всеми не взвешенными. Получается ровно 2000 взвешиваний.

Но это не минимальное число взвешиваний. Попробуем оценить минимальное число взвешиваний.

Предположим, у нас есть N монет. Мы можем взвесить любые две монеты за 1 раз. Таким образом, после первого взвешивания мы знаем суммарный вес этих двух монет.

Допустим, мы сделали K взвешиваний. Пусть w_i - вес i-ой монеты. Тогда мы знаем K сумм вида w_i + w_j.

Вопрос: можем ли мы по этим K суммам однозначно определить все w_i?

Если K < N - 1, то мы не сможем однозначно определить все w_i.

Доказательство: пусть у нас есть система из K уравнений с N неизвестными. Если K < N - 1, то у этой системы бесконечно много решений.

Таким образом, нам нужно не менее N - 1 взвешиваний.

В нашем случае N = 2001, поэтому нам нужно не менее 2000 взвешиваний.

Ответ: 2000