[ Tasks with inequalities. Case analysis ] [Examples and counterexamples. Constructions]

## Authors: Khayaturyan A.V., Raskina I.V.

Thirty-three bogatyrs (Russian knights) were hired to guard Lukomorye 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 that Chernomor can get if:

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

b) Chernomor distributes the salary among the squads equally?
From a 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, where $K-$ is the number of detachments. But if there is only one detachment, then since $240=33 \cdot 7+9$, Chernomor will receive only 9 coins. Therefore, it is impossible for Chernomor to receive 32 coins.
a) Let's show how to get 31 coins. For example, Chernomor divides the bogatyrs into two detachments: the first with 32 bogatyrs, and the second with only one. He can give the first detachment 63 coins (from which he will receive 31), and the remaining 177 coins to the single bogatyr in the second detachment.

b) To get 31 coins, Chernomor must divide the bogatyrs into two detachments and give each detachment 120 coins. In this case, from a detachment of $N$ people, he should receive $N-1$ coins. This means that 121 must be divisible by $N$. However, 121 is only divisible by 1, 11, and 121, and it is impossible to sum up to 33 using two such numbers. Therefore, it is impossible for Chernomor to receive 31 coins.

However, it is possible to receive 30 coins. For example, form one detachment of 27 bogatyrs and two detachments of 3 bogatyrs each. Each detachment receives 80 coins, and since 81 is divisible by the number of people in each detachment, the "kickback" will be $26+2+2=30$ coins.

## Answer

a) 31 coins; b) 30 coins.