Однажды путешественник решил остановится в гостинице на неделю. Денег у него почти не было, но была золотая цепочка, состоящая из семи колец. Хозяин гостиницы согласился получать в уплату звенья этой цепочки из расчета одно колечко в день, но с некоторыми условиями. Во-первых, каждый прожитый день оплачивать следовало раздельно. Во-вторых, хозяин попросил не откалывать от цепочки по одному звену в день, а сразу рассечь какое-то минимальное количество колечек, чтобы цепочка распалась на несколько секций, с помощью которых путешественник смог бы расплачиваться с хозяином одним колечком (не исключая рассеченных) ежедневно. Какое минимальное количество колечек нужно рассечь и как следует производить оплату, чтобы выполнить условия хозяина? (Учтите, что в виде сдачи хозяин может использовать ранее полученные кольца этой цепочки).
update
Ответ
Достаточно рассечь одно кольцо - третье. Не считая рассеченного, образуется две секции: из двух колец и из четырех.
Оплата будет производится следующим образом.
1-й день: путешественник отдает рассеченное кольцо;
2-й день: отдает секцию из двух колец, получает обратно рассеченное;
3-й день: отдает рассеченное;
4-й день: отдает секцию из четырех колец, получает обратно рассеченное и секцию из двух колец;
5-й день: отдает рассеченное;
6-й день: отдает секцию из двух колец, получает обратно рассеченное;
7-й день: отдает рассеченное.
Головоломка сварщика.
