The original puzzle
A man must pay his room at the inn for a period of 23 days. He owns a golden chain with, coincidentally, 23 links and, day
by day, he must leave with the inn-keeper the number of lnks corresponding to the number of days which he already spent at
the inn. At the end of his stay, someone will bring the money required and he will regain possession of the 23 links. Since
he must now pay to have a jeweler repair the links that have been opened, these must be kept to a minimum. What is the smallest
number of links he must open to produce all the numbers from 1 to 23 ? (Links previously given can be redeemed when a larger
section of links is presented.)
One can only arrive at the answer of the minimum number of open links
by a thorough knowledge of the process involved,
and the best way to achieve this is by doing the operation "the other way around",
by starting with the number of open links
and observing the maximum length of chain possible.
Let's start by opening only one link -
This open link is, of course, good for the first day.
We do not know yet where it is in the chain,
but we do know that it divides the chain into 3 parts, with 1 part on each side of it.
On the second day, we will need a 2-link section,
and we now know that we opened the third link, right after this 2-link section.
We have what we need for the third day, the open link and the 2-link section.
On the fourth day, we will need a 4-link section, which will be on the other side of the open link.
We have what we need for 3 more days by adding the two smaller sections.
With one open link we can pay for 7 days.
Now, let's open two links, without knowing yet where they are,
but knowing that they divide the chain into 5 parts,
one on each side of them, and another between them.
These two open links are good for the first 2 days.
On the third day, we will need a 3-link section,
and we know that the fourth link was opened.
We are now good for the fourth and fifth days (adding the two open links).
On the sixth day, we need a 6-link section, which is between the two open links,
and we know that the eleventh link was opened.
On the twelfth day, we need a 12-link section at the end of the chain,
and we are now good for 12 more days.
With two open links we can pay for 23 days.
If "n" represnts the number of open links,
the maximum number of links in the chain will be (n+1)(2n+1) - 1.
A variation of our basic 2n - 1 formula.
Opening 5 links would permit a chain of 6 x 64 - 1 = 383 links !
You will find an application of this in the Devices Chapter.