Problem 6. Thirty-three bogatyrs (Russian knights) were hired to guard Lake Luka for 240 coins. The cunning Chernomor can divide the bogatyrs into squads of any size (or record all in one squad), and then distribute the entire salary among the squads. Each squad divides its coins equally, and the remainder goes to Chernomor. What is the maximum number of coins Chernomor can get if:

a) Chernomor distributes the salary among the squads as he pleases

b) Chernomor distributes the salary among the squads equally? [8 points] (I.V.Raskina, A.V.Khachaturyan)
Answer. a) 31 coins; b) 30 coins.

Solution. From each detachment of $N$ bogatyrs, Chernomor will receive at most $N-1$ coins in the best case, since the remainder is less than the divisor. Therefore, he will receive no more than $33-K$ coins in total, where $K$ is the number of detachments. Can Chernomor get 32 coins if there is only one detachment? No, because $240: 33=7$ (remainder 9), so Chernomor will receive only 9 coins. He can try to get 31 coins by dividing the bogatyrs into two detachments.

If (part a) the money does not necessarily have to be divided equally, this is quite possible. For example, let the first detachment have 32 bogatyrs, and the second only one. Then the first detachment can be given 63 coins (from which Chernomor will receive 31), and the remaining 177 coins can be given to the single bogatyr in the second detachment. There are many other ways to divide the money.

However, if (part b) the money must be divided equally, this cannot be done. To show this, one could enumerate all the ways to divide the bogatyrs into two detachments, but there is a simpler way. If, by giving a detachment of $N$ people 120 coins, Chernomor expects to receive $N-1$ coins, then the number 121 must be divisible by $N$. However, 121 is only divisible by 1, 11, and 121, and it is impossible to add up to 33 from two such numbers.

However, it is possible to get 30 coins in part b) by dividing the bogatyrs into three detachments and giving each detachment $240: 3 = 80$ coins. The number of people in each detachment must be a divisor of the number $80+1=81$. From three divisors of 81, it is possible to add up to 33: $33=27+3+3$. Let's check: from detachments of three people, Chernomor will receive 2 coins each, and from the detachment of 27 people, he will receive 26 coins, totaling $26+2+2=30$.

## 7th grade