Baltic Way 1997 · Problem 18

Solution: a) Let $A$ be the set of non-negative integers whose only non-zero decimal digits are in even positions counted from the right, and $B$ the set of non-negative integers whose only non-zero decimal digits are in odd positions counted from the right. It is obvious that $A$ and $B$ have the required property.

b) Since the only possible representation of $0$ is $0+0$, we have $0 \in A \cap B$. The only possible representations of $1$ are $1+0$ and $0+1$. Hence $1$ must belong to at least one of the sets $A$ and $B$. Let $1 \in A$, and let $k$ be the smallest positive integer such that $k \notin A$. Then $k>1$. If any number $b$ with $0<b<k$ belonged to $B$, it would have the two representations $b+0$ and $0+b$. Hence no such number belongs to $B$. Also, in $k=a+b$ with $a \in A$ and $b \in B$ the number $b$ cannot be $0$ since then $a=k$, contradicting the assumption that $k \notin A$. Hence $b=k$, and $k \in B$.

Consider the decomposition of $A$ into the union $A_{1} \cup A_{2} \cup \cdots$ of its maximal subsets $A_{1}, A_{2}, \ldots$ of consecutive numbers, where each element of $A_{1}$ is less than each element of $A_{2}$ etc. In particular, $A_{1}=\{0,1, \ldots, k-1\}$. By our assumption the set of all non-negative integers is the union of non-intersecting sets $A_{n}+b=\left\{a+b \mid a \in A_{n}\right\}$ with $n \in \mathbb{N}$ and $b \in B$, each of these consisting of some number of consecutive integers. We will show that each subset $A_{n}$ has exactly $k$ elements. Indeed, suppose $m$ is the smallest index for which the number $l$ of elements in $A_{m}$ is different from $k$, then $l<k$ since $A_{m}+0$ and $A_{m}+k$ do not overlap. Denoting by $c$ the smallest element of $A_{m}$, we have $c+k-1 \notin A$, so $c+k-1=a+b$ with $a \in A$ and $0 \neq b \in B$. Hence, $b \geqslant k$ and $a<c$. Suppose $a \in A_{n}$, then $n<m$ and the subset $A_{n}$ has $k$ elements. But then $A_{n}+b$ overlaps with either $A_{m}+0$ or $A_{m}+k$, a contradiction.

Hence, the set of non-negative integers is the union of non-intersecting sets $A_{n}+b$ with $n \in \mathbb{N}$ and $b \in B$, each of which consists of $k$ consecutive integers. The smallest element of each of these subsets is a multiple of $k$. Since each integer $b \in B$ is the smallest element of $A_{1}+b$, it follows that each $b \in B$ is a multiple of $k$.