# Determine the minimum value for good partitions

Solution IMO 2015 ( combinatoric shortlist problem 3)

**Problem 3:**

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.

Also Read:

Answer. 3024.

Solution. Let A = {a_{1}, a_{2}, …,a_{n}}, where a_{1} < a_{2} < …< a_{n}. For a ﬁnite nonempty set B of positive integers, denote by lcm B and gcd B the least common multiple and the greatest common divisor of the elements in B, respectively.

Consider any good partition (A_{1},A_{2}) of A. By deﬁnition, lcm A_{1} = d = gcd A_{2} for some positive integer d. For any and , we have a . Therefore, we have A_{1} = {a_{1}, a_{2}, …a_{k}} and A_{2} = {a_{k+1}, a_{k+2} , …, a_{n}} for some k with . Hence, each good partition is determined by an element a_{k}, where . We call such a_{k} partitioning.

It is convenient now to define l_{k} = lcm {a_{1}, a_{2}, …, a_{k}} and g_{k} = gcd{ a_{k+1}, a_{k+2}, …, a_{n}}. For . So a_{k} is partitioning exactly when l_{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 , then g_{k-1} = g_{k} = a_{k}.

**Proof**. Assume that a_{k-1} and a_{k} are partitioning. Since l_{k-1} = g_{k-1}, we have l_{k-1} | a_{k}. Therefore, g_{k} = l_{k} = lcm(l_{k-1}, a_{k}) = a_{k}, and g_{k-1} = gcd(a_{k},g_{k}) = a_{k}, as desired.

Property 1.

For every k = 2, 3, . . . , n – 2, at least one of a_{k-1}, a_{k}, and a_{k+1} is not partitioning.

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} = l_{1} = lcmp (a_{1}) = 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} = gcd ( a_{n} ) = a_{n}. a contradiction.

Now let A be an n-element set with exactly 2015 good partitions. Clearly, we have . Using Property 2, we ﬁnd that there is at most one partitioning element in each of {a_{1}, a_{2}} and {a_{n-2}, a_{n-1}}. Property 1, there are at least non-partitioning elements in {a_{3}, a_{4}, …, a_{n-3}}. Therefore, there are at most (n – 1) – 2 – partitioning elements in A. Thus, , which implies that .

Finally, we show that there exists a set of 3024 positive integers with exactly 2015 partitioning elements. Indeed, in the set A = { 2. 6^{i}, 3.6^{i}, 6^{i + 1} | }, each element of the form 3. 6^{i} or 6^{i} , except 6^{1008} is partitioning.

Therefore, the minimum possible value of n is 3024.

**Also Read : combinatoric shortlist problem IMO 2015**