EGMO 2013 problem 3

Đề bài:
Cho $n$ là một số nguyên dương.
a. Chúng minh rằng tồn tại tập $S\subset \mathbb{Z}^+$ với $|S|=6n$ sao cho bội chung nhỏ nhất của 2 phần tử bất kỳ của $S$ không lớn hơn $32n^2$.
b. Chứng minh rằng với mọi tập $T\subset \mathbb{Z}^+$ với $|S|=6n$ thì tồn tại 2 phần tử của $T$ có bội chung nhỏ nhất lớn hơn $9n^2$.

Lời giải:
a.
Xét 2 tập hợp: $A=\{1;2;3;\ldots;4n\}$, $B=\{4n+2;4n+4;\ldots;8n\}$
Dễ thấy tập $S=A\cap B$ thỏa mãn đề bài.

b.
Bổ đề: Cho $U\subset \mathbb{Z}^+$ với $|U|=m+1,m\ge 2$ và $u\ge m,\forall u\in U$, tồn tại 2 phần tử của $U$ có bội chung nhỏ nhất không nhỏ hơn $m^2$.
Chứng minh bổ đề:
Giả sử các phần tử của $U$ là $m_1>m_2>\ldots>u_{m+1}\ge m$.
Suy ra: $\displaystyle \frac{1}{u_1}\le\frac{1}{u_i}\le\frac{1}{m},\forall i=\overline{1;m+1}$.
Ta chia đoạn $\displaystyle [\frac{1}{u_1};\frac{1}{m}]$ thành $m$ đoạn có độ dài bằng nhau.
Theo nguyên lý Dirichlet, tồn tại $i,j$ với $1\le i<j\le m+1$ sao cho $\displaystyle \frac{1}{u_i};\frac{1}{u_j}$ thuộc cùng 1 đoạn.
Khi đó ta có:
$\displaystyle 0<\frac{1}{u_j}-\frac{1}{u_i}\le\frac{1}{m}\left(\frac{1}{m}-\frac{1}{u_1}\right)<\frac{1}{m^2}$
Từ đó suy ra: $lcm (u_i;u_j)>m^2$, đpcm.
Áp dụng bổ đề với $m=3n+1$ và $U$ là tập $3n+1$ phần tử lớn nhất của $T$.