|
|
 |
Условие
Робин Гуд взял в плен семерых богачей и потребовал выкуп. Слуга каждого богача принёс кошелёк с золотом, и все они выстроились в очередь перед шатром, чтобы отдать выкуп. Каждый заходящий в шатер слуга кладёт принесённый им кошелёк на стол в центре шатра и, если такого или большего по тяжести кошелька ранее никто не приносил, богача отпускают вместе со слугой. Иначе слуге велят принести ещё один кошелёк, который был бы тяжелее всех, лежащих в этот момент на столе. Сходив за очередным кошельком, слуга становится в конец очереди. Походы за кошельками занимают у всех одинаковое время, поэтому очерёдность захода в шатёр не сбивается.
Когда Робин Гуд отпустил всех пленников, у него на столе оказалось: а) 28; б) 27 кошельков. Каким по счёту стоял в исходной очереди слуга богача, которого отпустили последним?
Решение
Если слуга принёс новый кошелёк, а с тех пор как он был в прошлый раз в шатре, никого не отпускали, то его точно ждёт удача (его кошелёк самый тяжёлый и на этот раз его хозяина отпустят). То есть если в плену было N богачей и одного только что отпустили, то дальше может произойти не более N − 1 неудачи подряд.
а) Если в начале было семь богачей, то первого отпустят сразу, дальше будет не более 6 неудач, потом удача и не более 5 неудач и т. д. – и всего Робин Гуд получит не более (1 + 6) + (1 + 5) + (1 + 4) + (1 + 3) + (1 + 2) + (1 + 1) + 1 = 28 кошельков. И ровно 28 кошельков он получит, только если на первом круге неудача постигла всех, кроме первого, потом всех, кроме второго и т. д. А последним положит кошелёк седьмой слуга.
б) Если Робин Гуд получил в итоге не 28, а 27 кошельков, то ровно один промежуток неудач должен оказаться на 1 короче максимального. Тогда он закончится не после перехода на следующий круг, а на один шаг раньше, и на этом круге кроме слуги с наименьшим номером повезёт ещё и седьмому слуге.
Если это произошло на последнем круге, когда все
остальные слуги уже ушли, то седьмой слуга и положит
последний кошелёк. А если какие-то слуги ещё остались,
когда седьмому слуге выпала удача вне очереди, то оставшиеся продолжат уходить по очереди, как в предыдущем
пункте. И последний кошелёк положит последний из
оставшихся – шестой слуга.
