Tập hợp và tập hợp con


Trong bài này chúng ta sẽ quan tâm đến các tập hợp nhưng không quan tâm đến tính chất của các phần tử của nó.

Bài 1. Chứng minh rằng số tập con của tập có n phần tử bằng 2^n.

Lời giải. Dùng phương pháp quy nạp theo n hoặc chú ý là mỗi tập con sẽ ứng với một xâu nhị phân có độ dài n.
Bài 2. Cho 1978 tập hợp A_{1},\cdots,A_{1978} thoả mãn các tính chất sau
a)|A_i\cap A_j|=1\forall i<j;
b)|A_i|=40\forall i.
Chứng minh rằng |\cap A_i|=1.
Lời giải. Gỉa sử ngược lại, khi đó giao của các tập hợp phải bằng rỗng. Gỉa sử m là số nguyên dương lớn nhất sao cho trong các tập đó ta tìm được m tập có giao khác rỗng. Không giảm tổng quát gọi các tập đó là A_1,A_2,\cdots,A_m\{x\}=\cap_{i=1}^mA_i, cố định A_1, trong 1977 tập còn lại vì mỗi tập giao với A_1 tại đúng một phần tử và chúng đôi một giao nhau đúng một phần tử, suy ra x thuộc ít nhất [1977/40]+1=50 tập trong 1977 tập này, suy ra m\geq 51. Vì x không thuộc A_{m+1} nên x sẽ không thuộc m tập A_i\cap A_{m+1}, đương nhiên m tập này đôi một rời nhau và là các tập con của A_{m+1}, suy ra m\leq 40, vô lý! Bài toán được giải hoàn toàn.
Bài 3. Tìm số các bộ ba có thứ tự các tập (A,B,C) sao cho A\cup B\cup C=\{1,2,\cdots,2003\}A\cap B\cap C=\emptyset.
Lời giải. Mỗi bộ ba như vậy ứng với một xâu (a_1,a_2,\cdots,a_{2003})\in \{1,2,3,4,5,6\}^{2003}, vì mỗi phần tử i chỉ có thể thuộc A,B,C,A\cap B,B\cap CC\cap A. Đáp số 6^{2003}.
Bài 4. Có bao nhiêu cặp có thứ tự tập hợp con không giao nhau của tập hợp gồm n phần tử?
Lời giải. Kí hiệu một cặp nào đó như đầu bài là (A_1,A_2). Nếu |A_1|=k thì chúng ta sẽ có C_n^k cách chọn A_1, sau khi chọn A_1 rồi thì số cách chọn A_2 bằng số cách chọn một tập con của tập S-A_1, tập này có n-k phần tử (S là tập có n phần tử trong đầu bài), hay số cách chọn A_2 bằng 2^{n-k}. Vậy đáp số của bài toán là \sum_{k=0}^n C_n^k2^{n-k}=(2+1)^n=3^n.
Cách tiếp cận khác: Mỗi cặp như vậy sẽ ứng với một xâu (a_1,a_2,\cdots,a_n)\in\{0,1,2\}^n vì mỗi phần tử của S có thể thuộc A_1, hoặc A_2, hoặc không thuộc cả hai tập đó.

Bài 5. Tập Xn phần tử. Đối với cặp có thứ tự tập con (A_1,A_2) của X, ta tính số phần tử của A_1\cap A_2. Chứng minh rằng tổng các số nhận được bằng n4^{n-1}.
Lời giải. Gỉa sử (A_1,A_2) là một cặp tập con của X, |A_1\cap A_2|=kH=A_1\cap A_2. Ta thấy có C_n^k cách chọn H, sau khi đã chọn H rồi thì số cách chọn (A_1,A_2) bằng số cách chọn cặp (B_1,B_2) các tập con rời nhau của tập X-H, vì tập này có n-k phần tử nên số các cặp (B_1,B_2) bằng 3^{n-k}. Vậy đáp số của bài toán là \sum_{k=0}^nkC_n^k3^{n-k}=n4^{n-1}.
Cách tiếp cận khác: Có 4^n cặp tập (A_1,A_2), chia các cặp này thành các bộ bốn \{(A_1,A_2),(\overline{A}_1,A_2),(A_1,\overline{A}_2),(\overline{A}_1,\overline{A}_2)\}, mỗi phần tử của X sẽ thuộc đúng một trong bốn giao hình thành từ bộ này, do đó tổng đối với bộ này bằng n, mà có đúng 4^{n-1} bộ nên ta có điều phải chứng minh.

