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

Topic về tổ hợp, các bài toán về tổ hợp


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

#41 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 03-07-2013 - 13:32

Bài 18: Cho $n$ điểm phân biệt trên đoạn thẳng có độ dài 1 đơn vị. Với mỗi điểm, ta tính tích khoảng cách từ điểm đó đến $n-1$ điểm còn lại. Gọi $S(n)$ là tổng nghịch đảo của các tích ấy. Chứng minh rằng: $S(n) \ge 2^{n-3}$


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 03-07-2013 - 15:55


#42 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 03-07-2013 - 14:02



Bài 14:(Cực trị tổ hợp, China TST 2012) Trong một hình vuông được tạo bởi \[2012 \times 2012\] ô vuông có chứa những con bọ, trong một ô vuông có nhiều nhất 1 con bọ. Vào một thời điểm nào đó, những con bọ này bay lên rồi lại đậu xuống lại vào các ô vuông, mỗi ô vuông cũng có nhiều nhất một con bọ. Đối với mỗi con bọ, có thể xem đoạn thẳng có hướng nối tâm của ô vuông lúc đầu và tâm của lúc sau mà nó đậu lên tạo thành một vector. Với một số lượng bọ ban đầu, xét tất cả những trường hợp  có thể xảy ra với các vị trí đầu tiên và cuối cùng của những con bọ, hãy tìm độ dài lớn nhất của tổng các vector.

Hình như mình đưa bài này hơi bị quá sức  :icon6:

File đính kèm dưới đây là lời giải của bài 14.

Ngoài ra còn bài 7,16(2 bài),18 chưa có lời giải, mong các anh(bạn) cố gắng xử lý  :icon6:

File gửi kèm



#43 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 07-07-2013 - 20:19

Bài 7: (Đề đề nghị 30/4 -2012) Trong một kì thi hoa hậu, mỗi thành viên của ban giám khảo được quyền đề xuất $10$ người đẹp vào vòng chung kết. Một nhóm người đẹp được gọi là nhóm ưng ý đối với giám khảo A nếu trong nhóm đó có ít nhất một người đẹp mà A đề xuất. Biết rằng với 6 giám khảo bất kỳ luôn tồn tại một nhóm gồm 2 người đẹp là nhóm ưng ý đối với mỗi giám khảo trong 6 giám khảo đó. Chứng minh rằng tồn tại một nhóm gồm 10 người đẹp là nhóm ưng ý đối với mỗi thành viên của ban giám khảo.

Hình như bài này đề sai rồi, đề đúng ở đây:http://diendantoanho...hợp/#entry20366

Trong 1 cuộc thi hoa hậu.Mỗi giám khảo được chọn ra 10 ứng cử viên. Một nhóm được gọi là ưng ý với 1 GK nếu có người ông ta đề cử.Biết cứ 6 người (Hoa hậu) bất kì luôn chọn Được 2 GK ưng ý!
CMR: Có thể chọn đựoc nhóm 10 hoa hau ưng ý với tất cả GK



#44 Nxb

Nxb

    Thiếu úy

  • Thành viên
  • 539 Bài viết
  • Giới tính:Nam

Đã gửi 12-07-2013 - 10:04

Bài 19 (Dirichlet). Cho một bảng 4.4, trong mỗi ô vuông có 2 con ngựa và cỏ. Biết 2 con ngựa trong mỗi ô vuông không ăn cỏ trong ô vuông đó mà ở các ô vuông chung cạnh và chúng không ăn cỏ trong cùng một ô vuông. Tìm số lớn nhất các ô vuông không có cỏ bị ăn

 



#45 gogo123

gogo123

    Trung sĩ

  • Thành viên
  • 102 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Phan Bội Châu-Nghệ An

Đã gửi 13-07-2013 - 01:59

Bài 18.Sử dụng nội suyLagrange và đa thức Chebysev.

$T_{n-1}(x)=\sum_{k=0}^{n-1} T_{n-1}(x_k)\prod_{i\neq k}\frac{x-x_i}{x_k-x_i}$

Xét hệ số cao nhất ta có :

 $2^{n-2}=\sum_{k=0}^{n-1} \frac{T_{n-1}(x_k)}{\prod_{i\neq k}(x_k-x_i)}$

Suy ra 

$2^{n-2}\leq \left |\sum_{k=0}^{n-1} \frac{T_{n-1}(x_k)}{\prod_{i\neq k}(x_k-x_i)}  \right | \leq \sum_{k=0}^{n-1} \frac{1}{\left |\prod_{i\neq k}(x_k-x_i)  \right |}=S_n$


LKN-LLT


#46 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 23-07-2013 - 15:00

Làm nóng topic cái đã

Bài 20:( đếm bằng truy hồi) Với $n\geq 2$, tính số hoán vị của $a_{1},a_{2},...,a_{n}$ của các số $\left \{ 1,2,...,n \right \}$ thoả mãn $a_{i+1}-a_{i}\leq 1$$\forall i=\overline{1,n-1}$



#47 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 02-08-2013 - 09:25

Làm nóng topic cái đã

Bài 20:( đếm bằng truy hồi) Với $n\geq 2$, tính số hoán vị của $a_{1},a_{2},...,a_{n}$ của các số $\left \{ 1,2,...,n \right \}$ thoả mãn $a_{i+1}-a_{i}\leq 1$$\forall i=\overline{1,n-1}$

đặt $S(n)$ là số hoán vị thỏa mãn yêu cầu đề. Giả sử $n$ nằm ở $a_k$$\forall k=\overline{1,n}$

 

. Dễ thấy với mỗi hoán vị thỏa yêu cầu đề, ta chỉ có 2 cách thêm $n+1$ vào vị trí $a_1$ hoặc vào vị trí $a_{k+1}$ để tạo thành 1 hoán vị mới thỏa yêu cầu đề bài nên từ đây ta có công thức: $S(n+1)=2S(n)$ và $S(1)=1$ nên $S(n)=2^{n-1}$.

 

Bài 19 (Dirichlet). Cho một bảng 4.4, trong mỗi ô vuông có 2 con ngựa và cỏ. Biết 2 con ngựa trong mỗi ô vuông không ăn cỏ trong ô vuông đó mà ở các ô vuông chung cạnh và chúng không ăn cỏ trong cùng một ô vuông. Tìm số lớn nhất các ô vuông không có cỏ bị ăn

bài này mình nghĩ chỉ là suy luận thông thương thôi. 
TH1: nếu con ngựa đứng ở các ô không phải là cạnh của bảng vuông $4 \times 4$, số ô vuông có cỏ bị ăn là 4 và sẽ tồn tại 1 ô nằm trong góc mà 2 ô có cạnh chung với nó đã bị ăn, đặt ô vuông này là ô vuông $k$. số lớn nhất các ô vuông không có cỏ bị ăn tương đương với số ô vuông bé nhất mà  con ngựa có thể ăn. Dễ thấy nếu đặt con ngựa thứ 2 ở các ô khác thì nó có thể ăn được cỏ trong 1 hoặc 2 ô vuông, nhưng nếu đặt vào ô $k$ thì nó không ăn được cỏ ở bất kì ô vuông nào nên 0 là số ô vuông bé nhất mà con ngựa có thể ăn. Vậy nên số ô vuông lớn nhất không bị ăn trong TH này là 12.
TH2: nếu con ngựa đứng ở ô cạnh mà không đứng ở ô góc thì dễ thấy con ngựa này ăn được 3 ô vuông có cỏ. Gọi $k$ là ô vuông góc có cạnh chưng là ô vuông đã bị ăn cỏ, dễ thấy ở ô vuông này, con ngựa 2 chỉ có thể ăn 1 ô và đây cũng là số ô bé nhất mà con ngựa có thể ăn được nên số ô vuông lớn nhất mà không có cỏ bị ăn trong TH này cũng là 12.
TH3: con ngựa 1 nằm ở ô góc. bằng cách lập luận như ở 2 TH trên thì ô vuông $k$ kể với 2 ô vuông mà cỏ bị ăn sẽ là ô vuông mà nếu ngựa 2 đặt trong đó, số ô vuông mà nó có thể ăn cỏ được đạt ít nhất là 2 ô. Vậy trong TH này số ô vuông lớn nhất không bị ăn là 12.
vậy max=12.
Bài 21: (Đồ thi 1 chiều, giải tích tổ hợp)
Có một ngưới đi từ gốc tọa độ O đến điểm A có tọa độ n trên trục tọa độ.Người này bị say rượu nên chỉ bước mỗi lần 1 bước và có thể bước tới hoặc quay lui lại. Ban đầu tại O, ngưòi  đó vẫn có thể quay lui được, nhưng nếu đến A thì không bước tiến hay lùi được nữa.
Hỏi người đó có bao nhiêu cách bước nếu số bước đi thực hiện là $m$?



