Назад

Олимпиадная задача Звонкина про набор гирек: взвешивания 1–55 граммов с потерями

Задача 198194 • Сложность: 3 • 8-10 класс
Задача

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

  а) необходимо подобрать 10 гирек, из которых может быть потеряна любая одна;

  б) необходимо подобрать 12 гирек, из которых могут быть потеряны любые две.

Авторы:
Звонкин Д.
Разделы:
Последовательности Теория алгоритмов
Источники:
Турнир городов 15 турнир (1993/1994 год) осенний тур, основной вариант, 8-9 класс Олимпиады и турниры
Количество версий:
3
Решение

  а) Искомый набор гирь:  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+1 – fn–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+1 – Fn–2 = Fn,  который можно взвесить с помощью набора гирь  F1, ..., Fn–1,  причём использованную ранее гирю следует считать потерянной.

  Таким образом, предъявленный набор позволяет (с потерей двух гирь) взвесить любой целый вес от 1 до  41 + 19 – 1 = 59 г.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Войти Зарегистрироваться
Комментариев нет