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

[tientthegioi]

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$. 

[chanhquocnghiem]

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$

[quocbaolqd11]

Đề 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

[chanhquocnghiem]

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

[quocbaolqd11]

à, 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 .

[chanhquocnghiem]

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