Chain Link 2

We can do this with 4 cuts. First, cut the 5th, 12th, and 21st link. When welding the links shut, combine 2 of the cut links into a chain of length 2. This leaves us with chains of length 1, 2, 4, 6, and 8.

Day 1: You pay with the chain of length 1.
Day 2: The apprentice returns the previous day’s chain and you give him the chain of length 2.
Day 3: You pay with the chain of length 1, giving him 3 links in total.
Day 4: The apprentice returns the previous chains and you give him the chain of length 4.

In fact, as long as you can use these chains to represent all lengths from 1 to 21, you can make your apprentice all previous chains and pay him the exact amount. The representations are as follows:

Day	Breakdown
1	$1$1
2	$2$2
3	$2+1$2+1
4	$4$4
5	$4+1$4+1
6	$4+2$4+2
7	$4+2+1$4+2+1
8	$8$8
9	$8+1$8+1
10	$8+2$8+2
11	$8+2+1$8+2+1
12	$8+4$8+4
13	$8+4+1$8+4+1
14	$8+4+2$8+4+2
15	$8+4+2+1$8+4+2+1
16	$6+8+2$6+8+2
17	$6+8+2+1$6+8+2+1
18	$6+8+4$6+8+4
19	$6+8+4+1$6+8+4+1
20	$6+8+4+2$6+8+4+2
21	$6+8+4+2+1$6+8+4+2+1

To see how this works, a good starting point would be to look at binary representations of numbers. As a refresher, the binary representation of a number indicates how it can be represented as a sum of unique powers of two. For example, $45=32+8+4+1$45=32+8+4+1. If we have chains of length 32, 8, 4, and 1, then we can make a full payment of 45. By extension, if we have chains of length 1, 2, 4, 8, 16, and 32, we can represent all the numbers 0 to 63 (all 6-digit binary numbers). In general, if we have $k$k chains in ascending powers of 2 ($1$1, $2$2, $4$4, … $2^{k-1}$2k−1), you can represent all the numbers from $0$0 to $2^k-1$2k−1.

Unlike the previous puzzle, 21 is 6 more than 15. As earlier mentioned, we can represent all the numbers from 0 to 15 with 4 chains of length 1, 2, 4, and 8. To be conservative, the remaining 6 chain links can be on a single chain. For payments of more than 15 chains, we pay with the chain of length 6, then pay the remainder with the original method (since it will now be within the 0-15 range). That leaves us with 5 chains of length 1, 2, 4, 6, and 8 respectively. We can do this by cutting 4 chain links to produce 5 shorter chains.

Can we do better than 4 cuts? Yes! Notice that if we’re given a chain of length 6 and we cut the 3rd link. From a single cut, we can get 3 pieces of chain of length 2, 3, and 1 (the link we cut).

We still want to split the chain to get shorter chains of length 4, 6, and 8, so let’s cut them at the 5th, 12th, and 21st links. When re-welding the links, we can link 2 of the links to form a 2-length chain, giving us the 5 chains we need.