[ Sorting in ascending (descending) order ] [ Classical combinatorics (other). $\quad]$

a) A traveler stopped at an inn, and the owner agreed to accept rings from a golden chain the traveler wore on his wrist as payment for his stay. However, he set a condition that the payment should be daily: each day the owner should have one more ring than the previous day. The chain, which was closed in a loop, contained 11 rings, and the traveler planned to stay exactly 11 days, so he agreed. What is the minimum number of rings he needs to cut to be able to pay the owner?

b) How many rings should the chain consist of so that the traveler can stay at the inn for the maximum number of days, given that he can only cut $n$ rings?
a) It is enough to cut two rings so that pieces of three and six rings are separated. On the third day, the traveler gives the piece of three rings and receives two rings as change, and on the sixth day, the piece of six rings and receives five rings as change.

b) Arrange the resulting pieces of the chain (not counting the cut rings) in increasing order of the number of rings in them: \(a_{1} \leq a_{2} \leq \ldots\) Clearly, \(a_{1} \leq n+1\) (otherwise, it would be impossible to pay for the \((n+1)\)-th day), \(a_{2} \leq a_{1}+n+1 \leq 2(n+1), a_{3} \leq a_{2}+a_{1}+n+1 \leq 4(n+1), \ldots\) Moreover, the number of pieces does not exceed \(n\). Therefore, the chain contains no more than \(n+(n+1)\left(1+2+2^{2}+\ldots+2^{n-1}\right)=(n+1) 2^{n}-1\) rings.

By taking pieces of the maximum possible length \(\left(a_{k}=(n+1) 2^{k-1}, k=1, \ldots, n\right)\), we obtain a chain of \((n+1) 2^{n}-1\) rings.

## Answer

a) 2 rings. b) From \((n+1) 2^{n}-1\) rings.