Cho số nguyên dương $n$. Chứng minh có ít nhất $2^{n-1}+n$ số có thể chọn từ $\{ 1,2,...,2^n \}$ sao cho với mỗi cặp hai số phân biệt đã chọn $x,y$ ta đều có $x+y$ không là ước của $xy$.
$x+y$ không là ước của $xy$.
#1
Đã gửi 14-04-2005 - 19:12
#2
Đã gửi 10-01-2014 - 11:01
Đề bài nên sửa lại một chút cho khỏi nhầm lẫn :
Chỗ $\left \{ 1,2,...,2^n \right \}$ sửa thành $\left \{ 1,2,3,4,...,2^n \right \}$ để khỏi nhầm với $\left \{ 2^0,2^1,...,2^n \right \}$
Giải :
Từ $\left \{1,2,3,4,...,2^n \right \}$ ta chọn ra $2$ tập hợp như sau :
$A=\left \{ 1,3,5,7,...,2^n-1 \right \}$ ($A$ có tất cả $2^{n-1}$ số, đều là số lẻ)
$B=\left \{ 2^1,2^2,2^3,...,2^n \right \}$ ($B$ có tất cả $n$ số, đều là số chẵn)
Rõ ràng $A$ và $B$ là $2$ tập hợp không có phần tử nào chung.
Ta gọi $C$ là tập hợp gồm tất cả các số của $A$ và $B$ ($C=A\cup B$).Tập $C$ có $2^{n-1}+n$ số.
Ta chứng minh rằng $\forall x,y\in C$ ($x\neq y$) ta có $x+y$ không phải là ước của $xy$.
Có $3$ trường hợp :
$1)$ $x$ và $y$ đều lẻ :
Khi đó $x+y$ là số chẵn, không thể là ước của $xy$ (vì $xy$ khi đó là số lẻ)
$2)$ $x$ và $y$ có $1$ số chẵn và $1$ số lẻ
Gọi số lẻ là $l$, số chẵn là $2^k$ ($1\leqslant k\leqslant n$)
Rõ ràng $l$ và $2^k$ là $2$ số nguyên tố cùng nhau.
Giả sử $l+2^k$ là ước của $l.2^k\Rightarrow l+2^k$ là ước của $l$ hoặc $l+2^k$ là ước của $2^k$ (vì $l$ và $2^k$ nguyên tố cùng nhau)
Nhưng cả $2$ điều đó đều vô lý vì $l+2^k> l$ và $l+2^k> 2^k$
$\Rightarrow$ điều giả sử sai $\Rightarrow$ $l+2^k$ không phải là ước của $l.2^k$ hay $x+y$ không phải là ước của $xy$
$3)$ $x$ và $y$ đều chẵn :
Gọi số lớn hơn là $2^p$, số nhỏ hơn là $2^q$ ($1\leqslant q< p\leqslant n$)
Ta phải chứng minh $2^p+2^q$ không là ước của $2^p.2^q$
Hay $2^{p-q}+1$ không phải là ước của $2^p$
Điều đó là hiển nhiên vì $p> q$ nên $2^{p-q}+1$ là số lẻ lớn hơn $1$, không thể là ước của $2^p$ được.
Vậy trong trường hợp này $x+y$ cũng không phải là ước của $xy$
Vậy $\forall x,y\in C$ ($x\neq y$) ta đều có $x+y$ không phải là ước của $xy$
Trong đó $C$ là tập hợp có $2^{n-1}+n$ số như đã nêu rõ ở trên.
- Zaraki, BlackSelena, DarkBlood và 9 người khác yêu thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh