uniolympiads Ελληνικά

IMC 2025, Day 2, Problem 7

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

(a) if x∈Mx \in M, then 2x∈M2x \in M,

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

Original from the official PDFLet Z >0 be the set of positive integers. Find all nonempty subsets M ⊆ Z >0 satisfying both of the following properties: (a) if x ∈ M , then 2x ∈ M , x + y (b) if x, y ∈ M and x + y is even, then ∈ M . 2

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Alexandr Bolbot, Novosibirsk State University)

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

Let dd be the greatest common divisor of all members from MM. Then M⊆d Z>0M \subseteq d\,\mathbb{Z}_{>0} and dd is odd. Since dd can be represented in the form

d=v1a1+v2a2+…+vkak−vk+1ak+1−vk+2ak+2−…−vnand = v_1a_1 + v_2a_2 + \ldots + v_ka_k - v_{k+1}a_{k+1} - v_{k+2}a_{k+2} - \ldots - v_na_n
for some ai∈Ma_i \in M and vi∈Z>0v_i \in \mathbb{Z}_{>0}, there exist two members of MM with difference dd.

Let cc be the minimal element of MM, c<ac < a, and a,a+d∈Ma, a+d \in M. We choose the largest x∈Mx \in M such that x<ax < a. Then the only elements of MM in the interval [x,a+d][x, a+d] are xx, aa, and a+da+d, since M⊆d ZM \subseteq d\,\mathbb{Z}. Meanwhile, x<x+a2<ax < \frac{x+a}{2} < a, so x+ax + a must be odd, hence x+a+dx + a + d is even, and then x<x+a+d2<a+dx < \frac{x+a+d}{2} < a + d means x=a−dx = a - d. Thus, the following implication holds:

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

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

a−d,a∈M  ⟹  a+d∈M.a - d, a \in M \implies a + d \in M.

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

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?