РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 1827 Добавить в вариант

У барона Мюнхгаузена есть набор гирь 1000 различных целых весов, по 2¹⁰⁰⁰ гирь каждого веса. Барон утверждает, что если взять по одной гире каждого веса, то общий вес этих 1000 гирь будет меньше 2¹⁰¹⁰, причём этот вес невозможно набрать гирями из этого набора другим способом. Могут ли слова барона оказаться правдой?

Спрятать решение

Решение.

Пусть $k=1000.$ Докажем, что подойдет набор гирь $a_k минус 1=2 в степени левая круглая скобка k правая круглая скобка минус 2 в степени левая круглая скобка k минус 1 правая круглая скобка ,$ $a_k минус 2=2 в степени левая круглая скобка k правая круглая скобка минус 2 в степени левая круглая скобка k минус 2 правая круглая скобка , \ldots, a_0=2 в степени левая круглая скобка k правая круглая скобка минус 2 в степени левая круглая скобка 0 правая круглая скобка .$ Сумма их весов равна

$S=k умножить на 2 в степени левая круглая скобка k правая круглая скобка минус 2 в степени левая круглая скобка k минус 1 правая круглая скобка минус умножить на s минус 2 в степени левая круглая скобка 1 правая круглая скобка минус 2 в степени левая круглая скобка 0 правая круглая скобка = левая круглая скобка k минус 1 правая круглая скобка умножить на 2 в степени левая круглая скобка k правая круглая скобка плюс 1.$

При $k=1000$ ясно что $s меньше 2 в степени левая круглая скобка 1010 правая круглая скобка .$ Кроме того, $s \equiv 1 левая круглая скобка \bmod 2 в степени левая круглая скобка k правая круглая скобка правая круглая скобка .$ Предположим, что мы другим способом набрали $s .$ Так как $a_i \equiv минус 2 в степени левая круглая скобка i правая круглая скобка левая круглая скобка \bmod 2 в степени левая круглая скобка k правая круглая скобка правая круглая скобка ,$ то нам удалось набрать 1 по модулю $2 в степени левая круглая скобка k правая круглая скобка$ как сумму нескольких $минус 2 в степени левая круглая скобка i правая круглая скобка ,$ а стало быть, можно набрать число, сравнимое с $2 в степени левая круглая скобка k правая круглая скобка минус 1$ как сумму нескольких $2 в степени левая круглая скобка i правая круглая скобка .$ Будем в такой сумме заменять две одинаковые степени 2 на одну, пока это возможно. В результате получится, что $2 в степени левая круглая скобка k правая круглая скобка минус 1$ набрано как сумма различных степенней двойки, а это можно сделать единственным способом: сложив все меньшие степени двойки. Это соответствует сумме $a_k минус 1 плюс a_k минус 2 плюс умножить на s плюс a_0 .$ Остается лишь добавить, что замена одной степени двойки на две меньших (обратная нашим операциям) дает замену $a_i$ на $2 a_i минус 1,$ что увеличивает сумму. Значит, наш способ единственен.

Ответ: да, существуют.

Санкт-Петербургская олимпиада школьников, 11 класс, 2 тур (заключительный), 2019 год

Классификатор: Разное. Взвешивания, Разное. Да или нет?

Спрятать решение · Помощь