Задача
Имеется кусок цепи из 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 доl1+k, гдеl1$\le$k.) Затем наиболее выгодно иметь часть из 2(k+ 1) звеньев, затем из 4(k+ 1) звеньев и т.д. Итак, если мы расковалиkзвеньев, то наиболее выгодна ситуация, когда полученные при этомk+ 1 частей состоят изk+ 1, 2(k+ 1), 4(k+ 1), 8(k+ 1), ..., 2k(k+ 1) звеньев (раскованные звенья мы здесь не учитываем). В таком случае можно составить любое число звеньев от 1 доn= 2k + 1(k+ 1) - 1. Итак, если2kk$\le$n$\le$2k + 1(k+ 1) - 1, то можно обойтисьkразрывами и нельзя обойтисьk- 1 разрывами. В частности, если24$\le$n$\le$63, то наименьшее число раскованных звеньев равно 3. Полученные при расковке четыре части цепи должны состоять при этом из 4, 8, 16, 29 звеньев.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь