|
Название задачи: Золотая цепочка. |
 |
Условие
а) На постоялом дворе остановился путешественник, и хозяин согласился в качестве уплаты за проживание брать кольца золотой цепочки, которую тот носил на руке. Но при этом он поставил условие, чтобы оплата была ежедневной: каждый день хозяин должен был иметь на одно кольцо больше, чем в предыдущий. Замкнутая в кольцо цепочка содержала 11 колец, а путешественник собирался прожить ровно 11 дней, поэтому он согласился. Какое наименьшее число колец он должен распилить, чтобы иметь возможность платить хозяину? б) Из скольких колец должна состоять цепочка, чтобы путешественник мог прожить на постоялом дворе наибольшее число дней при условии, что он может распилить только n колец?Решение
а) Достаточно разрезать два кольца так, чтобы отделились куски из трёх и шести колец. На третий день путешественник отдает кусок из трёх колец и получает два кольца сдачи, а на шестой – кусок из шести колец и получает пять колец сдачи.
б) Расположим получившиеся куски цепочки (не считая распиленных колец) по возрастанию числа колец в них: a1 ≤ a2 ≤ ... Ясно, что a1 ≤ n + 1 (иначе заплатить за (n+1)-й день не удастся), a2 ≤ a1 + n + 1 ≤ 2(n + 1), a3 ≤ a2 + a1 + n + 1 ≤ 4(n + 1), ... Кроме того, количество кусков не превосходит n. Поэтому в цепочке не более n + (n + 1)(1 + 2 + 2² + ... + 2n–1) = (n + 1)2n – 1 колец. Взяв куски максимальной возможной длины (ak = (n + 1)2k–1, k = 1, ..., n), мы получим цепочку из (n + 1)2n – 1 колец.
Ответ
а) 2 кольца. б) Из (n + 1)2n – 1 колец.Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 1 |
| Название | Метод математической индукции |
| Тема | Индукция |
| параграф | |
| Номер | 3 |
| Название | Индукция в геометрии и комбинаторике |
| Тема | Индукция (прочее) |
| задача | |
| Номер | 01.047 |
