For a finite set $A$ of positive integers, we call a partition of $A$ into two disjoint nonempty subsets $A_{1}$ and $A_{2}$ good if the least common multiple of the elements in $A_{1}$ is equal to the greatest common divisor of the elements in $A_{2}$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly 2015 good partitions. (Ukraine) Answer. 3024.
Let $A=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}$, where $a_{1}<a_{2}<\cdots<a_{n}$. For a finite nonempty set $B$ of positive integers, denote by $\operatorname{lcm} B$ and $\operatorname{gcd} B$ the least common multiple and the greatest common divisor of the elements in $B$, respectively. Consider any good partition $\left(A_{1}, A_{2}\right)$ of $A$. By definition, $\operatorname{lcm} A_{1}=d=\operatorname{gcd} A_{2}$ for some positive integer $d$. For any $a_{i} \in A_{1}$ and $a_{j} \in A_{2}$, we have $a_{i} \leqslant d \leqslant a_{j}$. Therefore, we have $A_{1}=\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}$ and $A_{2}=\left\{a_{k+1}, a_{k+2}, \ldots, a_{n}\right\}$ for some $k$ with $1 \leqslant k<n$. Hence, each good partition is determined by an element $a_{k}$, where $1 \leqslant k<n$. We call such $a_{k}$ partitioning. It is convenient now to define $\ell_{k}=\operatorname{lcm}\left(a_{1}, a_{2}, \ldots, a_{k}\right)$ and $g_{k}=\operatorname{gcd}\left(a_{k+1}, a_{k+2}, \ldots, a_{n}\right)$ for $1 \leqslant k \leqslant n-1$. So $a_{k}$ is partitioning exactly when $\ell_{k}=g_{k}$. We proceed by proving some properties of partitioning elements, using the following claim. 

Claim. If $a_{k-1}$ and $a_{k}$ are partitioning where $2 \leqslant k \leqslant n-1$, then $g_{k-1}=g_{k}=a_{k}$. 

Proof. Assume that $a_{k-1}$ and $a_{k}$ are partitioning. Since $\ell_{k-1}=g_{k-1}$, we have $\ell_{k-1} \mid a_{k}$. Therefore, $g_{k}=\ell_{k}=\operatorname{lcm}\left(\ell_{k-1}, a_{k}\right)=a_{k}$, and $g_{k-1}=\operatorname{gcd}\left(a_{k}, g_{k}\right)=a_{k}$, as desired. 

Proof. Suppose, to the contrary, that all three numbers $a_{k-1}, a_{k}$, and $a_{k+1}$ are partitioning. The claim yields that $a_{k+1}=g_{k}=a_{k}$, a contradiction. 

Property 2. The elements $a_{1}$ and $a_{2}$ cannot be simultaneously partitioning. Also, $a_{n-2}$ and $a_{n-1}$ cannot be simultaneously partitioning.

Proof. Assume that $a_{1}$ and $a_{2}$ are partitioning. By the claim, it follows that $a_{2}=g_{1}=\ell_{1}=\operatorname{lcm}\left(a_{1}\right)=a_{1}$, a contradiction. Similarly, assume that $a_{n-2}$ and $a_{n-1}$ are partitioning. The claim yields that $a_{n-1}=g_{n-1}=\operatorname{gcd}\left(a_{n}\right)=a_{n}$, a contradiction. 

Now let $A$ be an $n$-element set with exactly 2015 good partitions. Clearly, we have $n \geqslant 5$. Using Property 2, we find that there is at most one partitioning element in each of $\left\{a_{1}, a_{2}\right\}$ and $\left\{a_{n-2}, a_{n-1}\right\}$. By Property 1, there are at least $\left\lfloor\frac{n-5}{3}\right\rfloor$ non-partitioning elements in $\left\{a_{3}, a_{4}, \ldots, a_{n-3}\right\}$. Therefore, there are at most $(n-1)-2-\left\lfloor\frac{n-5}{3}\right\rfloor=\left\lceil\frac{2(n-2)}{3}\right\rceil$ partitioning elements in $A$. Thus, $\left\lceil\frac{2(n-2)}{3}\right\rceil \geqslant 2015$, which implies that $n \geqslant 3024$. 

Finally, we show that there exists a set of 3024 positive integers with exactly 2015 partitioning elements. Indeed, in the set $A=\left\{2 \cdot 6^{i}, 3 \cdot 6^{i}, 6^{i+1} \mid 0 \leqslant i \leqslant 1007\right\}$, each element of the form $3 \cdot 6^{i}$ or $6^{i}$, except $6^{1008}$, is partitioning. 

Therefore, the minimum possible value of $n$ is 3024. 

Comment. Here we will work out the general case when 2015 is replaced by an arbitrary positive integer $m$. Note that the bound $\left\lceil\frac{2(n-2)}{3}\right\rceil \geqslant m$ obtained in the solution is, in fact, true for any positive integers $m$ and $n$. Using this bound, one can find that $n \geqslant\left\lceil\frac{3 m}{2}\right\rceil+1$. 

To show that the bound is sharp, one constructs a set of $\left\lceil\frac{3 m}{2}\right\rceil+1$ elements with exactly $m$ good partitions. Indeed, the minimum is attained on the set $\left\{6^{i}, 2 \cdot 6^{i}, 3 \cdot 6^{i} \mid 0 \leqslant i \leqslant t-1\right\} \cup\left\{6^{t}\right\}$ for every even $m=2 t$, and $\left\{2 \cdot 6^{i}, 3 \cdot 6^{i}, 6^{i+1} \mid 0 \leqslant i \leqslant t-1\right\}$ for every odd $m=2 t-1$.