16. a) One day, a guest came to the hotel owner, K, without money but with a silver chain consisting of seven links. The owner agreed to keep the guest for a week on the condition that the guest would give him one of the chain links as payment each day. What is the minimum number of links that need to be cut so that the chain owner can pay the hotel owner daily for seven days (possibly taking back previously given links and giving other ones in exchange)?

b) The chain consists of 2000 links. What is the minimum number of links that need to be cut so that any number of links from 1 to 2000 can be collected by taking some number of the resulting parts?
16. a) It is sufficient to saw off one third link; in this case, the chain will break into two parts, containing 2 and 4 links respectively, and one separate (sawed) link. On the first day, the guest will give this link; on the second day, he will take it back and give in exchange the part of the chain consisting of two links; on the third day, he will add the sawed link again; on the fourth day, he will take back everything he gave earlier and hand over the part of the chain consisting of four links; on the fifth day, he will add the sawed link again; on the sixth day, he will take back this link and give in exchange the part of the chain consisting of two links; on the seventh day, he will give the last link.

b) It is convenient to first solve the following problem: for what maximum $n$ is it sufficient to saw $k$ links of an $n$-link chain so that any number of links from 1 to $n$ can be obtained by taking some of the resulting parts? To solve this problem, let's consider the most advantageous arrangement of $k$ sawed links. Since after sawing $k$ links, we will have $k$ separate (sawed) links, we can already collect any number of links from 1 to $k$ from them. But we cannot get $k+1$ links if we do not have a part consisting of $k+1$ or fewer links. It is clear that it is most advantageous to have a part exactly of $k+1$ links; then from this part and $k$ separate links, we can collect any number from 1 to $2k+1$. To be able to get $2k+2=2(k+1)$ links, we need to have a part containing $2(k+1)$ or fewer links; the most advantageous for us will be if this part contains exactly $2(k+1)$ links. Now we can already form all numbers from 1 to $2k+1+2(k+1)=4k+3$; the next largest part we need is a part containing $4(k+1)$ links. Continuing to reason in the same way, we will see that the most advantageous will be if the $k+1$ parts, obtained after we saw $k$ links (the $k$ separate links obtained in this process are not counted here as parts), will have the following numbers of links:

$$
k+1, 2(k+1), 4(k+1), 8(k+1), \ldots, 2^k(k+1)
$$

In this case, any number of links from 1 to

$$
\begin{aligned}
n=k+\{k+1+2(k+1)+ & \left.4(k+1)+\ldots+2^k(k+1)\right\}= \\
& =k+\left(2^{k+1}-1\right)(k+1)=2^{k+1}(k+1)-1
\end{aligned}
$$

can be formed from the parts of the chain.

Thus, if $2^k k \leqslant n \leqslant 2^{k+1}(k+1)-1$, then $k$ cuts of the chain are sufficient, but $k-1$ cuts are not sufficient. In particular,

| for $-2 \leqslant n \leqslant 7$ | $k=1$, | for $160 \leqslant n \leqslant 383$ | $k=5$, |
| :--- | :--- | :--- | :--- |
| for $8 \leqslant n \leqslant 23$ | $k=2$, | for $384 \leqslant n \leqslant 895$ | $k=6$, |
| for $24 \leqslant n \leqslant 63$ | $k=3$, | for $896 \leqslant n \leqslant 2047$ | $k=7$. |
| for $64 \leqslant n \leqslant 159$ | $k=4$, |  |  |

Thus, we see that for $n=2000$, the minimum number of sawed links is 7. The conditions of the problem will be met if these links are chosen so that the 8 resulting parts of the chain (7 separate links are not counted here) have 8, 16, 32, 64, 128, 256, 512, and 977 links respectively.