Let $n$ be a positive integer and $M = {1, 2, . . . , 2n + 1}$. Find out in how many ways we can split the set $M$ into three mutually disjoint nonempty sets $A,B,C$ so that both the following are true: (i) for each $a \in A$ and $b \in B$, the remainder of the division of $a$ by $b$ belongs to $C$ (ii) for each $c \in C$ there exists $a \in A$ and $b \in B$ such that $c$ is the remainder of the division of $a$ by $b$.
Problem
Source:
Tags: number theory
rms
18.08.2024 19:44
parmenides51 wrote: Let $n$ be a positive integer and $M = {1, 2, . . . , 2n + 1}$. Find out in how many ways we can split the set $M$ into three mutually disjoint nonempty sets $A,B,C$ so that both the following are true: (i) for each $a \in A$ and $b \in B$, the remainder of the division of $a$ by $b$ belongs to $C$ (ii) for each $c \in C$ there exists $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 \), which is a contradiction. It follows that the set \( A \) consists of consecutive natural numbers and \( 2n + 1 \in A \).
If \( c \in C \), then there exists \( a \in A \) and \( b \in B \) such that \( a = bq + c \geq 2c + 1 \), therefore \( 2n + 1 \geq 2c + 1 \Rightarrow n \geq c \).
Assuming that \( n + 1 \notin B \), it follows that \( n + 1 \notin A \), so the set \( \{n + 1, n + 2, \ldots, 2n + 1\} \subset A \). If \( b \in B \), then \( b \leq n \), and since \( A \) consists of \( n+1 \) consecutive numbers, it follows that \( A \) contains at least one multiple of \( b \), which is a contradiction.
Therefore, \( n + 1 \in B \), so there exists \( k \in \{n + 1, n + 2, \ldots, 2n\} \) such that \( A = \{2n + 1, 2n, \ldots, k + 1\} \).
Given that \( c \leq n \) for any \( c \in C \), it follows that \( \{n + 1, n + 2, \ldots, k\} \subset B \).
The remainders of the elements of \( A \) when divided by the elements of \( \{n + 1, n + 2, \ldots, k\} \) are the numbers \( \{1, 2, \ldots, n\} \). Thus, \( B = \{n + 1, n + 2, \ldots, k\} \) and \( C = \{1, 2, \ldots, n\} \), as \( k \) traverses the set \( \{n + 1, n + 2, \ldots, 2n\} \), we have \( n \) ways of partitioning.