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 A1 and A2 good if the least common multiple of the elements in A1 is equal to the greatest common divisor of the elements in A2. 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 = {a1, a2, …,an}, where a1 < a2 < …< an. For a finite 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 (A1,A2) of A. By definition, lcm A1 = d = gcd A2 for some positive integer d. For any a_i\in A_1 and a_j\in A_2, we have a a_i\leqslant d\leqslant a_j. Therefore, we have A1 = {a1, a2, …ak} and A2 = {ak+1, ak+2 , …, an} for some k with 1\leqslant k\leqslant n. Hence, each good partition is determined by an element ak, where 1\leqslant k\leqslant n. We call such ak partitioning.

It is convenient now to define lk = lcm {a1, a2, …, ak} and gk = gcd{ ak+1, ak+2, …, an}. For 1\leqslant k\leqslant n-1. So ak is partitioning exactly when lk = gk.

We proceed by proving some properties of partitioning elements, using the following claim. Claim. If ak-1 and ak are partitioning where 2\leqslant k\leqslant n-1, then gk-1 = gk = ak.

Proof. Assume that ak-1 and ak are partitioning. Since lk-1 = gk-1, we have lk-1 | ak. Therefore, gk = lk = lcm(lk-1, ak) = ak, and gk-1 = gcd(ak,gk) = ak, as desired.

Property 1.

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

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 = l1 = lcmp (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\geqslant 5. Using Property 2, we find that there is at most one partitioning element in each of {a1, a2} and {an-2, an-1}. Property 1, there are at least \left \lfloor \frac{n-5}{3} \right \rfloor non-partitioning elements in {a3, a4, …, an-3}. 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 = { 2. 6i, 3.6i, 6i + 1 | 0\leqslant i\leqslant 1007}, each element of the form 3. 6i or 6i , except 61008 is partitioning.

Therefore, the minimum possible value of n is 3024.

Also Read : combinatoric shortlist problem IMO 2015

%d bloggers like this: