International Mathematics Competition
for University Students
2025

IMC2025: Day 2, Problem 7

Problem 7. Let \(\displaystyle \mathbb{Z}_{>0}\) be the set of positive integers. Find all nonempty subsets \(\displaystyle M \subseteq \mathbb{Z}_{>0}\) satisfying both of the following properties:

(a) if \(\displaystyle x \in M\), then \(\displaystyle 2x\in M\),

(b) if \(\displaystyle x, y\in M\) and \(\displaystyle x+y\) is even, then \(\displaystyle \displaystyle\frac{x+y}{2}\in M\).

Alexandr Bolbot, Novosibirsk State University

Solution. Note that \(\displaystyle M\) is closed under addition since \(\displaystyle x+y = \frac{2x+2y}{2}\). Therefore it is closed under multiplication by an arbitrary natural number. Also, \(\displaystyle M\) contains some odd numbers since \(\displaystyle x\in M\) \(\displaystyle \implies\) \(\displaystyle \frac{x+2x}{2} = \frac{3x}{2}\in M\), and we can repeat this until all factors of \(\displaystyle 2\) are removed from a number.

Let \(\displaystyle d\) be the greatest common divisor of all members from \(\displaystyle M\). Then \(\displaystyle M\subseteq d\,\ZZ_{>0}\) and \(\displaystyle d\) is odd. Since \(\displaystyle d\) can be represented in the form

\(\displaystyle d = v_1a_1+ v_2a_2+\ldots + v_k a_k - v_{k+1}a_{k+1} - v_{k+2}a_{k+2}- \ldots - v_n a_n \)

for some \(\displaystyle a_i\in M\) and \(\displaystyle v_i\in \ZZ_{>0}\), there exist two members of \(\displaystyle M\) with difference \(\displaystyle d\).

Let \(\displaystyle c\) be the minimal element of \(\displaystyle M\), \(\displaystyle c<a\), and \(\displaystyle a, a+d\in M\). We choose the largest \(\displaystyle x\in M\) such that \(\displaystyle x<a\). Then the only elements of \(\displaystyle M\) in the interval \(\displaystyle [x,a+d]\) are \(\displaystyle x\), \(\displaystyle a\), and \(\displaystyle a+d\), since \(\displaystyle M\subseteq d\,\ZZ\). Meanwhile, \(\displaystyle x < \frac{x+a}{2} < a\), so \(\displaystyle x+a\) must be odd, hence \(\displaystyle x+a+d\) is even, and then \(\displaystyle x<\frac{x+a+d}{2}<a+d\) means \(\displaystyle x=a-d\). Thus, the following implication holds:

\(\displaystyle (a, a+d \in M \text{ and } c < a) \implies a-d \in M . \)

Similarly, by setting \(\displaystyle x\in M\) to be the smallest such that \(\displaystyle x > a\) (we know that such an element exists, since \(\displaystyle 2a\in M\)), we obtain

\(\displaystyle a-d , a \in M \implies a+d \in M . \)

We thus get that \(\displaystyle M\) is obtained as the set of elements of the arithmetic progression \(\displaystyle c+kd\) (\(\displaystyle k\in\ZZ_{\geq 0}\)). Obviously, this set satisfies both of the properties (a) and (b). Hence, we have proved that \(\displaystyle M\) satisfies these properties if and only if \(\displaystyle M = \{nd\mid m\leqslant n \in \mathbb N\}\) for some \(\displaystyle m\in \mathbb{N}\) and odd \(\displaystyle d\).