Problem 1672

Let $a_1 < a_2 < \dots < a_{3n+2}$ be the positive integers in our set. For each good division of the set into subsets $A_1$ and $A_2$ the least common multiple of the numbers from $A_1$ is greater than or equal to all of the elements of $A_1$. Similarly, the greatest common divisor of the numbers in $A_2$ is smaller than or equal to all the numbers in $A_2$. So, all the numbers in $A_1$ have to be smaller than all of the numbers in $A_2$ and any good division can only be of the form
$$A_1 = \{a_1, a_2, \dots, a_k\} \text{ in } A_2 = \{a_{k+1}, a_{k+2}, \dots, a_{3n+2}\},$$
where $1 \le k \le 3n+1$.

For each good division let us call the greatest element $a_k$ of $A_1$ the *dividing number*. For each $k$, $1 \le k \le 3n+1$, let $l_k$ denote the least common multiple of the numbers $a_1, \dots, a_k$ and let $d_k$ denote the greatest common divisor of the numbers $a_{k+1}, \dots, a_{3n+2}$.

At the moment we have $3n+1$ divisions which can potentially be good. We have to show that there are at most $2n$ good divisions. We observe the validity of the following propositions.

Proposition 1: If $a_k$ and $a_{k+1}$ are both dividing numbers then we have $d_k = l_k = d_{k+1} = l_{k+1} = a_{k+1}$.

*Proof:* Since $a_k$ and $a_{k+1}$ are both dividing we have $d_k = l_k$ and $d_{k+1} = l_{k+1}$. Also, $l_{k+1} = \text{lcm}(a_{k+1}, l_k)$ and $d_k = \text{gcd}(a_{k+1}, d_{k+1})$. But $l_k = d_k|a_{k+1}$, so $l_{k+1} = \text{lcm}(a_{k+1}, l_k) = a_{k+1}$. Similarly, $a_{k+1} = l_{k+1} = d_{k+1}$, so $d_k = \text{gcd}(a_{k+1}, d_{k+1}) = a_{k+1}$.

Proposition 2: The numbers $a_{k-1}$, $a_k$ and $a_{k+1}$ cannot all be dividing numbers.

*Proof:* If they were, then by Proposition 1 we would have $a_k = d_k = d_{k+1} = a_{k+1}$, which contradicts the assumption that the elements of the set $A$ are all distinct.

Proposition 3: The numbers $a_1$ and $a_2$ cannot both be dividing numbers.

*Proof:* If they were, then by Proposition 1 we would have $a_1 = l_1 = l_2 = a_2$, which contradicts the assumption that $a_1 < a_2$.

Proposition 4: The numbers $a_{3n}$, $a_{3n+1}$ cannot both be dividing numbers.

*Proof:* If they were, then by Proposition 1 we would have $a_{3n+1} = d_{3n+1} = a_{3n+2}$, which contradicts the assumption that $a_{3n+1} < a_{3n+2}$.

There are $3n+1$ candidates for the dividing numbers (i.e. $a_1, a_2, \dots, a_{3n+1}$). However, out of any three subsequent numbers at most two can be dividing numbers. Also, the first two and the last two cannot both be dividing numbers. So, the number of good divisions is at most $\frac{2((3n+2)-2)}{3} = 2n$.

Consider the set
$$\begin{aligned} B &= \{6^i, 2 \cdot 6^i, 3 \cdot 6^i \mid 0 \le i \le n-1\} \cup \{6^n, 2 \cdot 6^n\} \\ &= \{1, 2, 3, 6, \dots, 3 \cdot 6^{n-1}, 6^n, 2 \cdot 6^n\}. \end{aligned}$$
In this set the dividing numbers are exactly $1, 6^1, \dots, 6^{n-1}$ and $3, 3 \cdot 6^1, \dots, 3 \cdot 6^{n-1}$. There are $2n$ of them, which shows that a set with $3n+2$ numbers that has $2n$ good divisions, exists.