#48 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 02-08-2013 - 10:15

Post tiếp 2 bài nữa làm ... điểm tâm  :wacko: :

Bài 16:(Bulgaria 1996) HÌnh chữ nhật $m \times n ( m,n \in N, m,n>1)$ được chia thành $mn$ hình vuông đơn vị. Có bao nhiêu cách xoá 2 hình vuông sao cho phần còn lại có thể lát kín bởi các domino?

đặt $S(m,n)$ là số cách tô thỏa yêu cầu. Nếu $m,n$ lẻ thì $S(n)=0$. Tô xen kẽ các ô vuông bằng 2 màu đen trắng. Ta sẽ chứng minh bằng cách bỏ đi 2 ô khác màu nhau thì phân còn lại sẽ được phủ kín bới các ô vuông $1 \times 2$.
dễ thấy nó đúng với cách bảng $2 \times 2$, $2 \times 3$, $2 \times 4$, ....
Giả sử nó đúng với $m.n$
ta chứng minh nó đúng với $m.(n+1)$.(m chẵn )
chia bảng  $m.(n+1)$ thành 2 bảng $A$ và $B$ sao cho $A$ là bảng gồm 2 hàng  đầu tiên, và $B$ là bảng còn lại thỏa $m$ là độ dài chiều ngang.
nếu 2 ô vuông khác màu nhau bị bỏ ở trong cùng 1 bảng $A$ hoặc $B$ thì dễ thấy theo giả thiết quy nạp, ta có đpcm.
nếu 1  ô nằm trong $A$ và 1 ô nằm trong $B$. Khi đấy, ta phủ 1 hcn $1 \times 2$ lên 2 ô vuông nằm cạnh nhau sao cho 1 ô thuộc $A$ và 1 ô thuộc $B$ sao cho ô nằm trong $A$ phải khác màu ô đã bị bỏ trong $A$ trước đó và tương bị với ô trong $B$. Theo giả thiết quy nạp thì phần còn lại của mỗi bảng đều được phủ kín.
Vậy ta có đpcm.
từ đó dễ thấy số cách chọn là $S(m,n)=\frac{m^{2}.n^{2}}{4}$.



#49 Nxb

Nxb

    Thiếu úy

  • Thành viên
  • 539 Bài viết
  • Giới tính:Nam

Đã gửi 02-08-2013 - 20:13

bài này mình nghĩ chỉ là suy luận thông thương thôi. 

