Problem 1880

Answer: 3024

Suppose $A = \{a_1, a_2, \cdots, a_n\}$, where $a_1 < a_2 < \cdots < a_n$. For any nonempty set of positive integers $B$, let $l(B)$ and $g(B)$ denote the least common multiple and the greatest common divisor of all its elements, respectively.

Consider all good partitions $(A_1, A_2)$ of $A$. By definition, for all $a_i \in A_1$ and $a_j \in A_2$, we must have $a_i \le l(A_1) = g(A_2) \le a_j$, so there must exist $1 \le k < n$ such that $A_1 = \{a_1, a_2, \cdots, a_k\}$ and $A_2 = \{a_{k+1}, \cdots, a_n\}$. Below we refer to such a partition as the $a_k$ partition, and let $l_k = l(a_1, a_2, \cdots, a_k)$, $g_k = g(a_{k+1}, \cdots, a_n)$.

Now, note the following properties:

- Property 1: If both $a_{k-1}$ and $a_k$ are good partitions, then $g_{k-1} = g_k = a_k$.

Proof: Note that $l_{k-1} = g_{k-1}|a_k$, so $g_k = l_k = l(l_{k-1}, a_k) = a_k$, and $g_{k-1} = g(a_k, g_k) = a_k$.

- Property 2: Among $a_{k-1}$, $a_k$ and $a_{k+1}$, at least one is not a good partition.

Proof: If not, by Property 1, $a_k = g_k = a_{k+1}$, a contradiction.

- Property 3: $a_1$ and $a_2$ cannot both be good partitions. Likewise, $a_{n-2}$ and $a_{n-1}$ cannot both be good partitions.

Proof: If both $a_1$ and $a_2$ are good partitions, then by Property 1, $a_2 = g_1 = l_1 = a_1$, a contradiction. The second part is similar.

Now, suppose $|A| = n$. By Property 3, at most one of $\{a_1, a_2\}$ is a good partition, and at most one of $\{a_{n-2}, a_{n-1}\}$ is a good partition as well. Also, by Property 2, among $\{a_3, \cdots, a_{n-3}\}$ there are at least $[(n-5)/3]$ partitions that are not good. Combining the above, the number of good partitions is at most $(n-1)\cdot 2 - \lfloor \frac{n-5}{3} \rfloor = \lfloor \frac{2(n-2)}{3} \rfloor \ge 2015$, hence $n \ge 3024$.

Finally, we show that 3024 indeed satisfies the requirements of the problem. Consider $A = \{2 \times 6^i, 3 \times 6^i, 6^{i+1}\mid 0 \le i \le 1007\}$. Then all $3 \times 6^i$ and $6^i$ (except $6^{1007}$) are good partitions.