17/11/2013


Bài 25. Chứng minh nguyên lý bù-trừ: Nếu A_1,A_2,\cdots,A_n là các tập hữu hạn thì

|\cup_{i=1}^nA_i|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-1)^{n+1}|\cap_{1\leq i\leq n}A_i|.

Bài 26. Tìm số các số nguyên dương trong \{1,2,\cdots,500\} chia hết cho 2 hoặc 3 hoặc 5.

Bài 27. Tính giá trị của phi hàm Euler tại n theo phân tích chính tắc của n.

 

Bài 28. Chứng minh nguyên lý bù-trừ bằng quy nạp toán học.

 

Bài 29. Cho X là một tập hữu hạn và A,B,C là các tập con của nó. Chứng minh rằng |\bar{A}\cap B|=|B|-|A\cap B||\bar{A}\cap\bar{B}\cap C|=|C|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.

 

Bài 30. Tìm số các số nguyên trong tập \{1,2,\cdots,1000\} không chia hết cho 5, không chia hết cho 7, nhưng chia hết cho 3.

 

Bài 31. Có bao nhiêu số nguyên dương n sao cho n là ước của ít nhất một trong hai số 10^{40}20^{30}?

 

Bài 32.

1/. Có bao nhiêu song ánh từ S=\{1,2,\cdots,n\} đến chính S sao cho nó không có điểm cố định?

2/. Với mỗi số nguyên dương n>1, gọi A_n là số các song ánh từ S đến S sao cho f(k) khác k+1 với mỗi k=1,2,\cdots,n-1.

a)Tính A_n;

b)Chứng minh rằng A_n=D_n+D_{n-1} với mỗi n>1. (D_n là kết quả ở câu 1/.)

 

Bài 33. Tìm số các số nguyên dương là ước của ít nhất một trong các số 10^{60},20^{50},30^{40}.

 

Bài 34. Với k=1,2,\cdots,1992 cho A_k là một tập với 44 phần tử. Giả sử rằng |A_i\cap A_j|=1 với mỗi i,j khác nhau trong \{1,2,\cdots,1992\}. Tính |\cup_{i=1}^{1992}A_i|.

 

Bài 35. Cho A_1,A_2,\cdots,A_nn tập hữu hạn. Chứng minh rằng

|\cup_{i=1}^nA_i|\geq \sum_{i=1}^n|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|.

Sử dụng bất đẳng thức này để giải bài toán sau: Một hoán vị của \{1,2,\cdots,2n\} được gọi là có tính chất P nếu có ít nhất hai số dạng k,n+k đứng cạnh nhau. 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ố các hoán vị không có tính chất đó.

Bài 36. Cho các số nguyên dương m\leq nA,B là các tập có n,m phần tử tương ứng. Tìm số các toàn ánh từ A lên B. Từ đó suy ra \sum_{k=0}^n(-1)^kC_n^k(n-k)^n=n!.

Bài 37. a) Cho A là một tập hữu hạn và f là một hàm từ A đến \mathbb{R}. Với mỗi tập con B của A ta đặt f(B)=\sum_{x\in B}f(x)f(\emptyset)=0. Chứng minh rằng nếu A=\cup_{i=1}^nA_i thì f(A)=\sum_{I\not =\emptyset}(-1)^{|I|+1}f\left(\cap_{i\in I}A_i\right),

ở đây tổng chạy trên các tập con của \{1,2,\cdots,n\};

b) Cho n>1 là một số nguyên và a_1,a_2,\cdots,a_{\varphi (n)} là các số trong tập \{1,2,\cdots,n\} nguyên tố cùng nhau với n. Chứng minh rằng

a_1^2+a_2^2+\cdots+a_{\varphi (n)}^2=\dfrac{\varphi (n)}{6}(2n^2+(-1)^kp_1p_2\cdots p_k),

ở đây p_1,p_2,\cdots,p_k là các ước nguyên tố phân biệt của n.

Bài 38. Tìm số các lời giải nguyên không âm của x_1+x_2+x_3=15 với x_1\leq 5,x_2\leq 6x_3\leq 7.

Bài 39. Tìm số nghiệm nguyên của phương trình x_1+x_2+x_3=28 với 3\leq x_1\leq 9,0\leq x_2\leq 87\leq x_3\leq 17.

Bài 40. Tìm số nghiệm nguyên của phương trình x_1+x_2+x_3=40 với 6\leq x_1\leq 15, 5\leq x_2\leq 2010\leq x_3\leq 25.

Bài 41. Tìm số lời giải nguyên của phương trình x_1+x_2+x_3+x_4=20 thoả mãn 1\leq x_1\leq 5,0\leq x_2\leq 7,4\leq x_3\leq 82\leq x_4\leq 6.

Bài 42. Cho k,n,r là các số nguyên dương. Chứng minh rằng số nghiệm nguyên của phương trình x_1+x_2+\cdots+x_n=r sao cho 0\leq x_i\leq k với mỗi i bằng \sum_{i=0}^n(-1)^iC_n^iC_{r-(k+1)i+n-1}^{n-1}, và nếu thay điều kiện bởi 1\leq x_i\leq k với mỗi i thì số nghiệm bằng \sum_{i=0}^n(-1)^iC_n^iC_{r-ki-1}^{n-1}.

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