ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 77922
Темы:    [ Взвешивания ]
[ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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

Решение

Ответ: 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 звеньев.
Также доступны документы в формате TeX

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

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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .