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.$
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.$
#1
Posted 07-09-2018 - 22:14
#2
Posted 04-01-2023 - 21:26
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$.
Edited by nhungvienkimcuong, 04-01-2023 - 21:31.
- Hoang72 likes this
Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users