10/11/2013


Bài 1. Chứng minh rằng với mỗi tập hữu hạn X ta có |P(X)|=2^{|X|}.

Bài 2. Cho m,n là các số nguyên lớn hơn 1S là một tập có n phần tử. Giả sử có các tập con A_1,A_2,\cdots,A_m của S thoả mãn: Với mỗi hai phần tử x,y\in S, có tập A_i sao cho x\in A_i,y\not\in A_i hoặc x\not\in A_i,y\in A_i. Chứng minh rằng n\leq 2^m.

Bài 3. Cho m,n là các số nguyên dương và một bảng ô vuông cỡ m\times n. Giả sử A,B là hai trong các đỉnh của các ô vuông nhỏ của bảng, một đường đi từ A đến B là một dãy điểm D_0D_1\cdots D_k sao cho D_iD_{i+1} là cạnh của một ô vuông con(có thể là cạnh chung của hai ô vuông con) và D_0=A,D_k=B; khi đó k gọi là độ dài của đường đi. Tính số các đường đi ngắn nhất nối đỉnh dưới bên trái và đỉnh trên bên phải của bảng ô vuông.

Bài 4. Cho n là một số nguyên dương và X=\{1,2,\cdots,n\}. Chứng minh rằng số r-tổ hợp của X không chứa hai số nguyên liên tiếp là C_{n-r+1}^r. Trong đó r là số nguyên thoả mãn 0\leq r\leq n-r+1.

Bài 5. Cho n là một số nguyên dương. Một hoán vị x_1x_2\cdots x_{2n} của tập \{1,2,\cdots,2n\} được gọi là có tính chất P nếu |x_i-x_{i+1}|=n với ít nhất một i\in\{1,2,\cdots,2n-1\}. Chứng minh rằng với mỗi số nguyên dương n, số các hoán vị có tính chất P nhiều hơn số hoán vị không có tính chất đó.

Bài 6. Cho m,n là các số nguyên dương. Chứng minh rằng có

a) C_{n-1}^{m-1} bộ (x_1,x_2,\cdots,x_m) các số nguyên dương thoả mãn x_1+x_2+\cdots+x_m=n;

b) C_{n+m-1}^{m-1} bộ (x_1,x_2,\cdots,x_m) các số nguyên không âm thoả mãn x_1+x_2+\cdots+x_m=n.

Bài 7. Cho k là một số nguyên dương và F là tập các bộ (A_1,A_2,\cdots, A_k) các tập con của tập \{1,2,\cdots,1998\}. Tính tổng \displaystyle S=\sum_{(A_1,A_2,\cdots,A_k)\in F}|A_1\cup A_2\cup\cdots\cup A_k|.

Bài 8. Cho n là một số nguyên dương. Giả sử M là tập tất cả các số nguyên dương viết trong hệ thập phân có n chữ số 1, n chữ số 2 và không có chữ số nào khác; N là tập tất cả các số nguyên dương viết trong hệ thập phân gồm n chữ số, chỉ chứa các chữ số 1,2,3,4 và số các số 1 bằng số các số 2. Chứng minh rằng |M|=|N|.

Bài 9. Cho n>1 là một số nguyên dương và S là dãy số 1,2,\cdots,n. Một dãy con của S được gọi là cấp số cộng cực đại của S nếu nó là một cấp số cộng và dãy này không thể thành một cấp số cộng dài hơn bằng cách bổ sung một phần tử. Hỏi có bao nhiêu cấp số cộng cực đại của S?

Bài 10. Cho A=\{a_1,a_2,\cdots,a_{100}\}B=\{1,2,\cdots,50\}. Hỏi có bao nhiêu ánh xạ f:A\to B sao cho f toàn ánh và f(a_1)\leq f(a_2)\leq\cdots\leq f(a_{100})?

Nếu f không cần toàn ánh thì sao?

Bài 11. Cho n>1 là một số nguyên dương và T_n là số các tập con khác rỗng của tập \{1,2,\cdots,n\} sao cho trung bình cộng tất cả các phần tử của nó là một số nguyên. Chứng minh rằng T_n-n là một số chẵn.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s