a) $1,2,...4n, 4n+2, 4n+4,...8n$. b) http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1359755&sid=e95ee7eb1f133def37b2982a84a3eeb5#p1359755

MariusBocanu wrote: b) http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1359755&sid=e95ee7eb1f133def37b2982a84a3eeb5#p1359755 The EGMO version is a bit easier, since if we go by contradiction and let $a_1<a_2<\cdots<a_{6n}$ denote the elements, we have $\frac{a_ia_{i+1}}{a_{i+1}-a_i} \le \frac{a_ia_{i+1}}{(a_i,a_{i+1})} \le 9n^2$, whence $\frac{6n-k}{9n^2} \le \frac{1}{a_k} - \frac{1}{a_{6n}}$ for all $k$. Now $k=3n$ here already gives a contradiction ($a_{3n} \ge 3n$), and in fact we only need a small refinement for the China TST problem.

a) Note that $\text{lcm}(a,b) = ab/\text{gcd}(a,b)$. Consider $S = \{1, 2, \ldots , 4n\} \cup \{4n+2, \ldots 8n\}$. The $\text{lcm}$ of two terms in the formet set is at most $4n(4n-1) < 32n^2$, and the $\text{lcm}$ of any two terms in the latter set is $\tfrac12[8n(8n-2)] < 32n^2$, and the $\text{lcm}$ of a term in the former and a term in the latter set is at most $4n\cdot 8n \leq 32n^2$, so this set works. b) FTSoC assume we have $T = a_1 < a_2 < \ldots < a_{6n}$ such that $\text{lcm}(a_i, a_j) \leq 9n^2$ for all $i \neq j$. Intuitively, this fails by size. Indeed, we can check that\[\frac{a_ia_j}{\gcd(a_i, a_j)} = \text{lcm}(a_i, a_j) \leq 9n^2 \implies \frac{\text{gcd}(a_i, a_j)}{a_ia_j} \geq \frac{1}{9n^2}\]for all pairs $i \neq j$. WLOG consider this statement across all $i < j$. We know $a_j - a_i$ is a multiple of $\text{gcd}(a_i, a_j)$, hence\[\frac{1}{a_i} - \frac{1}{a_j} \geq \frac{\text{gcd}(a_i, a_j)}{a_ia_j} \geq \frac{1}{9n^2}\]for all $i < j$. Consider\[\frac{1}{a_{3n}} - \frac{1}{a_{6n}} = \sum_{i = 3n}^{6n-1} \left(\frac{1}{a_i} - \frac{1}{a_{i+1}}\right) \geq \frac{3n}{9n^2}\]which however, cannot be true, since $a_{3n} \geq 3n$ hence $\tfrac{1}{a_{3n}} \leq \tfrac{3n}{9n^2}$, the desired contradiction.

