Đến nội dung

Hình ảnh

Một số bài toán tổ hợp chuyên toán 10

- - - - -

  • Please log in to reply
Chưa có bài trả lời

#1
dunglamtym

dunglamtym

    Trung sĩ

  • Thành viên
  • 122 Bài viết

*Hàm đếm :

A1;A2;...;An là tập con của tập X hữu hạn. Với mỗi x thuộc X ta kí hiệu d(x) là số tập Ai mà x thuộc Ai. Ta có các công thức sau đây:

1. $\sum d(x)=\sum_{i=1}^{n}|A_i|$

2. $\sum \frac{d(x).[d(x)-1]}{2} = \sum_{1\leq i< j\leq n}^{ }|A_i\cap A_j|$

3. $\sum [d(x)]^{2} = \sum_{i=1}^{n}\sum_{j=1}^{n}|A_i\cap A_j|$

 

Bài tập:

 

1. Cho n nguyên dương lớn hơn bằng 2. X là một tập có n phần tử. Giả sử $A_1;A_2;...;A_{101}\subset X$ thỏa mãn hợp của 50 tập bất kì có nhiều hơn $\frac{50}{51}n$ phần tử. CMR: trong 101 tập nói trên có 3 tập đôi một có giao khác rỗng.

 

2. Tìm số nguyên dương n sao cho ta có thể tô màu các cạnh và đường chéo của một đa giác lồi n đỉnh bởi n màu cho trước thỏa mãn các điều kiện sau: 

+ Mỗi cạnh, mỗi đường chéo được tô bởi đúng 1 màu.

+ Với 3 màu bất kì thì có ít nhất một tam giác có đỉnh là đỉnh đa giác mà 3 cạnh của nó tương ứng được tô bởi 3 màu đã cho.

 

3. Cho n nguyên dương và A1;A2;...;Ak là các tập con của tập S={1;2;...;n}, mỗi tập có ít nhất $\frac{n}{2}$ phần tử. 2 tập Ai;Aj khác nhau (i khác j) thì $|A_i\cap A_j|\leq \frac{n}{4}$. $CMR: |A_1\cup A_2\cup ...\cup A_k|\geq \frac{nk}{k+1}$

 

4. Cho X={1;2;...;n} $(n\geq 2)$; $A_1;A_2;...;A_n\subset X;|A_i|\geq 2\forall i=1,2,...,n$. Biết nếu A là một tập con 2 phần tử của X thì có duy nhất một chỉ số i để $A\subset A_i. CMR: A_i\cap A_j\neq \varnothing \forall i\neq j$

 

*Bất biến : Lát phủ bảng ô vuông

1. Cho bảng 8x8. CMR không thể lát bảng này bởi 1 hình vuông 2x2 và 15 hình T ( hình vẽ bên dưới)

 

2. Tìm n nguyên dương để bảng ô vuông kích thước (2n+1)x(2n+1) bỏ đi ô vuông góc trên cùng bên trái để lát được bởi các hình chữ nhật 1x2 trong đó có một nửa ngang, một nửa dọc.

 

3. Cho bảng mxn. Hỏi cần bỏ đi ít nhất bao nhiêu ô của bảng để phần còn lại không có 3 ô nào tạo thành hình L ( hình vẽ bên dưới)

 

4. Cho n nguyên dương lẻ và bảng nxn được tô màu như bàn cơ. Biết 4 ô góc là ô đen. Hỏi với n bằng bao nhiêu thì hình gồm các ô đen của bảng có thể được phủ kín bởi các hình sao cho không có 2 hình L ( hình vẽ bên dưới) nào chồng lên nhau. Khi đó cần ít nhất bao nhiêu hình này?

 

5. Tìm m,n để bảng mxn được lát kín bởi các hình L ( hình vẽ bên dưới)

hình tổ hợp.png

 






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

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