Logic Puzzles

I'm reading a book on logic. It's called "aha! Insight" by Martin Gardner.

Anyway, there's a puzzle that might interest y'all:


Gloria, a young lady from Arkansas, is visiting in California. She wants to rent a hotel room for a week.
The clerk was very unpleasant.
Clerk: The room is $20 per day and you have to pay cash.
Gloria: I'm sorry sir, but I don't have any cash. However, I do have this solid gold bracelet. Each of its seven links is worth more than $20.
Clerk: Alright, give me the bracelet.
Gloria: No, not now. I'll have a jeweler cut the bracelet so I can give you 1 link a day. Then when I get some money at the end of the week I'll redeem it.
The clerk finally agreed. But now Gloria had to decide how to cut the bracelet. She was in a dilemma.
Gloria: I have to be careful because the jeweler is going to charge me for each link that he cuts and for each link that he joins when the bracelet is put back together again.
After thinking a while Gloria realized she didn't have to cut all the links because she could trade pieced back and forth. She couldn't believe it when she figured out how many cuts the jeweler had to make. How many cuts would you make?

*

*

*

*

*

*

*

ANSWER.
Only one link need be cut. It must be third from one end. This makes three pieces of 1, 2, and 4 links. And these are sufficient to trade back and forth so that each day the clerk gets one more link.

Two aha! insights are needed to solve this problem. The first is to realize that the smallest set of chains that can be combined in various ways to form sets of 1, 2, 3, 4, 5, 6 and 7 links is a set of chains with 1, 2 and 4 links; that is, with numbers in the doubling series. As we learned in the last problem, this is the power series that is the basis of binary notation.
The second insight is to realize that cutting only one link divides the bracelet into this desired set of three chains.

I got this one fine (after a time). But the thing is the following problem:

The problem generalizes to chains of longer lengths. For instance, suppose Gloria had a chain of 67 gold links that she wanted to cut and use in the same way she used her bracelet—to pay for 67 days, one link per day. The cutting of as few as three links will do the trick. Do you see how? Can you devise a general procedure that solves the problem, with a minimum number of cut links, for a chain of any length?

*

*

*

*

*

*

*

ANSWER. Provided by Nathaniel.
Alright. The maximum number of different lengths that can be rendered from one length by three cuts is seven. This is if you cut and remove three lengths, none of which are next to each other or at an end of the chain, and reattach none of them.

Let's figure out how many different combinations we can make with different lengths of chain (not counting zero as a combination):

1 length : 1 possible combination
2 lengths : 3 possible combinations
3 lengths : 7 possible combinations
4 lengths : 15 possible combinations
5 lengths : 31 possible combinations
6 lengths : 63 possible combinations
7 lengths : 127 possible combinations

You can either come up with this list the hard way, or you can realize that each step up necessarily is the previous step multiplied by two, plus one. For instance, the only possible combination for 1 length is:
A
For 2 lengths,
A, B, AB
For 3 lengths,
A, B, AB, C, CA, CB, CAB
And so forth. With each step, it's all the possibilities of the previous step, plus all the possibilities of the previous step with the addition of the new variable, plus the new variable alone.

So. From what we've done so far, it looks like it may be possible. 7 lengths renders a maximum of 127 possible, unique combinations—and we only need 67 combinations.

However, the ONLY way to render 7 lengths from 1 with 3 cuts is if three of the lengths are 1 chain long. So, let's see how many possible combinations we can make with different lengths of chain, if 3 of them are the same:

1 length : N/A
2 length : N/A
3 lengths : 3 possible combinations
4 lengths : 7 possible combinations
5 lengths : 15 possible combinations
6 lengths : 31 possible combinations
7 lengths : 63 possible combinations
8 lengths : 127 possible combinations

1 and 2 don't make sense. 3 is this:
A, AA, AAA
4 is:
A, AA, AAA, B, AB, AAB, AAAB
And so forth. As you can see, it's the same pattern as before, just removed by one place.

So. It is IMPOSSIBLE to make 67 different combinations with fewer than 8 lengths, if 3 of them are identical. Furthermore, it is IMPOSSIBLE to make as many as 7 different lengths unless at least 3 of them are identical. Finally, it is IMPOSSIBLE to allow for 67 different combinations with fewer than 7 different lengths. Therefore the problem is not soluble with as few as 3 cuts.

My question is: WHAT WERE THEY THINKING? Can you provide any holes in Nat's theory? They don't have the answer in the book.