[ Inequalities problems. Case analysis ] [Examples and counterexamples. Constructions]

Authors: Khachatryan A.v., Raskina I.v.

Thirty-three bogatyrs (Russian epic heroes) hired themselves 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, 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) We will 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 receive 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 two such numbers to 33. 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 "commission" will be $26+2+2=30$ coins.

## Answer

a) 31 coins; b) 30 coins.

\section*{[ Game Theory (other) ]  Problem 116966 Topics: [ Military Numbering System ]

$$
\text { [ Estimation + Example ] }
$$

## Author: Shapovalov A.V.

Fox Alyosha and Cat Basilio grew 20 fake banknotes on a tree and are now filling in their seven-digit numbers. Each banknote has 7 empty cells for digits. Basilio names one digit "1" or "2" (he knows no others), and Alyosha writes the named digit in any free cell of any banknote and shows the result to Basilio. When all cells are filled, Basilio takes as many banknotes with different numbers as possible (from several with the same number, he takes only one), and the rest go to Alyosha. What is the maximum number of banknotes Basilio can get, no matter how Alyosha acts?

## Solution

Basilio can always get two banknotes: he knows the position where the last digit should be written and names it so that it differs from the digit in the same position on some other banknote. Then the numbers on these two banknotes will be different, and the cat will be able to take them.

We will show how Alyosha can ensure that there are no more than two different numbers. She arranges the banknotes one above the other so that the cells for digits form a table.

When the cat names a "1", Alyosha writes it in the leftmost column with a free cell (in any of the cells), and when the cat names a "2" - in the rightmost column.

If a column starts to receive both ones and twos, then all other columns are already filled: on the left with ones, on the right with twos. Therefore, there will be at most one column where both ones and twos will be written.

Thus, if the numbers differ, they will differ only by the digit in this column. But since there are only two digits, there will be no more than two different numbers.

## $\begin{array}{lllllllll}1 & 1 & 1 & 1 & 2 & 2 & 2\end{array}$  $\begin{array}{lllllll}1 & 1 & 1 & 2 & 2 & 2\end{array}$  $\begin{array}{lll}1 & 1 & 1\end{array} \square 222$  $\begin{array}{lllllll}1 & 1 & 1 & 2 & 2 & 2 & 2\end{array}$  $\begin{array}{llllllll}1 & 1 & 1 & 2 & 2 & 2 & 2\end{array}$

## Answer

2.