(a). The set $S=\{2,4,\cdots,8n\}\cup \{1,3,\cdots ,4n-1\}$. The maximum pairwise $lcm$ is $\leq \min\{\frac{8n(8n-2)}{2}, 8n\cdot 4n-1\}< 32n^2$. (b) Let the numbers be $x_1< x_2<\cdots< x_{6n}$. Then, let $L$ be the largest lcm, by definition we have \[L\geq lcm(x_i,x_{i+1} \geq \frac{x_i\cdot x_{i+1}}{x_{i+1}-x_i}\]Taking the reciprocal, \[\frac{1}{L} \leq \frac{1}{x_i}-\frac{1}{x_{i+1}}\]Taking the sum for $i=3n$ to $i=6n-1$ gives \[3n\cdot \frac{1}{L}\leq \frac{1}{x_{3n}} - \frac{1}{x_{6n}} < \frac{1}{3n}\]Thus, $9n^2< L$ and we are done. $\blacksquare$.

(a) Consider the set $S=\{1,2,\ldots,4n-1,4n,4n+2,4n+4,\ldots,8n-2,8n\}$. If there exists two numbers such that the least common multiple is greater than $32n^2$, then their product must be more than $32n^2$. Therefore, both numbers must be between $4n$ and $8n$, but this means that they are both even, so the least common multiple is at most $\frac12(8n)^2=32n^2$. (b) Let the elements of $T$ be $a_1$, $a_2$, $\ldots$, $a_{6n}$. Suppose that the least common multiple of every two elements is at most $9n^2$. Then, $\frac{a_{i+1}a_i}{a_{i+1}-a_i}\leq9n^2$, so $\frac1{a_i}-\frac1{a_{i+1}}\geq\frac1{9n^2}$. Since $a_{3n}\geq3n$, this means that $\frac1{a_{3n}}-\frac1{a_{6n}}<\frac1{3n}$. However, we also have $\frac1{a_{3n}}-\frac1{a_{6n}}\geq\frac{3n}{9n^2}=\frac1{3n}$. This is a contradiction. Therefore, there exists two elements whose least common multiple is more than $9n^2$.

For part (a) take the set $\{1,\ldots,4n,4n+2,\ldots,8n\}$, i.e. all integers in $[1, 4n]$ and all even integers in $[4n+2,8n]$. We can check that this works. For part (b), we employ the bound $\mathrm{lcm}(a,b)\geq \tfrac{ab}{|a-b|}$ where $a \neq b$. Suppose the elements of $T$ are $x_1<x_2<\cdots<x_{6n}$; clearly $x_i\geq i$, so $x_{3n}\geq 3n$. Now suppose that $\mathrm{lcm}(x_i,x_{i+1})\leq 9n^2$ for all $1 \leq i<6n$. We then have $$\frac{x_ix_{i+1}}{x_{i+1}-x_i}\leq 9n^2 \implies \frac{x_{i+1}-x_i}{x_ix_{i+1}} \geq \frac{1}{9n^2} \implies \frac{1}{x_i}-\frac{1}{x_{i+1}} \geq \frac{1}{9n^2} \implies \frac{1}{x_{i+1}}\leq \frac{1}{x_i}-\frac{1}{9n^2}.$$Thus by induction, $$\frac{1}{x_{3n+i}} \leq \frac{1}{x_{3n}}-\frac{i}{9n^2}\leq \frac{1}{3n}-\frac{i}{9n^2},$$but then by setting $i=3n$ we obtain $\tfrac{1}{x_{6n}} \leq 0$: absurd. $\blacksquare$

Maybe a lil misplaced for a p3 For part a, take 1,2,...,4n, 4n+2,4n+4,...,8n, which works since both elements have to be in (4n,8n) to have a chance at larger lcm but they have a common factor of 2, whence at most (8n-2)(8n)/2<32n^2. For part b, suppose FTSOC not: \lcm(x,y)=\frac{xy}{\gcd(x-y,y)}\ge\frac{xy}{x-y}\implies\frac{x_ix_{i+1}}{x_{i+1}-x_i}\le\lcm(x_{i+1},x_i)\le9n^2\implies\frac{1}{x_i}-\frac{1}{x_{i+1}}\ge\frac{1}{9n^2} \implies\frac{1}{x_{i+1}}\le\frac{1}{x_i}-\frac{1}{9n^2}\implies\frac{1}{x_{6n}}\le x_{3n}-\frac{3n}{9n^2}\le0, contradiction.

Wow neat problem! Solved with Amazing Aarav aka everythingpi3141592 For part a, take the first $4n$ evens and the first $2n$ odds. This works because, the least common multiple of any two even numbers is at most $lcm(8n,8n-2)$, any two odds is at most $lcm(4n-1,4n-3)$ and one even and one odd is at most $lcm(8n,4n-1)$, and in all cases, the least common multiple is strictly less than $32n^2$. As of part b, enumerate ascendingly $a_i$, we can easily get that: \[\frac{1}{a_i}-\frac{1}{a_j}\geq \frac{(j-i)}{9n^2}\]Here plug $i=3n$ and $j=6n$ to get that $3n>a_{3n}$, a contradiction to $a_{3n}\ge 3n$ and so we are done. Remarks. I think part a construction is mainly about realizing that the dumbest thing works, i.e. first you try to begin with the first 5n consecutive naturals, and then you realize adding n more is a difficult task, then you think why not first 4n evens? Once you think this, the reason as to why $32$ was the chosen constant becomes clear and you're done. For part b however, I think having a good theoretical base helps.

For part (a), take all the integers between $1, 2, \dots, 4n$ and the even integers between $4n+2, 4n+4, \dots, 8n$. For part (b), we use the (pretty common) bound \[\frac 1{9n^2} \leq\frac 1{\operatorname{lcm}(a_i, a_{i+1})} = \frac{\gcd(a_i, a_{i+1})}{a_ia_{i+1}} \leq \frac{a_{i+1}-a_i}{a_ia_{i+1}} =\frac 1{a_i} - \frac 1{a_{i+1}}.\]In particular, sorting $T$ in order as $a_1, a_2, \dots, a_{6n}$, we obtain that $\frac 1{a_{3n}} \geq \frac 1{a_{6n}} +\frac 1{3n} > \frac 1{3n}$, i.e. $a_{3n} < 3n$, contradiction. But why write nice solutions when you can write horrible ones? Observe that for $k \geq 3$, any elements $a, b$ of $T$ both in the interval $[kn, (k+1)n)$ must have GCD at least $\left \lfloor \frac{k^2}9 \right \rfloor + 1$; otherwise their LCM will be greater than $9n^2$. It follows that they differ by at least $\left \lfloor \frac{k^2}9 \right \rfloor + 1 \geq \frac{k^2+2}9$ for $3 \nmid k$, as $7$ is the greatest quadratic residue mod $9$. As such, by summing over all intervals, there can be at most \[T \leq \left(3+ \sum_{k=1}^\infty \frac 1{k^2+1} + \sum_{k=1}^\infty \frac 9{(3k+1)^2 + 2} + \sum_{k=1}^\infty \frac 9{(3k+2)^2 + 2}\right)n\]elements, where the first term in the sum accounts for $3 \mid k$ cases. We can estimate this sum by hand. In particular, \[\sum_{k=1}^\infty \frac 9{(3k+1)^2 + 2} < \frac{13}{17} + \int_3^\infty \frac 9{(3k+1)^2 + 2} = \frac{13}{17} + \frac{3(\pi - 2\arctan(5\sqrt 2))}{2\sqrt 2}.\]Small angle approximation gives $\pi - 2\arctan(5\sqrt 2) < \frac{\sqrt 2}5$, so \[\sum_{k=1}^\infty \frac 9{(3k+1)^2+2} < \frac{181}{170}.\]Similarly, \[\sum_{k=1}^\infty \frac 9{(3k+1)^2 + 1} < \frac{1469}{2706} + \int_3^\infty \frac 9{(3k+2)^2+2} = \frac{1469}{2706} + \frac{3\left(\pi-2\arctan\left(\frac{11}{\sqrt 2}\right)\right)}{2\sqrt 2} < \frac{1469}{2706} + \frac 3{11} = \frac{2207}{2706}.\]Finally, \[\sum_{k=1}^\infty \frac 1{k^2+1} < \frac{73}{85}+ \int_4^\infty \frac 1{k^2+1} = \frac{73}{85} + \frac{\pi-2\arctan 4}2 < \frac{73}{85} + \frac 14 = \frac{377}{340}.\]In total, the sum \[|T| < \left(3 + \frac{377}{340} + \frac{2207}{2706} + \frac{181}{170}\right)n = \frac{2755117n}{460020} < 6n\]thus done!

For the first part, consider $$1,2,3\dots,4n-1,4n,4n+2,4n+4,\dots 8n.$$If both numbers are even, the LCM is at most $\frac{8n(8n-2)}{2}$, otherwise, the LCM is at most the product which is at most $8n(4n-1)$. Now, for the second part, suppose FTSOC all LCMs are at most $9n^2$. The main idea is that two relatively large numbers can't be too close together as then they would have a large LCM, so we lower-bound the sequence and show that this causes the final term to be greater than $9n^2$. Precisely, if we let the numbers be $a_1\dots a_{6n}$ in increasing order, Claim: $$a_{k+1}\geq \frac{9n^2a_k}{9n^2-a_k}.$$ We have $$\frac{a_ka_{k+1}}{a_{k+1}-a_k}\leq 9n^2$$since the GCD is at most $a_{k+1}-a_k$. Rearranging gives the desired bound. Now, note that $r_{3n}\geq 3n$. We will use this to inductively show the following lower bound on $a_k$: Claim: For $k\geq 3n$, we have $$a_k>\frac{9n^2}{6n+1-k}.$$ Clearly this is true for $k=3n$. If $k$ works, then $$a_{k+1}\geq \frac{9n^2a_k}{9n^2-a_k}$$$$>\frac{9n^2\frac{9n^2}{6n+1-k}}{9n^2-\frac{9n^2}{6n+1-k}}$$$$=\frac{9n^2}{6n+1-k-1}=\frac{9n^2}{6n-k},$$as desired. Thus, $a_{6n}>9n^2$ and we are done.