TH1: nếu con ngựa đứng ở các ô không phải là cạnh của bảng vuông $4 \times 4$, số ô vuông có cỏ bị ăn là 4 và sẽ tồn tại 1 ô nằm trong góc mà 2 ô có cạnh chung với nó đã bị ăn, đặt ô vuông này là ô vuông $k$. số lớn nhất các ô vuông không có cỏ bị ăn tương đương với số ô vuông bé nhất mà  con ngựa có thể ăn. Dễ thấy nếu đặt con ngựa thứ 2 ở các ô khác thì nó có thể ăn được cỏ trong 1 hoặc 2 ô vuông, nhưng nếu đặt vào ô $k$ thì nó không ăn được cỏ ở bất kì ô vuông nào nên 0 là số ô vuông bé nhất mà con ngựa có thể ăn. Vậy nên số ô vuông lớn nhất không bị ăn trong TH này là 12.
TH2: nếu con ngựa đứng ở ô cạnh mà không đứng ở ô góc thì dễ thấy con ngựa này ăn được 3 ô vuông có cỏ. Gọi $k$ là ô vuông góc có cạnh chưng là ô vuông đã bị ăn cỏ, dễ thấy ở ô vuông này, con ngựa 2 chỉ có thể ăn 1 ô và đây cũng là số ô bé nhất mà con ngựa có thể ăn được nên số ô vuông lớn nhất mà không có cỏ bị ăn trong TH này cũng là 12.
TH3: con ngựa 1 nằm ở ô góc. bằng cách lập luận như ở 2 TH trên thì ô vuông $k$ kể với 2 ô vuông mà cỏ bị ăn sẽ là ô vuông mà nếu ngựa 2 đặt trong đó, số ô vuông mà nó có thể ăn cỏ được đạt ít nhất là 2 ô. Vậy trong TH này số ô vuông lớn nhất không bị ăn là 12.
vậy max=12.

Chẳng hạn ta có một cái bảng thế này:

1  2 3  4

5  6 7  8

1' 2' 3' 4'

5' 6' 7' 8'

Ta thấy có 8 ô 2,3,8,4',6',7',5,1' bị ăn. Vậy thì không thể xảy ra trường hợp 12 ô không bị ăn như bạn nói được. 


  • LNH yêu thích

#50 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 02-08-2013 - 21:00

Chẳng hạn ta có một cái bảng thế này:

1  2 3  4

5  6 7  8

1' 2' 3' 4'

5' 6' 7' 8'

Ta thấy có 8 ô 2,3,8,4',6',7',5,1' bị ăn. Vậy thì không thể xảy ra trường hợp 12 ô không bị ăn như bạn nói được. 

mình nhầm giả thiết, xin lỗi bạn.


Bài viết đã được chỉnh sửa nội dung bởi quocbaolqd11: 02-08-2013 - 21:36


#51 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 02-08-2013 - 21:02

Chẳng hạn ta có một cái bảng thế này:

1  2 3  4

5  6 7  8

1' 2' 3' 4'

5' 6' 7' 8'

Ta thấy có 8 ô 2,3,8,4',6',7',5,1' bị ăn. Vậy thì không thể xảy ra trường hợp 12 ô không bị ăn như bạn nói được. 

Theo em nghĩ số ô vuông lớn nhất không bị ăn là 4 chứ :icon6:



#52 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 02-08-2013 - 21:13

Theo em nghĩ số ô vuông lớn nhất không bị ăn là 4 chứ :icon6:

up lời giải đi em. Cơ bản là bài này cái giả thiết có vấn đề, không hiểu tại sao mỗi ô đều có ngựa mà lại còn bắt tìm số ô không bị ăn nên anh sửa lại thành "bảng $4 \times 4$ có 2 con ngựa".


  • LNH yêu thích

#53 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 02-08-2013 - 21:15

Bài 19 (Dirichlet). Cho một bảng 4.4, trong mỗi ô vuông có 2 con ngựa và cỏ. Biết 2 con ngựa trong mỗi ô vuông không ăn cỏ trong ô vuông đó mà ở các ô vuông chung cạnh và chúng không ăn cỏ trong cùng một ô vuông. Tìm số lớn nhất các ô vuông không có cỏ bị ăn

Em sẽ sử dụng bảng của anh Nxb ở bài trên

Xét các con ngựa ở ô vuông $1,4,5^{'},8^{'}$

Dễ dàng nhận ra rằng cỏ ở các ô vuông $2,3,5,8,1^{'},4^{'},6^{'},7^{'}$ đều bị ăn

Dễ dàng CM các con ngựa ở ô $6,7,2^{'},3^{'}$ đều có thể ăn cỏ ở các ô trên

Xét các con ngựa ở ô $2,3,5,8,1^{'},4^{'},6^{'},7^{'}$

Mỗi ô sẽ có 1 con ngựa ăn cỏ ở 1 trong các ô trên

