Maths Olympiad Prep

Library / /456 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Find the answer

For a finite set AA of positive integers, we call a partition of AA into two disjoint nonempty subsets A1A_{1} and A2A_{2} good if the least common multiple of the elements in A1A_{1} is equal to the greatest common divisor of the elements in A2A_{2}. Determine the minimum value of nn such that there exists a set of nn positive integers with exactly 2015 good partitions. (Ukraine) Answer. 3024.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let A={a1,a2,,an}A=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}, where a1<a2<<ana_{1}<a_{2}<\cdots<a_{n}. For a finite nonempty set BB of positive integers, denote by lcmB\operatorname{lcm} B and gcdB\operatorname{gcd} B the least common multiple and the greatest common divisor of the elements in BB, respectively. Consider any good partition (A1,A2)\left(A_{1}, A_{2}\right) of AA. By definition, lcmA1=d=gcdA2\operatorname{lcm} A_{1}=d=\operatorname{gcd} A_{2} for some positive integer dd. For any aiA1a_{i} \in A_{1} and ajA2a_{j} \in A_{2}, we have aidaja_{i} \leqslant d \leqslant a_{j}. Therefore, we have A1={a1,a2,,ak}A_{1}=\left\{a_{1}, a_{2}, \ldots, a_{k}\right\} and A2={ak+1,ak+2,,an}A_{2}=\left\{a_{k+1}, a_{k+2}, \ldots, a_{n}\right\} for some kk with 1k<n1 \leqslant k<n. Hence, each good partition is determined by an element aka_{k}, where 1k<n1 \leqslant k<n. We call such aka_{k} partitioning. It is convenient now to define k=lcm(a1,a2,,ak)\ell_{k}=\operatorname{lcm}\left(a_{1}, a_{2}, \ldots, a_{k}\right) and gk=gcd(ak+1,ak+2,,an)g_{k}=\operatorname{gcd}\left(a_{k+1}, a_{k+2}, \ldots, a_{n}\right) for 1kn11 \leqslant k \leqslant n-1. So aka_{k} is partitioning exactly when k=gk\ell_{k}=g_{k}. We proceed by proving some properties of partitioning elements, using the following claim.

Claim. If ak1a_{k-1} and aka_{k} are partitioning where 2kn12 \leqslant k \leqslant n-1, then gk1=gk=akg_{k-1}=g_{k}=a_{k}.

Proof. Assume that ak1a_{k-1} and aka_{k} are partitioning. Since k1=gk1\ell_{k-1}=g_{k-1}, we have k1ak\ell_{k-1} \mid a_{k}. Therefore, gk=k=lcm(k1,ak)=akg_{k}=\ell_{k}=\operatorname{lcm}\left(\ell_{k-1}, a_{k}\right)=a_{k}, and gk1=gcd(ak,gk)=akg_{k-1}=\operatorname{gcd}\left(a_{k}, g_{k}\right)=a_{k}, as desired.

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

Property 2. The elements a1a_{1} and a2a_{2} cannot be simultaneously partitioning. Also, an2a_{n-2} and an1a_{n-1} cannot be simultaneously partitioning.

Proof. Assume that a1a_{1} and a2a_{2} are partitioning. By the claim, it follows that a2=g1=1=lcm(a1)=a1a_{2}=g_{1}=\ell_{1}=\operatorname{lcm}\left(a_{1}\right)=a_{1}, a contradiction. Similarly, assume that an2a_{n-2} and an1a_{n-1} are partitioning. The claim yields that an1=gn1=gcd(an)=ana_{n-1}=g_{n-1}=\operatorname{gcd}\left(a_{n}\right)=a_{n}, a contradiction.

Now let AA be an nn-element set with exactly 2015 good partitions. Clearly, we have n5n \geqslant 5. Using Property 2, we find that there is at most one partitioning element in each of {a1,a2}\left\{a_{1}, a_{2}\right\} and {an2,an1}\left\{a_{n-2}, a_{n-1}\right\}. By Property 1, there are at least n53\left\lfloor\frac{n-5}{3}\right\rfloor non-partitioning elements in {a3,a4,,an3}\left\{a_{3}, a_{4}, \ldots, a_{n-3}\right\}. Therefore, there are at most (n1)2n53=2(n2)3(n-1)-2-\left\lfloor\frac{n-5}{3}\right\rfloor=\left\lceil\frac{2(n-2)}{3}\right\rceil partitioning elements in AA. Thus, 2(n2)32015\left\lceil\frac{2(n-2)}{3}\right\rceil \geqslant 2015, which implies that n3024n \geqslant 3024.

Finally, we show that there exists a set of 3024 positive integers with exactly 2015 partitioning elements. Indeed, in the set A={26i,36i,6i+10i1007}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 36i3 \cdot 6^{i} or 6i6^{i}, except 610086^{1008}, is partitioning.

Therefore, the minimum possible value of nn is 3024.

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

To show that the bound is sharp, one constructs a set of 3m2+1\left\lceil\frac{3 m}{2}\right\rceil+1 elements with exactly mm good partitions. Indeed, the minimum is attained on the set {6i,26i,36i0it1}{6t}\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=2tm=2 t, and {26i,36i,6i+10it1}\left\{2 \cdot 6^{i}, 3 \cdot 6^{i}, 6^{i+1} \mid 0 \leqslant i \leqslant t-1\right\} for every odd m=2t1m=2 t-1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.