Let $n$ be an integer larger than $1$ and let $S$ be the set of $n$-element subsets of the set $\{1,2,\ldots,2n\}$. Determine \[\max_{A\in S}\left (\min_{x,y\in A, x \neq y} [x,y]\right )\] where $[x,y]$ is the least common multiple of the integers $x$, $y$.
Problem
Source: Romania TST 2013 Day 4 Problem 2
Tags: least common multiple, number theory unsolved, number theory
numbertheorist17
02.03.2015 03:09
Let $T$ be the set $\{1,2,...,2n\}$. Call the odd value of an element $t\in T$ to be the largest odd divisor of $t$. Note that the odd values are all in the set $\{1,3,...,2n-1\}$. Let $U=\{1,3,...,2n-1\}$. Take any set $A$ in $S$. Note that since there are $n$ elements in $U$ and $n$ elements in $A$, the odd values of two elements in $A$ must be the same or the set of all odd values of the elements of $A$ must be $U$.
Suppose that there are two elements in $A$ with the same odd value. Let these elements be $2^{a}c$ and $2^bc$ where $c\in U$. Thus, since $$[2^ac,2^bc]=2^{max(a,b)}c=max(2^ac,2^bc)\le 2n.$$ Thus, the minimum value of the least common multiple of two elements in $A$ is at most $2n$.
Now, suppose that the odd values of $A$ form the whole set $U$. Therefore, for any two elements of $A$ have different odd values. Suppose that $u$ is an element of $A$ so that $u\le n$. Replacing $u$ by $2u$ will not decrease the minimum value of the least common multiple of two elements in $A$ and this replacement will be valid since $2u\le 2n$ and $u$ has a different odd value from the rest of $A$. Thus, the set $A$ for which the minimum such least common multiple will be a maximum is $\{n+1,n+2,...,2n\}$.
Now, since the odd values of the elements of $A$ are all distinct, $A$ can be represented by the set $\{1\cdot 2^{b_1}, 3\cdot 2^{b_3},...,(2n-1)\cdot 2^{b_{2n-1}}\}$ where the $b_i$ are all nonnegative integers. Notice that if $i<j$ are odd integers then $b_i\ge b_j$ since if $b_i<b_j$, then $$i\cdot 2^{b_i+1}\le i\cdot 2^{b_j}<j\cdot 2^{b_j}\le 2n$$which is a contradiction.
Suppose that $i<j$ are odd integers such that $i|j$. Since $i|j$ and both are odd, $j\ge 3i$. Therefore, $$[2^{b_i}\cdot i, 2^{b_j}\cdot j]=2^{max(b_i,b_j)}\cdot [i,j]=2^{b_i}\cdot j\ge 2^{b_i}\cdot 3i=3\cdot (2^{b_i}\cdot i).$$
Now if $i<j$ are odd integers such that $i\not| j$, then there exists an odd prime $p$ that divides $i$ more times than it divides $j$. Therefore, $[i,j]\ge pj\ge 3j$. Thus, $$[2^{b_i}\cdot i,2^{b_j}\cdot j]=2^{max(b_i,b_j)}\cdot [i,j]\ge 2^{b_i}\cdot 3j=3\cdot (2^{b_i}\cdot j).$$ Thus, the least common multiple of any two elements of $A$ is at least $3\cdot (i\cdot 2^{b_i})$ where $i\cdot 2^{b_i}\in A$ which is at least $3(n+1)$. Thus, the maximum value that is desired is found by taking $A$ to be the set $\{n+1,n+2,...,2n\}$.
If $n$ is an odd integer, then note that $n+1$ is even and that $(n+1)/2\le 2n/3$. Let $i$ be the odd value of $n+1$. Since $(n+1)/2\le 2n/3$, $3i\le 2n$. Therefore, the minimum value of the least common multiple of two elements of $A$ is $3(n+1)$ by taking $i\cdot 2^{b_i}$ and $3i\cdot 2^{b_{3i}}$.
If $n=2$, note that $A=\{3,4\}$ which means that the value that is desired is $12$.
If $n=4$, then $A=\{5,6,7,8\}$. Taking the pairwise least common multiples gives that the desired value is $24$ by taking $6$ and $8$.
Now, let $n$ be an even integer that is at least $6$. Note that $n+2$ is an even integer. Let $u$ be the odd part of $n+2$ and note that $u\le (n+2)/2\le 2n/3$ which implies that $3u\le 2n$. Thus, $3(n+2)$ is an achievable least common multiple of two elements in $A$. In order to show that this is the least possible achievable value, it suffices to show that $[n+1,i]>3(n+2)$ for all $n+1<i\le 2n$. Let $v$ be the odd part of $i$. If $v\le n$, then $b_v\ge 1$ which implies that $$[n+1,i]\ge 3(n+1)\cdot 2^{b_v} \ge 6(n+1)\ge 3(n+2).$$If $v>n$, then $i=v>n+1$ which implies that $$[n+1,i]\ge 3\cdot 2^{b_i}\cdot i\ge 3(n+2).$$Therefore, if $n$ is even, then $3(n+2)$ is the value desired.
Overall, the answer is $\boxed{3(n+1)}$ if $n$ is odd, $\boxed{3(n+2)}$ if $n\ge 6$ is even, $\boxed{12}$ if $n=12$, and $\boxed{24}$ if $n=4$.