|
|
 |
Условие
Требуется сделать набор гирек, каждая из которых весит целое число граммов,
с помощью которых можно взвесить любой целый вес от 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+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 г.
Замечания
баллы: 4 + 4
