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.

Continue reading “17/11/2013”

16/11/2013


Bài 18. Chứng minh định lý Wilson.

Bài 19. Cho số nguyên dương lẻ n>1. Gọi S là tập các số nguyên x\in [n] sao cho \gcd (x,n)=\gcd (x+1,n)=1. Chứng minh rằng \displaystyle\prod_{x\in S}x\equiv 1\pmod{n}.

Bài 20. Cho số nguyên tố p>3. Chứng minh rằng nếu ab là các số nguyên dương thỏa mãn

1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{p-1}=\dfrac{a}{b}

thì a chia hết cho p^2.

Bài 21. Cho p là một số nguyên tố. Chứng minh rằng phương trình x^2+1\equiv 0\pmod{p} có nghiệm nguyên khi và chỉ khi p=2 hoặc p\equiv 1\pmod{4}. Từ kết quả này hãy đưa ra một chứng minh cho định lý Fermat về tổng của hai bình phương.

Bài 22. (Euler,1749)

Đặt S=\{x^2+y^2|\,x,y\in\mathbb{N}\}.

a) Chứng minh rằng ab\in S\,\,\forall (a,b)\in S^2;

b) Chứng minh rằng nếu m\in Sp là một số nguyên tố trong S thỏa mãn p|m thì \frac{m}{p}\in S;

c) Chứng minh rằng nếu a,b là các số nguyên dương thỏa mãn a\in S,b\not\in Sb|a thì \frac{a}{b} có ít nhất một ước không nằm trong S;

d) Gọi T là tập các số nguyên dương có ít nhất một bội có dạng a^2+b^2 với ab là các số nguyên dương nguyên tố cùng nhau. Chứng minh rằng nếu t_1\in T-S thì có t_2\in T-S sao cho t_2<t_1. Từ đó suy ra rằng T\subset S;

e) Cho số nguyên tố p=4n+1\, (n\in\mathbb{N}^*). Chứng minh rằng p là ước của (i+1)^{4n}-i^{4n} với mỗi i=1,2,\cdots,4n-1. Từ đó suy ra p\in S.

Bài 23. Cho tập khác rỗng X và một ánh xạ f:X\to X. Ánh xạ f được gọi là một involution trên X nếu f(f(a))=a\,\,\forall a\in X. Chứng minh rằng nếu X là một tập hữu hạn khác rỗng, f là một involution trên X thì |X||X_f| là cùng tính chẵn lẻ. Ở đây X_f là tập các điểm bất động của f.

Bài 24. (Don Zagier,1990) Cho p là một số nguyên tố thỏa mãn p\equiv 1\pmod{4}S là tập các bộ ba (a,b,c) các số nguyên dương sao cho a^2+4bc=p. Xét các ánh xạ f,g:S\to S được xác định bởi f(a,b,c)=(a,c,b)\,\,\forall (a,b,c)\in Sg(a,b,c)=(a+2c,c,b-a-c) nếu a<b-c, =(2b-a,b,a-b+c) nếu b-c<a<2b, =(a-2b,a-b+c,b) nếu a>2b với mỗi (a,b,c)\in S.

1) Chứng minh rằng f,g là các involution trên S;

2) Chứng minh rằng |S_g|=1;

3) Chứng minh rằng có các số nguyên dương a,b để p=a^2+b^2.

14/11/2013


Bài 12. Cho p là một số nguyên tố có dạng 4k+3\,\, (k\in\mathbb{N} và hai số nguyên a,b. Chứng minh rằng a^2+b^2\equiv 0\pmod{p} khi và chỉ khi a\equiv 0\pmod{p}b\equiv 0\pmod{p}. Từ đó suy ra rằng có vô hạn các số nguyên tố có dạng 4k+1\,\, (k\in\mathbb{N}).

Bài 13. Tìm tất cả các số nguyên dương n sao cho 7|2^n-1. Chứng minh rằng không có số nguyên dương n thỏa mãn 7|2^n+1.

Bài 14. Chứng minh rằng tập \{2^n-3|n=2,3,\cdots\} có một tập con vô hạn S sao cho hai phần tử khác nhau bất kì của S nguyên tố cùng nhau.

Bài 15. Kí hiệu \mathbb{P} là tập tất cả các số nguyên tố. Giả sử rằng M là một tập con của \mathbb{P} thoả mãn các điều kiện sau

a) M có ít nhất ba phần tử;

b) Với mỗi tập con thực sự, khác rỗng và hữu hạn A của M , các ước nguyên tố của số -1+\displaystyle\prod_{p\in A}p cũng thuộc M.

Chứng minh rằng M=\mathbb{P}.

Bài 16. Tìm tất cả các số nguyên dương nguyên tố cùng nhau với mỗi số hạng của dãy (a_k) xác định bởi a_n=2^n+3^n+6^n-1\,\,\forall n\geq 1.

Bài 17. Dãy số (u_n) xác định bởi u_1=0,u_2=14,u_3=-18

u_{n+1}=7u_{n-1}-6u_{n-2}\,\,\forall n\geq 3.

Chứng minh rằng với mỗi số nguyên tố p ta có p|u_p.

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.

Continue reading “10/11/2013”