Problem 4. Let $n$ be a non-zero natural number; consider the set $M=\{1,2, \ldots, 2 n+1\}$.

Determine in how many ways the set $M$ can be partitioned into three non-empty subsets $A, B, C$ $(A \cup B \cup C=M, A \cap B=B \cap C=C \cap A=\emptyset)$ such that the following conditions are simultaneously satisfied:

(i) for any $a \in A$ and any $b \in B$, the remainder of the division of $a$ by $b$ belongs to the set $C$;

(ii) for any $c \in C$, there exist $a \in A$ and $b \in B$ such that $c$ is the remainder of the division of $a$ by $b$.
Solution. We observe that $a>b$ for any $a \in A$ and $b \in B$. Indeed, otherwise, the remainder of the division of $a$ by $b$ is 0 or $a$, a contradiction. It follows that the set $A$ consists of consecutive natural numbers and $2 n+1 \in A$.

....................................................................................................

Let $b_{1}$ be the smallest element in the set $B$. Since $0 \notin C$, it follows that $2 b_{1}>2 n+1$. We deduce that $2 b>2 n+1$, for any $b \in B$. Thus, the quotients of all divisions of numbers in $A$ by numbers in $B$ are equal to 1.

If there exists $c \in C$ such that $c>b_{1}$, then $c$ is the remainder of the division of a number $a \in A$ by a number $b \in B$. It follows that $a=1 \cdot b+c>b_{1}+b_{1}=2 b_{1}>2 n+1$, a contradiction. We deduce that $c<b$, for any $c \in C$ and $b \in B$.

Therefore, the sets $B$ and $C$ are formed by consecutive natural numbers. ........ $\mathbf{2 p}$

Consider $C=\left\{1,2, \ldots, c_{1}\right\}, 1 \leq c_{1} \leq 2 n-1, B=\left\{c_{1}+1, c_{1}+2, \ldots, c_{1}+m\right\}, 1 \leq m \leq$ $2 n-c_{1}$ and $A=\left\{c_{1}+m+1, c_{1}+m+2, \ldots, 2 n+1\right\}$. The remainder of the division of $2 n+1$ by $c_{1}+1$ is $c_{1}$, so $2 n+1=1 \cdot\left(c_{1}+1\right)+c_{1}$. We deduce that $c_{1}=n$. Therefore, $C=\{1,2, \ldots, n\} . \ldots \mathbf{2 p}$

We have $n$ ways to choose the sets $A$ and $B$, namely $B=\{n+1, n+2, \ldots, m\}$, $A=\{m+1, m+2, \ldots, 2 n+1\}$, where $n+1 \leq m \leq 2 n$. In conclusion, the required partition can be made in $n$ ways. $1 p$

Working time 4 hours.

Each problem is scored out of 7 points.