Let A={a1,a2,…,an}, where a1<a2<⋯<an. For a finite nonempty set B of positive integers, denote by lcmB and gcdB the least common multiple and the greatest common divisor of the elements in B, respectively. Consider any good partition (A1,A2) of A. By definition, lcmA1=d=gcdA2 for some positive integer d. For any ai∈A1 and aj∈A2, we have ai⩽d⩽aj. Therefore, we have A1={a1,a2,…,ak} and A2={ak+1,ak+2,…,an} for some k with 1⩽k<n. Hence, each good partition is determined by an element ak, where 1⩽k<n. We call such ak partitioning. It is convenient now to define ℓk=lcm(a1,a2,…,ak) and gk=gcd(ak+1,ak+2,…,an) for 1⩽k⩽n−1. So ak is partitioning exactly when ℓk=gk. We proceed by proving some properties of partitioning elements, using the following claim.
Claim. If ak−1 and ak are partitioning where 2⩽k⩽n−1, then gk−1=gk=ak.
Proof. Assume that ak−1 and ak are partitioning. Since ℓk−1=gk−1, we have ℓk−1∣ak. Therefore, gk=ℓk=lcm(ℓk−1,ak)=ak, and gk−1=gcd(ak,gk)=ak, as desired.
Proof. Suppose, to the contrary, that all three numbers ak−1,ak, and ak+1 are partitioning. The claim yields that ak+1=gk=ak, a contradiction.
Property 2. The elements a1 and a2 cannot be simultaneously partitioning. Also, an−2 and an−1 cannot be simultaneously partitioning.
Proof. Assume that a1 and a2 are partitioning. By the claim, it follows that a2=g1=ℓ1=lcm(a1)=a1, a contradiction. Similarly, assume that an−2 and an−1 are partitioning. The claim yields that an−1=gn−1=gcd(an)=an, a contradiction.
Now let A be an n-element set with exactly 2015 good partitions. Clearly, we have n⩾5. Using Property 2, we find that there is at most one partitioning element in each of {a1,a2} and {an−2,an−1}. By Property 1, there are at least ⌊3n−5⌋ non-partitioning elements in {a3,a4,…,an−3}. Therefore, there are at most (n−1)−2−⌊3n−5⌋=⌈32(n−2)⌉ partitioning elements in A. Thus, ⌈32(n−2)⌉⩾2015, which implies that n⩾3024.
Finally, we show that there exists a set of 3024 positive integers with exactly 2015 partitioning elements. Indeed, in the set A={2⋅6i,3⋅6i,6i+1∣0⩽i⩽1007}, each element of the form 3⋅6i or 6i, except 61008, 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 ⌈32(n−2)⌉⩾m obtained in the solution is, in fact, true for any positive integers m and n. Using this bound, one can find that n⩾⌈23m⌉+1.
To show that the bound is sharp, one constructs a set of ⌈23m⌉+1 elements with exactly m good partitions. Indeed, the minimum is attained on the set {6i,2⋅6i,3⋅6i∣0⩽i⩽t−1}∪{6t} for every even m=2t, and {2⋅6i,3⋅6i,6i+1∣0⩽i⩽t−1} for every odd m=2t−1.