Задача 77922

Темы:    [ Взвешивания ] [ Процессы и операции ] [ Теория алгоритмов (прочее) ] [ Оценка + пример ]

Сложность: 4 Классы: 8,9,10

Условие

Имеется кусок цепи из 60 звеньев, каждое из которых весит 1 г. Какое наименьшее число звеньев надо расковать, чтобы из образовавшихся частей можно было составить все веса в 1 г, 2 г, 3 г, ..., 60 г (раскованное звено весит тоже 1 г)?

Решение

Ответ: 3 звена. Выясним, при каком наибольшем n достаточно расковать k звеньев n-звенной цепи, чтобы из образовавшихся частей можно было составить все веса от 1 до n. Если расковано k звеньев, то любое число звеньев от 1 до k можно набрать из них. Но k + 1 звеньев мы не сможем набрать, если не будет части из k + 1 или менее звеньев (мы здесь не учитываем раскованные звенья). Наиболее выгодно иметь часть из ровно k + 1 звеньев. Тогда мы сможем получить любое число звеньев от 1 до 2k + 1. (Иначе мы сможем получить лишь число звеньев от 1 до l₁ + k, где l₁k.) Затем наиболее выгодно иметь часть из 2(k + 1) звеньев, затем из 4(k + 1) звеньев и т.д. Итак, если мы расковали k звеньев, то наиболее выгодна ситуация, когда полученные при этом k + 1 частей состоят из k + 1, 2(k + 1), 4(k + 1), 8(k + 1), ..., 2^k(k + 1) звеньев (раскованные звенья мы здесь не учитываем). В таком случае можно составить любое число звеньев от 1 до n = 2^{k + 1}(k + 1) - 1. Итак, если 2^kkn2^{k + 1}(k + 1) - 1, то можно обойтись k разрывами и нельзя обойтись k - 1 разрывами. В частности, если 24n63, то наименьшее число раскованных звеньев равно 3. Полученные при расковке четыре части цепи должны состоять при этом из 4, 8, 16, 29 звеньев.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	14
Год	1951
вариант
Класс	7,8
Тур	1
задача
Номер	5