(BÀI TẬP CƠ BẢN VỀ PHẦN TỬ CỦA TẬP HỢP HỮU HẠN)
Bài 2 : Cho n là số nguyên dương lớn hơn 1 và S là tập hợp các tập con gồm n phần tử của tập hợp $\left \{1,2,...,2n \right \}$ . Xác định $\underset{A\in S}{max}\left ( \underset{x,y\in A :x\neq y}{min}[x;y] \right )$, ở đây $[x,y]$ là BCNN của x và y.
(RMN_MO 2013)
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 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 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\leq 2n$ and 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\geq 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 that divides more times than it divides .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 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 is an odd integer, then note that $n +1$ is even and that $(n+1)/2\le 2n/3$. Let 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=\left \{ 3,4 \right \}$ which means that the value that is desired is $12$.
If $n=4$, then $A=\left \{ 5,6,7,8 \right \}$. Taking the pairwise least common multiples gives that the desired value is 24 by taking 6 and 8.
Now, let be an even integer that is at least 6. Note that $n+2$ is an even integer. Let be the odd part of $n+2$ and note that $u\le (n+2)/2\le 2n/3$ which implies that $3u\leq 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 be the odd part of . If $v\leq n$, then $b_{v}\geq 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\geq 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\geq 6$ is even, if $n=12$, and if $n=4$.
Bài viết đã được chỉnh sửa nội dung bởi BurakkuYokuro11: 21-08-2018 - 08:48