Bài 6. Đối với mỗi số nguyên dương n, tìm số nguyên dương k lớn nhất sao cho trong một tập hợp có n phần tử có thể chọn ra k tập con của nó đôi một giao nhau.
Lời giải. Gọi X là một tập có n phần tử và a là một phần tử của nó. Xét 2^{n-1} tập con của X có dạng \{a\}\cup A với A là một tập con của tập X-\{a\}, rõ ràng các tập con này là đôi một giao nhau (cách chọn như vậy là dễ nhất và đây cũng là chìa khoá cho lời giải). Mặt khác với mỗi cách chọn lớn hơn 2^{n-1} tập con của X, bao giờ cũng tồn tại hai tập trong cùng một bộ \{A,\overline{A}\} và hai tập này giao nhau bằng rỗng. Vậy đáp số của bài toán là 2^{n-1}.

Bài 7. Gỉa sử trong tập hữu hạn X chọn ra 50 tập hợp con A_1,A_2,\cdots,A_{50} sao cho mỗi tập này chứa hơn một nửa phần tử của X. Chứng minh rằng tồn tại tập con A của X thoả mãn các điều kiện sau
a)|A|<6, và
b)A\cap A_i\not =\emptyset.

Bài 8(APMO 1998). Cho F_n là tập tất cả các n-bộ (A_1,A_2,\cdots,A_n) sao cho mỗi A_i là một tập con của tập \{1,2,\cdots,2009\}. Tính \sum_{(A_1,A_2,\cdots,A_n)\in F_n}|A_1\cup A_2\cup\cdots\cup A_n|.

Bài 9(RMC 2006). Một tập M gồm 4 số nguyên dương được gọi là liên thông nếu với mỗi x trong M ít nhất một trong các số x-1,x+1 thuộc M. Cho U_n là số các tập con liên thông của tập \{1,2,\cdots,n\}.
a)Tính U_7;
b)Tìm n nhỏ nhất để U_n\geq 2006.

Bài 10(RMC 2006). Tìm số lớn nhất các tập con của tập \{1,2,\cdots,2006\} sao cho mỗi hai tập con khác nhau trong chúng có giao là một tập có 2004 phần tử.

Các tập hợp số


Bài 1(APMO 2004). Tìm tất cả các tập hữu hạn khác rỗng S các số nguyên dương sao cho \dfrac{i+j}{\gcd (i,j)}\in S\forall i,j\in S.
Lời giải. S=\{2\}.
Bài 2(Rumani TST 2008). Cho n>1 là một số nguyên dương. Tìm tất cả các tập A gồm n số nguyên sao cho tổng của tất cả các phần tử của mỗi tập con khác rỗng của A không chia hết cho n+1.
Lời giải. Các phần tử của A bằng nhau theo modulo n+1, chúng đồng dư với p, ở đây \gcd (p,n+1)=1.
Bài 3(Rumani TST 2007). Tìm tất cả các tập con A của tập các số nguyên dương sao cho A có ít nhất 2 phần tử và với mỗi x,y\in A (x\not =y) chúng ta có \dfrac{x+y}{\gcd (x,y)}\in A.
Lời giải. Xét hai trường hợp các phần từ đôi một không nguyên tố và có hai phần tử nguyên tố. Đáp số \mathbb{N}^*,\mathbb{N}^*-\{1\},\mathbb{N}^*-\{2\},\mathbb{N}^*-\{1,2\}\{n,n(n-1)\}(n>2).
Bài 4. (Rumani TST 2002) Tìm tất cả các tập AB sao cho
a)A\cup B=\mathbb{Z};
b)Nếu x\in A thì x-1\in B;
c)Nếu x,y\in B thì x+y\in A.
Lời giải. A=\mathbb{Z},B=\mathbb{Z}A=\{2k|k\in\mathbb{Z}\} , B=\{2k+1|k\in\mathbb{Z}\}.

Bài 5. Cho tập hợp khác rỗng M\subset\mathbb{Q} thoả mãn hai điều kiện
a)Nếu a\in Mb\in M thì a+b\in Mab\in M;
b)Nếu r\in\mathbb{Q} thì xảy ra đúng một trong ba khả năng sau r\in M,-r\in M,r=0.
Chứng minh rằng M là tập các số hữu tỷ dương.

Bài 6(RMC 2004). Kí hiệu \mathbb{P} là tập tất cả các số nguyên tố. Gỉa 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|>2;
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ố \prod_{p\in A}p-1 cũng thuộc M.
Chứng minh rằng M=\mathbb{P}.

Bài 7(Romania TST 2004). Cho A là một tập con của \mathbb{Z}^+ có các tính chất
a)Nếu a\in A thì tất cả các ước dương của a cũng thuộc A;
b)Nếu a,b\in A1<a<b thì 1+ab\in A;
c)|A|>2.
Chứng minh rằng A=\mathbb{Z}^+.

Bài 8(RMC 2006). Cho A là tập các số nguyên không âm có ít nhất hai phần tử sao cho nếu a,b\in A, a>b thì số \dfrac{\text{lcm}\, (a,b)}{a-b}\in A. Chứng minh rằng A có đúng hai phần tử.

Bài 9(RMC 2006). Xét các tập A=\{\sqrt{\dfrac{1}{a}+\dfrac{1}{b}}|a,b\in\mathbb{Z}^+,a\not =b\}  và B=\{\sqrt{\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}}|x,y,z\in\mathbb{Z}^+,x>y>z\}.
Chứng minh rằng A\cap B chứa vô hạn các số hữu tỷ và vô hạn các số vô tỷ.
Lời giải. Quan tâm đến phương trình \dfrac{1}{n}=\dfrac{1}{x}+\dfrac{1}{y}.
Bài 10(RMC 2007). Tìm tất cả các tập con khác rỗng A của tập \{2,3,\cdots\} sao cho với mỗi n\in A, cả hai số n^2+4[\sqrt{n}]+1 cũng thuộc A.
Bài 11(France 2002). Xét 2002 số hữu tỉ x_1,x_2,\cdots,x_{2002}. Biết rằng với mỗi tập con I gồm 7 phần tử của tập \{1,2,\cdots,2002\} tồn tại tập con J gồm 11 phần tử của tập \{1,2,\cdots,2002\} sao cho \dfrac{1}{7}\sum_{i\in I}x_i=\dfrac{1}{11}\sum_{j\in J}x_j. Chứng minh rằng x_1=x_2=\cdots=x_{2002}.

Polynomials by Victor V. Prasolov


Download all following 5 files

http://uploadwordpress.googlepages.com/1-PrasolovPolynomials.part1.rar

http://uploadwordpress.googlepages.com/2-PrasolovPolynomials.part2.rar

http://uploadwordpress.googlepages.com/3-PrasolovPolynomials.part3.rar

http://uploadwordpress.googlepages.com/4-PrasolovPolynomials.part4.rar

http://uploadwordpress.googlepages.com/5-PrasolovPolynomials.part5.rar

Note: Use winrar.

Solution of problem 11306 in AMM


Let a,b, and c be the lengths of the sides of a nondegenerate triangle, let p=(a+b+c)/2, and let r and R be the inradius and circumradius of the triangle, respectively. Show that \dfrac{a}{2}\cdot \dfrac{4r-R}{R}\leq\sqrt{(p-b)(p-c)}\leq \dfrac{a}{2},

and determine the cases of equality.

My solution.

Continue reading “Solution of problem 11306 in AMM”