Xét các con ngựa còn lại:

Nhận xét: con ngựa ở ô $2,5$ ăn cỏ chung một ô (tương tự với các ô $3$ và $8$, $4^{'}$ và $7^{'}$, $1^{'}$ và $6^{'}$)

Dễ dàng thấy rằng cỏ của 4 trong 8 ô còn lại phải bị ăn

Vậy số ô không bị ngựa ăn cỏ lớn nhất là 4

Xong  :biggrin:

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Hình như bài này thầy Vũ Đình Hoà có cho trên toán tuổi thơ rồi


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 02-08-2013 - 21:19


#54 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 02-08-2013 - 21:32

Em sẽ sử dụng bảng của anh Nxb ở bài trên

Xét các con ngựa ở ô vuông $1,4,5^{'},8^{'}$

Dễ dàng nhận ra rằng cỏ ở các ô vuông $2,3,5,8,1^{'},4^{'},6^{'},7^{'}$ đều bị ăn

Dễ dàng CM các con ngựa ở ô $6,7,2^{'},3^{'}$ đều có thể ăn cỏ ở các ô trên

Xét các con ngựa ở ô $2,3,5,8,1^{'},4^{'},6^{'},7^{'}$

Mỗi ô sẽ có 1 con ngựa ăn cỏ ở 1 trong các ô trên

Xét các con ngựa còn lại:

Nhận xét: con ngựa ở ô $2,5$ ăn cỏ chung một ô (tương tự với các ô $3$ và $8$, $4^{'}$ và $7^{'}$, $1^{'}$ và $6^{'}$)

Dễ dàng thấy rằng cỏ của 4 trong 8 ô còn lại phải bị ăn

Vậy số ô không bị ngựa ăn cỏ lớn nhất là 4

Xong  :biggrin:

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Hình như bài này thầy Vũ Đình Hoà có cho trên toán tuổi thơ rồi

có vấn đề chút. Giả thiết yêu cầu là 2 con ngựa không ăn chung 1 ô nên nếu 1 con ngựa ở ô 5 đã ăn cỏ ở ô 1 thì con ngựa còn lại ở ô 5 phải ăn cỏ ở ô 6 chứ ? Khi đấy thì chả có ô nào còn cỏ cả.



#55 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 02-08-2013 - 21:33

