Cho tập hợp $X= \{ 1,2,3...,n \} \subset \mathbb{N}$. Gọi $A$ là con của tập con của $X$ thỏa mãn điều kiện tồn tại 2 phần tử bất kì $a,b$ sao cho $a \vdots b$.
Tìm số nguyên dương $m$ nhỏ nhất sao cho $|A| =m$.
Cho tập hợp $X= \{ 1,2,3...,n \} \subset \mathbb{N}$. Gọi $A$ là con của tập con của $X$ thỏa mãn điều kiện tồn tại 2 phần tử bất kì $a,b$ sao cho $a \vdots b$.
Tìm số nguyên dương $m$ nhỏ nhất sao cho $|A| =m$.
Cho tập hợp $X= \{ 1,2,3...,n \} \subset \mathbb{N}$. Gọi $A$ là con của tập con của $X$ thỏa mãn điều kiện tồn tại 2 phần tử bất kì $a,b$ sao cho $a \vdots b$.
Tìm số nguyên dương $m$ nhỏ nhất sao cho $|A| =m$.
Đề bài này có vấn đề.Có lẽ nên sửa lại như thế này :
Cho tập hợp $X=\left \{ 1,2,3,...,n \right \}\subset \mathbb{N}$.Gọi $A$ là tập con của $X$ thỏa mãn điều kiện $\forall a,b\in A$ ($a> b$) ta đều có $a\vdots b$
Tìm số nguyên dương $m$ NHỎ nhất (hay LỚN nhất) sao cho $\left | A \right |=m$.
Giải :
+ Nếu là tìm số nguyên dương $m$ NHỎ nhất sao cho $\left | A \right |=m$ thì dễ thấy $m=2$ (khi đó $A=\left \{ 1,k \right \}$ trong đó $k\in X$ và $k\neq 1$)
+ Nếu là tìm số nguyên dương $m$ LỚN nhất sao cho $\left | A \right |=m$ :
Khi đó các phần tử của $A$ sẽ là $2^0;2^1;2^2;2^3;...;2^{m-1}$
Trong đó $2^{m-1}\leqslant n< 2^m\Leftrightarrow m-1\leqslant log_{2}n< m$
Hay $m=p+1$ với $p$ là phần nguyên của $log_{2}n$
...
Ðê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 ...
Đề bài này có vấn đề.Có lẽ nên sửa lại như thế này :
Cho tập hợp $X=\left \{ 1,2,3,...,n \right \}\subset \mathbb{N}$.Gọi $A$ là tập con của $X$ thỏa mãn điều kiện $\forall a,b\in A$ ($a> b$) ta đều có $a\vdots b$
Tìm số nguyên dương $m$ NHỎ nhất (hay LỚN nhất) sao cho $\left | A \right |=m$.
Giải :
+ Nếu là tìm số nguyên dương $m$ NHỎ nhất sao cho $\left | A \right |=m$ thì dễ thấy $m=2$ (khi đó $A=\left \{ 1,k \right \}$ trong đó $k\in X$ và $k\neq 1$)
+ Nếu là tìm số nguyên dương $m$ LỚN nhất sao cho $\left | A \right |=m$ :
Khi đó các phần tử của $A$ sẽ là $2^0;2^1;2^2;2^3;...;2^{m-1}$
Trong đó $2^{m-1}\leqslant n< 2^m\Leftrightarrow m-1\leqslant log_{2}n< m$
Hay $m=p+1$ với $p$ là phần nguyên của $log_{2}n$
Bạn hiểu sai ý đề rồi. $m$ nhỏ nhất để luôn có hai phần tử $a,b$ và $a \vdots b$ chứ không phải là $m$ nhỏ nhất để có thể có 2 phần tử $a,b$ mà $a \vdots b$. Mình nghĩ đáp án là $m=t+1$ với t là số các số nguyên tố trong $[1;n]$. Mà việc tìm $t$ thì minh chưa nghĩ ra. Nếu cho $n$ cụ thể thì sẽ dễ hơn nhiều.
Bài viết đã được chỉnh sửa nội dung bởi quocbaolqd11: 31-12-2013 - 11:44
Bạn hiểu sai ý đề rồi. $m$ nhỏ nhất để luôn có hai phần tử $a,b$ và $a \vdots b$ chứ không phải là $m$ nhỏ nhất để có thể có 2 phần tử $a,b$ mà $a \vdots b$. Mình nghĩ đáp án là $m=t+1$ với t là số các số nguyên tố trong $[1;n]$. Mà việc tìm $t$ thì minh chưa nghĩ ra. Nếu cho $n$ cụ thể thì sẽ dễ hơn nhiều.
Nếu vậy, đề bài cần sửa lại là :
" Cho tập hợp $X=\left \{ 1,2,3,...,n \right \}\subset \mathbb{N}$.Tìm số nguyên dương $m$ nhỏ nhất sao cho trong mọi tập con $A$ có $m$ phần tử của $X$ đều có ít nhất $2$ phần tử nào đó mà phần tử lớn hơn chia hết cho phần tử nhỏ hơn "
Giải :
Xét tập $A\subset X$.Giả sử trong tập $A$ tồn tại $2$ phần tử $a$ và $b$ thoả mãn $a\vdots b$ hay $a=k.b$ ($k\in \mathbb{N}^+$)
Vì $a\neq b$ (dĩ nhiên) nên giá trị nhỏ nhất của $k$ là $2$.Xét $2$ trường hợp :
$a)$ $n$ chẵn ($n=2p$, $p\in \mathbb{N}^+$)
Khi đó phần tử lớn nhất thuộc $X$ chia hết cho $2$ là $2p$
Ước lớn nhất của phần tử đó (không kể chính nó) là $p$.
Rõ ràng tập $Y=\left \{ p+1,p+2,...,2p \right \}$ (gồm có $p$ phần tử) không thể có $2$ phần tử $a$ và $b$ nào thoả mãn $a\vdots b$
Nhưng nếu từ tập $Y$ đó ta thêm vào $q$ phần tử lấy từ tập $T=\left \{ 1,2,3,...,p \right \}$ ($q\leqslant p$) rồi bỏ đi $q-1$ phần tử tuỳ ý thì được tập $V$ (gồm có $p+1$ phần tử).Dễ thấy rằng mỗi phần tử thêm vào đều có bội của nó thuộc $Y$ nên sau khi bỏ đi $q-1$ phần tử tuỳ ý thì vẫn còn ít nhất $2$ phần tử $a$ và $b$ thoả mãn $a\vdots b$
$\Rightarrow$ số nguyên dương $m$ nhỏ nhất cần tìm (khi $n=2p$) là $m=\left | V \right |=p+1=\frac{n}{2}+1=\frac{n+2}{2}$
$b)$ $n$ lẻ ($n=2p+1$, $p\in \mathbb{N}^+$)
Khi đó phần tử lớn nhất thuộc $X$ chia hết cho $2$ là $2p$
Ước lớn nhất của phần tử đó (không kể chính nó) là $p$.
Rõ ràng tập $S=\left \{ p+1,p+2,...,2p+1 \right \}$ (gồm $p+1$ phần tử) không thể có $2$ phần tử $a$ và $b$ nào thoả mãn $a\vdots b$
Nhưng nếu tử tập $S$ ta thêm vào $q$ phần tử lấy tử tập $T=\left \{ 1,2,3,...,p \right \}$ ($q\leqslant p$) rồi bỏ đi $q-1$ phần tử tuỳ ý thì được tập $U$ (gồm $p+2$ phần tử).Dễ thấy rằng mỗi phần tử thêm vào đều có bội của nó thuộc $S$ nên sau khi bỏ đi $q-1$ phần tử tuỳ ý thì vẫn còn ít nhất $2$ phần tử $a$ và $b$ thoả mãn $a\vdots b$
$\Rightarrow$ số nguyên dương $m$ nhỏ nhất cần tìm (khi $n=2p+1$) là $m=\left | U \right |=p+2=\frac{n-1}{2}+2=\frac{n+3}{2}$
Trả lời :
$a)$ Nếu $n$ chẵn thì $m=\frac{n+2}{2}$
$b)$ Nếu $n$ lẻ thì $m=\frac{n+3}{2}$
Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 01-01-2014 - 14:28
...
Ðê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 ...
à, mình hiểu là nếu như với một số $m$ mà $|A|=m$ và ta luôn xây dựng được 1 tập có $m$ phần tử và không có phần tử nào chia hết cho nhau thì số $m$ không thỏa đề và nếu ta tìm được $m$ lớn nhất không thỏa đề thì $m+1$ là số nhỏ nhất thỏa đề. Cơ mà, cái lúc nãy mình nói ở post trên có vẻ sai rồi. Theo mình nghĩ thì ta vẫn có thể xây dựng được tập hợp có $[\frac{n}{2}]$ phần tử và không phần tử nào chia hết cho nhau. Mình nêu cách xác định với $n=2k$ (lấy ý tưởng hầu hết từ bài TST 2007 p.5).
xét tập $A=\{a_i=2^{f(i)}(2i-1)| [\frac{n}{3}]+1 \le 3^{f(i)}(2i-1) \le n \}$ (nếu $n$ không chiâ hét cho 3 hoặc $A=\{a_i=2^{f(i)}(2i-1)| \frac{n}{3} \le 3^{f(i)}(2i-1) \le n \}$ nếu $n$ chia hết cho 3.
Dễ thấy tập này có $k$ phần tử thuộc $\{1,2,3,...2k \}$.
giả sử có $a_{j} \vdots a_i$ thì khi dó $2^{f(i)}(2i-1) \le 2^{f(j)}(2j-1)$, tức là $f(j) \ge f(i)$ và $2j-1 \vdots 2i-1$.
vì $2i-1; 2j-1$ lẻ nên $2j-1 \ge 3(2i-1)$.
Từ đó, có: $3^{f(i)+1}.(2i-1) \ge n >3^{f(j)}(2j-1) \ge 3^{f(i)+1}.(2i-1)$ hay $f(i) > f(j)$ (vô lí).
vậy với $m=k$ thì luôn xây dựng được tập thỏa ycđ. dễ chứng minh được rằng trong $k+1$ số trong $[1;2k]$ thì luôn tồn tại 2
số chia hết cho nhau nên $m_{min}=k+1$. TH $n$ lẻ thì để từ từ nghiên cứu vì cuối năm rồi .
Xin đề xuất thêm một cách giải khác.
Đặt $n=2p$ (nếu $n$ chẵn) hoặc $n=2p+1$ (nếu $n$ lẻ)
Ta chia tập $X$ thành $p$ tập con (nếu $n$ chẵn) hoặc $p+1$ tập con (nếu $n$ lẻ) theo cách sau đây :
- Xếp các phần tử $p+1$ vào tập $Y_{1}$; $p+2$ vào tập $Y_{2}$; ...; $2p$ vào tập $Y_{p}$ (và $2p+1$ vào tập $Y_{p+1}$ nếu $n$ lẻ)
- Lần lượt xếp các phần tử $p;p-1;p-2;...;1$ vào các tập trên theo nguyên tắc " phần tử $k$ phải được xếp cùng tập với phần tử $2k$ " ($1\leqslant k\leqslant p$)
Nhận xét rằng phải có ít nhất $1$ tập $Y_{j}$ mà trong tập đó có ít nhất $2$ phần tử thuộc $A$ thì tập $A$ mới thỏa mãn điều kiện " $\exists a,b\in A$ sao cho $a\vdots b$ "
Vậy để đảm bảo trong $A$ luôn luôn có $2$ phần tử $a,b$ sao cho $a\vdots b$ thì số phần tử của $A$ nhỏ nhất phải là $m=j_{max}+1$
$a)$ Nếu $n$ chẵn : $j_{max}=p\Rightarrow m=p+1=\frac{n}{2}+1=\frac{n+2}{2}$
$b)$ Nếu $n$ lẻ : $j_{max}=p+1\Rightarrow m=p+2=\frac{n-1}{2}+2=\frac{n+3}{2}$
Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 01-01-2014 - 16:45
...
Ðê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 ...
0 thành viên, 0 khách, 0 thành viên ẩn danh