Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Tìm số nguyên dương $m$ nhỏ nhất sao cho $|A| =m$.


  • Please log in to reply
Chủ đề này có 5 trả lời

#1 tientthegioi

tientthegioi

    Trung sĩ

  • Thành viên
  • 189 Bài viết
  • Giới tính:Nam
  • Đến từ:pleiku_GiaLai
  • Sở thích:chơi thôi +ngủ ( và làm những gì mình thích )

Đã gửi 11-10-2005 - 15:36

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


Tỏ ra mình hơn người chưa phải là hay. Con mèo hạnh phúc thì liếm mép của mình.

Hình đã gửi

#2 chanhquocnghiem

chanhquocnghiem

    Đại úy

  • Thành viên
  • 1901 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 31-12-2013 - 08:09

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

 

http://www.wolframal...-15)(x^2-8x+12)


#3 quocbaolqd11

quocbaolqd11

    Hạ sĩ

  • Thành viên
  • 73 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn Khánh Hòa.
  • Sở thích:tổ hợp và số học

Đã gửi 31-12-2013 - 11:41



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


#4 chanhquocnghiem

chanhquocnghiem

    Đại úy

  • Thành viên
  • 1901 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 31-12-2013 - 18:05



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

 

http://www.wolframal...-15)(x^2-8x+12)


#5 quocbaolqd11

quocbaolqd11

    Hạ sĩ

  • Thành viên
  • 73 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn Khánh Hòa.
  • Sở thích:tổ hợp và số học

Đã gửi 31-12-2013 - 20:30

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



#6 chanhquocnghiem

chanhquocnghiem

    Đại úy

  • Thành viên
  • 1901 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 01-01-2014 - 16:41

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

 

http://www.wolframal...-15)(x^2-8x+12)





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh