Day: March 10, 2009

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 và \{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\} và 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 C và C\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 X có n 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|=k và H=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\} và \{n,n(n-1)\}(n>2).
Bài 4. (Rumani TST 2002) Tìm tất cả các tập A và B 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} và 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 M và b\in M thì a+b\in M và ab\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 A và 1<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 và [\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}.

Solutions of the problems in the section 1 of GTM 81


Problem 1.1. (a) We have \infty\not\in\emptyset and \emptyset be open set in \mathbb{R}^n hence \emptyset be open set in X, we have also that X be open in X because \infty \in X and X-X=\emptyset be compact set in \mathbb{R}^n.
Assume that U,V are open sets in X, if \infty\not\in U or \infty\not\in V then \infty\not\in U\cap V and U\cap V is an open set in \mathbb{R}^n therefore U\cap V is open set in X. If \infty\in U and \infty\in V then U=\{\infty\}\cup U',V=\{\infty\}\cup V', here \infty\not\in U'\cup V' and \mathbb{R}^n-U',\mathbb{R}^n-V' are compact sets in \mathbb{R}^n. We have X-(U\cap V)=\mathbb{R}^n-(U'\cap V')=(\mathbb{R}^n-U')\cup (\mathbb{R}^n-V') is compact set in \mathbb{R}^n and \infty\in U\cap V therefore U\cap V be open set in X.
Assume that \{U_i\}_{i\in I} is a family of open sets in X and \infty\in U_i\forall i \in J,\infty\not\in U_i\forall i\in I-J for some J\subseteq I (maybe empty). If \infty\not\in\cup_{i\in I}U_i then \cup_{i\in I}U_i be open in \mathbb{R}^n, and so open in X. If \infty\in\cup_{i\in I}U_i then X-\cup_{i\in I}U_i=[\cap_{i\in J}(\mathbb{R}^n-U_i)]\cap [\cap_{i\in I-J}(\mathbb{R}^n-(U_i-\{\infty\}))] is closed and bound in \mathbb{R}^n, also it is compact set in \mathbb{R}^n, therefore \cup_{i\in I}U_i is open set in X.
Thanks to all conditions above we have X is a topological space.
Assume x\not=y are elements in X. If \infty \not\in \{x,y\} then x,y\in\mathbb{R}^n, note that because \mathbb{R}^n is Hausdorff space we can find open sets U_x,U_y in \mathbb{R}^n such that x\in U_x,y\in U_y and U_x\cap U_y=\emptyset(Note: U_x and U_y are also open sets in X). If \infty\in \{x,y\} , assume that y=\infty, denote U=S(x;1)=\{z\in\mathbb{R}^n|||z-x||<1\},\overline{U}=\{z\in\mathbb{R}^n|||z-x||\leq 1\} and V=\{\infty \}\cup (\mathbb{R}^n-\overline{U}). Then U,V are open sets in X, x\in U,y\in V and U\cap V=\emptyset.
Compactness of X is a immediately follows from (b).
(b)We have \sigma be a surjective because \sigma (0,\cdots,0,1)=\infty and \sigma (x_1,x_2,\cdots,x_{n+1})=(y_1,y_2,\cdots,y_n)\forall (y_i)\in\mathbb{R}^n, where x_i=\dfrac{2y_i}{k+1}(i=\overline{1,n}),x_{n+1}=\dfrac{k-1}{k+1},k=\sum_{i=1}^ny_i^2. But it is easy to see that \sigma is an injective(checking \sigma (x)=\sigma (y) then x=y), therefore \sigma is a bijective. By above formular, we have \sigma is a homeomorphism.(x_n\to x_0\Leftrightarrow \sigma (x_n)\to\sigma (x_0) in topology of \mathbb{R}^n)

Problem 1.2. We have D=\{z\in\mathbb{C}|cz+d\not =0\} is an open set in \mathbb{C} and f'(z)=\dfrac{ad-bc}{(cz+d)^2}\forall z\in D therefore f is holomorphic on D.
If c=0 then ad\not=0 we definition f:\mathbb{P}^1\to\mathbb{P}^1 by setting f(\infty)=\infty.
If c\not =0 then we definition f:\mathbb{P}^1\to\mathbb{P}^1 by setting f(\infty)=\dfrac{a}{c} and f(-\dfrac{d}{c})=\infty.
In both cases we have f is continuous over \mathbb{P}^1 and f is a bijective, it is easy to find formular of f^{-1} and check f and f^{-1} are holomorphic.

Problem 1.3.

Problem 1.4. The problem is wrong, an example \omega_1=1,\omega_2=i and \omega_1'=\sqrt{2}+i,\omega_2'=1+i\sqrt{2} and A=\left(\begin{matrix}\sqrt{2}&1\\1&\sqrt{2}\end{matrix}\right). Then \left(\begin{matrix}\omega_1'\\ \omega_2'\end{matrix}\right)=A\left(\begin{matrix}\omega_1\\ \omega_2\end{matrix}\right) and \omega_1'\not\in \Gamma . In my opinion, A must is belong to \text{SL}(2;\mathbb{Z}).
Problem 1.5. (a)Assume that U is open in \mathbb{C}/\Gamma' and f is original map. We have \pi^{-1}(f^{-1}(U))=\{y\in\mathbb{C}|\pi (y)\in f^{-1}(U)\}=\{y\in\mathbb{C}|\pi'(\alpha y)\in U\} and \pi'^{-1}(U) is open in \mathbb{C} therefore \pi^{-1}(f^{-1}(U)) is open in \mathbb{C}, so $f^{-1}(U)$ is open in \mathbb{C}/\Gamma , or f is continuous.
If \psi_1:U_1\to V_1 and \psi_2:U_2\to V_2 are complex charts of \mathbb{C}/\Gamma and \mathbb{C}/\Gamma', respectively, such that f(U_1)\subset U_2. We have \psi_2\cdot f\cdot \psi_1^{-1}(z)=\psi_2\cdot f ([z]_\Gamma ) =\psi_2 ([\alpha z]_{\Gamma'})=\alpha z\forall z\in V_1 therefore f is holomorphic.
If f is biholomorphic then f must is bijection and \alpha \Gamma =\Gamma'. In fact, if x\in \Gamma'-\alpha \Gamma then f([\dfrac{1}{\alpha}x])=f([0]) but [\dfrac{1}{\alpha}x]\not =[0], contradiction!
If \alpha \Gamma =\Gamma' then f is bijective and \dfrac{1}{\alpha}\Gamma'\subseteq \Gamma therefore by above, f and f^{-1} are holomorphic.
(b)We have \Gamma =\mathbb{Z}\omega_1+\mathbb{Z}\omega_2=\omega_1(\mathbb{Z}+\mathbb{Z}\cdot\dfrac{\pm\omega_2}{\omega_1}) and use (a).
(c)Use (a) again!

VMO Training 2009 – Giải tích


Bài 1. Cho (x_n)_{n\geq 0} là dãy các số thực xác định bởi x_1=0,x_2=2 và x_{n+2}=2^{-x_n}+\dfrac{1}{2}\forall n=1,2,\cdots
Chứng minh rằng dãy số này hội tụ và tìm giới hạn của nó.

Bài 2. Cho hàm số f:(0;\infty)\to (0;\infty) thoả mãn điều kiện f(3x)\geq f(\dfrac{1}{2}f(2x))+2x\forall x>0.
Chứng minh rằng f(x)\geq x\forall x>0.

Bài 3. Cho dãy số (a_n) xác định bởi a_1=1,a_{n+1}=a_n+\dfrac{1}{\sqrt{a_n}}\forall n\geq 1. Tìm tất cả các số thực \alpha sao cho dãy (a_n^{\alpha}/n) có giới hạn hữu hạn khác 0 khi n\to \infty.

Bài 4. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} thoả mãn f(x^2+y+f(y))=f^2(x)+2y\forall x,y\in\mathbb{R}.

Bài 5. Cho hàm số f:\mathbb{R}\to\mathbb{R} liên tục trên \mathbb{R} và phương trình f(x+f(x+\cdots+f(x)\cdots))=2008 (2008 chữ f) có nghiệm. Chứng minh rằng phương trình f(x)=x cũng có nghiệm.

Bài 6. Tìm tất cả các hàm số f:\mathbb{R}\to\mathbb{R} sao cho \forall x,y,z\in\mathbb{R}:|x-y|<|x-z|\Longrightarrow |f(x)-f(y)|<|f(x)-f(z)|.

Bài 7. Cho hai dãy (a_n) và (b_n) xác định bởi a_0=\sqrt{2},b_0=2,a_{n+1}=\sqrt{2-\sqrt{4-a_n^2}},b_{n+1}=\dfrac{2b_n}{2+\sqrt{4+b_n^2}}\forall n\geq 0. Chứng minh rằng các dãy (a_n),(b_n) giảm và hội tụ đến 0, dãy (2^na_n) tăng, dãy (2^nb_n) giảm và hai dãy này hội tụ đến cùng một giới hạn. Chứng minh rằng có hằng số C>0 sao cho $latex

Bài 8. Chứng minh rằng với mỗi số nguyên dương n ta có \dfrac{e}{2n+2}<e-\left(1+\dfrac{1}{n}\right)^n<\dfrac{e}{2n+1}.

Bài 9. Cho các số nguyên dương k,s và các số thực dương a_1,a_2,\cdots,a_k;b_1,b_2,\cdots,b_s sao cho \sqrt[n]{a_1}+\sqrt[n]{a_2}+\cdots+\sqrt[n]{a_k}=\sqrt[n]{b_1}+\sqrt[n]{b_2}+\cdots+\sqrt[n]{b_s} với vô hạn số nguyên dương n. Chứng minh rằng k=s và \prod a_i=\prod b_j. Continue reading “VMO Training 2009 – Giải tích”