March 10, 2009 – Nguyen Trung Tuan

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”

M	T	W	T	F	S	S
« Nov				Jun »
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

	Lớp 9 Chuyên năm học… on Lớp 9 Chuyên năm học 2019…
	Nguyen Trung Tuan on Đề chọn đội VMO 2020
	Cao Yến Anh on Đề chọn đội VMO 2020
	Đề chọn đội VMO 2020… on Đề chọn đội VMO 2017
	Một số cuốn sách hay… on Một số sách về Olympic To…
	Cao Yến Anh on Đề thi chọn đội IMO 2019 của T…
	Nguyen Trung Tuan on IMO 2019 – Kết quả
	Nguyen Trung Tuan on IMO 2019 – Kết quả
	Cao Yến Anh on IMO 2019 – Kết quả
	Nguyen Trung Tuan on IMO 2019 – Problems and…