Chủ đề này có 1 trả lời

[Zz Isaac Newton Zz]

Cho $n\geq 6$ và tập hợp $S=\left \{ 1,2,...,2n \right \}.$ Chứng minh rằng với mọi cách lấy $n$ phần tử của $S$ bao giờ cũng tìm được hai phần tử có bội chung nhỏ nhất không vượt quá $3n+6.$

[nhungvienkimcuong]

Gọi $A$ là tập hợp chứa $n$ phần tử được chọn. Gọi $m$ là phần tử nhỏ nhất của $A$ và giả sử $m\le n$. Nếu $2m\in A$ thì cặp $(m,2m)$ thỏa đề. Nếu $2m\notin A$, xét tập hợp $A'=(A\setminus\{m\})\cup\{2m\}$. Với mỗi tập hợp $X$, kí hiệu

\[\omega(X)=\min\Big\{\text{BCNN}(a,b):a,b\in X\Big\}.\]

Khi đó $\omega(A)\le \omega(A')$, như vậy nếu mệnh đề đúng với $A'$ thì cũng đúng với $A$.

 

Vậy ta chỉ cần xử lí trong trường hợp $\omega(A)$ lớn nhất, đó là khi $A=\{n+1,n+2,\dots,2n\}$. Tới đây chỉ cần chia ra hai trường hợp chẵn lẻ của $n$.

- $n=2k$ thì $\text{BCNN}(2k+2,3k+3)=6k+6=3n+6$,

- $n=2k+1$ thì $\text{BCNN}(2k+2,3k+3)=6k+6<3n+6$.

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 04-01-2023 - 21:31