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

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

Условие

Автор: Звонкин Д.

Требуется сделать набор гирек, каждая из которых весит целое число граммов, с помощью которых можно взвесить любой целый вес от 1 до 55 граммов включительно даже в том случае, если некоторые гирьки потеряны (гирьки кладутся на одну чашку весов, измеряемый вес – на другую). Рассмотрите два варианта задачи:
  а) необходимо подобрать 10 гирек, из которых может быть потеряна любая одна;
  б) необходимо подобрать 12 гирек, из которых могут быть потеряны любые две.


Решение

  а) Искомый набор гирь:  f1 = 1,  f2 = 1,  f3 = 2,  f4 = 3,  f5 = 5,  f6 = 8,  f7 = 13,  f8 = 21,  f9 = 34,  f10 = 55  (члены последовательности Фибоначчи, для которой
fn+2 = fn+1 + fn).
  Индукцией по n докажем, что, даже потеряв одну гирю из набора гирь  f1, f2, ..., fn,  можно составить любой вес от 1 до  fn+1 – 1.  База очевидна.
  Шаг индукции. Если вес  S < fn,  то его по предположению индукции можно взвесить уже набором  f1, f2, ..., fn–1  с потерей одной гири. Пусть  S ≥ fn.  Если не потеряна  fn, то вес  S – fn  можно взвесить с помощью гирь  f1, f2, ..., fn–1  (с потерянной гирей) и добавить гирю  fn. Если  fn потеряна, то  fn–1 не потеряна. Вычитая её из S, получим вес, меньший  fn+1fn–1 = fn.  Его можно взвесить с помощью набора  f1, f2, ..., fn–1  с потерянной гирей  fn–1. Добавив  fn–1, получим S.

  б) Искомый набор гирь  F1 = F2 = F3 = 1,  F4 = 2,  F5 = 3,  F6 = 4,  F7 = 6,  F8 = 9,  F9 = 13,  F10 = 19,  F11 = 28,  F12 = 41  (члены последовательности для которой  Fn+1 = Fn + Fn–2).  Аналогично а), по индукции докажем, что потеряв две гири из набора  F1, ..., Fn,  можно взвесить любой вес  S < Fn+1.  В шаге индукции, если потеряна гиря Fn, то одна из гирь  Fn–1, Fn–2  не потеряна. Вычитая её из S, получим вес, меньший  Fn+1Fn–2 = Fn,  который можно взвесить с помощью набора гирь  F1, ..., Fn–1,  причём использованную ранее гирю следует считать потерянной.
  Таким образом, предъявленный набор позволяет (с потерей двух гирь) взвесить любой целый вес от 1 до  41 + 19 – 1 = 59 г.

Замечания

баллы: 4 + 4

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

олимпиада
Название Турнир городов
Турнир
Номер 15
Дата 1993/1994
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 6

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

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