Baltic Way 2019 · Problem 7

We show first that $k = 32$ is such a number. Consider a partition $\{U, V\}$ of the set $\{2, 3, \dots, 32\}$ where we may assume that $2 \in U$. Towards contradiction, suppose that none of the parts contains numbers $a, b$ and $c$ with the desired property. As $2 \in U$ and $2 \cdot 2 = 4$, we have $4 \in V$. Similarly, $4 \cdot 4 = 16$ implies $16 \in U$. Hence $2, 16 \in U$, but $2 \cdot 8 = 16$, so $8 \in V$. We have concluded that $2, 16 \in U$ and $4, 8 \in V$, but $2 \cdot 16 = 32 = 4 \cdot 8$, which implies that the number $32$ cannot be in any of the parts, which is a contradiction. Therefore, $k = 32$ is a desired number.

We now prove that $k = 32$ is actually the least number with the desired property. We form the partition $\{U, V\}$ of the set $K = \{2, 3, \dots, 31\}$ in the following way. For any number $n \in \mathbb{Z}_+$, consider its prime factorization representation $n = \prod_{i=0}^{k-1} p_i$, and put $\Omega(n) = k$. If $n < 32 = 2^5$, then $n$ is necessarily a product of at most four primes (with repetitions counted) or $\Omega(n) \ge 4$. Put

$$U = \{n \in K \mid \Omega(n) = 1 \text{ tai } \Omega(n) = 4\}$$

and

$$V = \{n \in K \mid \Omega(n) = 2 \text{ tai } \Omega(n) = 3\}.$$

Let $a, b, c \in K$ be numbers with $ab = c$. We observe that $\Omega(c) = \Omega(a) + \Omega(b)$. On the other hand, we have $\Omega(c) \le 4$, as $c \in K$. If now $a, b \in U$, then necessarily $\Omega(a) = \Omega(b) = 1$, which implies $\Omega(c) = 2$ and $c \in V$. If instead of that $a, b \in V$, then $\Omega(a) = \Omega(b) = 2$ and $\Omega(c) = 4$, so $c \in U$. $\square$