Con ngựa ô 5 không ăn cỏ ô 1 thì ăn ở ô $1^{'}$ cũng được mà anh



#56 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 02-08-2013 - 21:46

Bài 22:(Lý thuyết đồ thị, cực trị tổ hợp) Cho một nhóm 9 người. Hai người có thể thích nhau, ghét nhau hoặc không quen biết. Hai người được gọi là "có quan hệ với nhau" nếu hoặc thích nhau hoặc quen nhau. Gọi số cặp 2 người có quan hệ với nhau là $n$. Tìm số $n$ nhỏ nhất sao cho trong bất kì trường hợp nào cũng tồn tại 3 người đôi một thích nhau hoặc ghét nhau.



#57 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 02-08-2013 - 22:06

à, đọc vội nên nhầm giả thiết, xin lỗi anh em. Cơ mà bài này cũng chẳng cần Đi-rích-lê, làm suy luận bình thường cũng được. 

 

Bài 16:(song ánh) Một tập hữu hạn các số nguyên dương được gọi là “béo” nếu mỗi phần tử của nó lớn hơn hoặc bằng số phần tử của nó (Tập rỗng “béo”) . Gọi $a_n$ là số tập con “béo” của $X= \left\{1,2,3,4,…..,n\right\}$ mà không chứa 2 số nguyên liên tiếp nào, $b_n$ là số tập con của X mà 2 phần tử bất kì hơn kém nhau ít nhất 3 đơn vị.

Chứng minh rằng $a_n=b_n$

Quất luôn cho nóng.
Gọi $A$ là các tập béo có k phần tử mà không chứa 2 số nguyên liên tiếp nào, B là các tập con của $X$ có tính chất 2 phần tử bát kì hơn kém nhau ít nhất 3 đơn vị. Từ giả thiết ta thấy : với $A' = {a_1, a_2, ..., a_k} \in A$ thì $k \le a_1 <a_2<...<a_k \le n$. Giờ ta thiết lập 1 ánh xạ đi từ $f: A \rightarrow B$. Đặt $a_i=b_{i}+k-i$ $\forall i=\overline{1,k}$, . ta có:
$a_{i+1}-a{i} \ge 2$ $\forall i=\overline{1,k-1}$ $\Rightarrow$  $b_{i+1}-b_{i} \ge 3, b_1 \ge 1, b_{k} \le n $. Từ đấy, ta thấy $B'=\left \{b_1,b_2,...,b_{k} \right. \left. \right \}$ $\in B$. Đặt $f(A)=B'=\left\{b_1,b_2,...\right. \left. \right \}=\left\{a_{1}+1-k,a_{2}+2-k,...a_{k}\right. \left. \right \}$. Vậy $f$ là ánh xạ từ $A$ vào $B$. Dễ chứng minh $f$ song ánh nên $|A|=|B|$ hay $a_{n}=b_{n}$. 


Bài viết đã được chỉnh sửa nội dung bởi quocbaolqd11: 02-08-2013 - 22:12


#58 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 02-08-2013 - 23:03

Bài 22:(Lý thuyết đồ thị, cực trị tổ hợp) Cho một nhóm 9 người. Hai người có thể thích nhau, ghét nhau hoặc không quen biết. Hai người được gọi là "có quan hệ với nhau" nếu hoặc thích nhau hoặc quen nhau. Gọi số cặp 2 người có quan hệ với nhau là $n$. Tìm số $n$ nhỏ nhất sao cho trong bất kì trường hợp nào cũng tồn tại 3 người đôi một thích nhau hoặc ghét nhau.

bài này có thể phát biểu thành: Cho 9 điểm trong không gian, mỗi 2 điểm được nối bởi 1 đoạn thẳng xanh hoặc đỏ hoặc không có màu. Gọi số đường thẳng được tô màu là $n$. Tìm n nhỏ nhất sao cho bất kì trường hợp nào cũng tồn tại 1 tam giác có 3 cạnh được tô cùng màu.
đây là bài IMO 1992, $n=33$. http://www.artofprob...75235fc#p366404


Bài viết đã được chỉnh sửa nội dung bởi quocbaolqd11: 02-08-2013 - 23:07


#59 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 03-08-2013 - 14:37

Bài 23:(Thái Lan 2007) 229 học sinh nam và 271 học sinh nữ được chia thành 10 nhóm, mỗi nhóm 50 học sinh được đánh số từ 1 đến 50. Người ta muốn chọn ra một nhóm 4 học sinh, trong đó số học sinh nữ được chọn là lẻ và thoả mãn điều kiện sau đây: 4 người này được chọn từ 2 nhóm và có 2 cặp học sinh có cùng số thứ tự. Chứng minh rằng số cách chọn các nhóm như vậy là một số lẻ.


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 03-08-2013 - 14:37


#60 AnnieSally

AnnieSally

    Thiếu úy

  • Thành viên
  • 647 Bài viết
  • Giới tính:Nữ

Đã gửi 05-08-2013 - 08:30

Bài 24: (Moldova 2007) Chứng minh rằng hình vuông cạnh 14 có thể phủ được bởi 21 hình vuông: 6 hình vuông cạnh 1, 5 hình vuông cạnh 2, …, 1 hình vuông cạnh 6.

Bài 25: (UK 2007) Ở nước Hexagonia, 6 thành phố được kết nối bởi hệ thống đường sắt sao cho giữa hai thành phố bất kỳ có đường sắt nối trực tiếp. Vào ngày chủ nhật, một số đoạn đường đóng cửa để sửa chữa. Luật đường sắt quy định là mọi thành phố phải có thể đến được từ một thành phố khác (không nhất thiết trực tiếp) trong mọi thời điểm. Có bao nhiêu cách đóng một vài đoạn đường để yêu cầu này được thoả mãn?






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

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