Tag Archives: anhxa

Ánh xạ – Bài tập

Bài giảng ánh xạ

Bài 1 Trong các quy tắc sau, quy tắc nào là ánh xạ?

a) Xét quy tắc $f$ từ tập các số nguyên $\mathbb{Z}$ vào $X = \{-1, 0 , 1\}$ sao cho với mỗi $x\in \mathbb{Z}$ thì:
$f\left( x \right) = \left\{ \begin{gathered}
– 1 \,\, khi\,\,\,x < 0 \hfill \\
0 \,\, khi\,\,\,x = 0 \hfill \\
1 \,\, khi\,\,\,x > 0 \hfill \\
\end{gathered} \right.$

a)Xét quy tắc cho tương ứng mỗi số thực dương $x$ với số thực $y$ sao cho $y^2 = x$.
b)Cho tương ứng các điểm $M$ thuộc mặt phẳng với các điểm $M’$ thuộc mặt phẳng sao cho $\overrightarrow{MM’} = \overrightarrow{u}$ cho trước.
c)Trong mặt phẳng cho tương ứng điểm $M$ với điểm $M’$ sao cho $MM’ = r > 0$ cho trước.
d)Trong mặt phẳng cho đường thẳng $d$. Quy tắc cho tương ứng $M$ thuộc $d$ ứng với $M$, $M$ không thuộc $d$ ứng với $M’$ sao cho $MM’ \bot d$.
e)Quy tắc cho tương ứng mỗi số hữu tỷ ứng với 1, mỗi số vô tỷ ứng với 0.

Bài 2 Trong các ánh xạ ở bài trên, ánh xạ nào là đơn ánh, song ánh, toàn ánh?

Bài 3 Trong các ánh xạ sau, ánh xạ nào là đơn ánh, toàn ánh, song ánh?

a)Ánh xạ $f: \mathbb{R} \to \mathbb{R}$ thỏa $f(x) = x^3$.
b)Ánh xạ $f: \mathbb{Z} \to \mathbb{N}$ thỏa $f(x) = |x|$.
c)Cho tương ứng mỗi số thực với phần nguyên của nó.

Bài 4 Cho ánh xạ $f: \mathbb{R} \to \mathbb{R}: f(x) = x^2+3x+1$.

a)$f$ có là đơn ánh?
b)$f$ có là toàn ánh không?

Bài 5 Cho $f: (0;1) \to (0;+\infty) $ thỏa $f(x) = \dfrac{x}{1-x}$.

a)Tìm $f(f(x))$.
b)Chứng minh $f$ là song ánh.
c)Tìm ánh xạ ngược của $f$.

Bài 6 Cho $A, B, C, D$ là các tập con của $X$. Đặt ${\chi _D}\left( x \right) = \left\{ \begin{gathered}
1\,\,\,\,\,khi\,\,\,x \in D \hfill \\
0\,\,\,\,khi\,\,\,x \notin D \hfill \\
\end{gathered} \right.$.
Chứng minh rằng:

a)Quy tắc trên là ánh xạ từ $X$ vào ${0, 1}$.
b)$\chi A\cdot \chi _A = \chi_A,\chi{X\backslash A} = 1 – \chi_A$
c)$\chi {A \cap B} = \chi_A.\chi _B,\chi{A \cup B} = \chi_A+ \chi_B – \chi_A\cdot \chi_B$
d)$\chi_A \geqslant \chi _B \Leftrightarrow B \subset A,\chi_A \equiv 0 \Leftrightarrow A = \emptyset $

Bài 7 Cho $f: X \to Y$. $A, B$ là các tập con của $X$; $C, D$ là các tập con của $Y$. Đặt $f(A) = {f(x)|x \in A}$ là tập ảnh của $A$; $f^{-1}(C) = {x \in X|f(x) \in X}$ là tạo ảnh của $C$.

a)Chứng minh nếu $A \subset B$ thì $f(A) \subset f(B)$.
b)Nếu $C \subset D$ thì $f^{-1}(C) \subset f^{-1}(D)$.
c)$f(A\cup B) = f(A) \cup f(B)$.
c)$f(A \cap B) \subset f(A) \cap f(B)$. Và $f(A \cap B) = f(A) \cap f(b)$ khi $f$ là đơn ánh.
d)$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ và $f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D)$.
e)$A \subset f^{-1}(f(A))$.

Bài 8 Cho $h: A \to B$, $g:B \to C$ và $f: C \to D$.

a)Chứng minh rằng nếu $f\circ g$ là đơn ánh và $f$ toàn ánh thì $g$ đơn ánh.
b)Nếu $f \circ g$ là toàn ánh thì $f$ cũng là toàn ánh.
c)Nếu $f, g$ là đơn ánh(toàn ánh, song ánh) thì $f \circ g$ cũng là đơn ánh (toàn ánh, song ánh).
d)Nếu $h$ là song ánh thì $h^{-1}$ cũng là song ánh.
e)Nếu $f \circ g$ và $g \circ h$ là song ánh thì $f, h, g$ cũng là song ánh.

Bài 9 Cho ánh xạ$f:\mathbb{R} \mapsto \left\{ {0,1} \right\}$

$f\left( x \right) = \left\{ \begin{gathered}
1\,\,\,khi\,\,x \in \mathbb{Q} \hfill \\
0\,\,khi\,\,x \notin \mathbb{Q} \hfill \\
\end{gathered} \right.$

a) Tìm tập ảnh của $f$.
b)Tìm ${f^{ – 1}}\left( 1 \right),{f^{ – 1}}\left( 0 \right)$
c)$f$ có là song ánh không? Vì sao?

Bài 10 Cho $A$ và $B$ là hai tập hợp sao cho có một đơn ánh từ $A$ vào $B$. Chứng minh rằng có một toàn ánh từ $B$ vào $A$.

Bài 11 Cho $A$ và $B$ là hai tập hợp sao cho có một toàn ánh từ $A$ vào $B$. Chứng minh rằng có một đơn ánh từ $B$ vào $A$.

Bài 12 Tìm một song ánh từ tập tập các số tự nhiên chẵn đến tập các số tự nhiên lẻ.

Bài 13 Tìm một đơn ánh từ tập các số tự nhiên đến tập các số nguyên.

Bài 14 Tìm một song ánh từ tập các số tự nhiên đến tập các số nguyên.

Bài 15 Tìm một song ánh từ tập $\mathbb{N} \times \mathbb{N}$ đến $\mathbb{N}^*$.

Bài 16 Gọi tập X là tập gồm các khoảng có dạng $\left( {a,b} \right)$ thỏa $0 \leqslant a < b \leqslant 1$.
Xét ánh xạ $X \to \left( {0,1} \right),f\left( {\left( {a,b} \right)} \right) = \frac{{a + b}}{2}$

a)$f$ có phải đơn ánh không? Vì sao?
b)$f$ có phải toàn ánh không? Vì sao?

Bài 17 Cho $X$ là tập khác rỗng, $P(X)$ là tập tất cả các tập con của $X$. Có tồn tại hay không một song ánh đi từ $X$ đến $P(X)$?

Bài 18 Tìm một song ánh từ tập $(0;1)$ đến tập các số thực.

Bài 19 Cho $m$ là số nguyên dương và tập $X = \{-m, -m+1, …, -1, 0, 1, …,m\}$. \Ánh xạ $f: X \to X$ thỏa $f(f(n)) = -n$ với mọi $n \in X$.\
Chứng minh $m$ là số chẵn.

Phương pháp ánh xạ trong các bài toán tổ hợp

Bài viết dựa vào bài giảng của NCS. Vương Trung Dũng (trường PTNK-ĐHQG) trong lớp chuyên đề 10 toán tại Star Education.

 

Ánh xạ là một khái niệm khó và quan trọng trong toán học, có vai trò trong hầu hết các lĩnh vực toán học. Trong bài giảng này ta xét ứng dụng của ánh xạ trong các bài toán tổ hợp.

Ánh xạ và một số tính chất

Định nghĩa. Cho hai tập hợp $X$ và $Y$ khác rỗng. Một ánh xạ $f$ từ tập $X$ đến tập $Y$ là một quy tắc đặt tương ứng mỗi phần tử $x$ của $X$ với một và chỉ một phần tử $y$ của $Y$, kí hiệu là $y = f(x)$.

Kí hiệu $f: X \longrightarrow Y$.

$f(x) = y$.

Các khái niệm: Cho ánh xạ $f: X \longrightarrow Y$.

  • $y = f(x)$ được gọi là ảnh của $x$.
  • $f(X) = \{f(x)|x \in X\}$ tập ảnh của $f$.
  • $y \in Y$ thì $f^-1(y) = \{x\in X|f(x) = y\}$ được gọi là tạo ảnh của $y$.

Đơn ánh, toàn ánh, song ánh

  1. Ánh xạ $f: X \longrightarrow Y$ được gọi là đơn ánh nếu với $a,b \in X$ mà $a \ne b$ thì $f(a) \ne f(b)$. Nói một cách khác ánh xạ $f$ là một đơn ánh nếu và chỉ nếu với $a, b \in X$ mà $f(a)=f(b)$ thì suy ra $a=b.$
  2. Ánh xạ $f:X \longrightarrow Y$ được gọi là toàn ánh nếu với mỗi phần tử $y \in Y$ đều tồn tại một phần tử $x \in X$ sao cho $f(x)=y$. Như vậy $f$ là toàn ánh nếu và chỉ nếu $f(X)=Y$.
  3. Ánh xạ $f: X \longrightarrow Y$ được gọi là song ánh giữa $X$ và $Y$ nếu và chỉ nếu nó vừa là đơn ánh và vừa là toàn ánh. Như vậy $f$ là song ánh nếu với mỗi $y \in Y$ tồn tại duy nhất một phần tử $x \in X$ sao cho $y=f(x).$

Ánh xạ và tập hợp

Cho $A = { 1, 2,\cdots, n }$. $X$ là tập khác rỗng. Nếu có một song ánh từ tập $X$ đến $A$ thì ta nói $X$ có $n$ phần tử và kí hiệu $|X| = n$.

Nếu không tồn tại song ánh thì ta nói $X$ có vô hạn phần tử.

  • Nếu tồn tại một song ánh từ $X$ vào tập các số tự nhiên, ta nói $X$ có lực lượng đếm được, ngược lại thì ta nó $X$ có lực lượng không đếm được.
  • Các tập số tự nhiên, số nguyên và hữu tỷ là các tập có lực lượng đếm được.

Định lý Cho $A$ và $B$ là hai tập hợp hữu hạn.

  • Nếu có một đơn ánh $f: X \longrightarrow Y$ thì $|X| \le |Y|.$
  • Nếu có một toàn ánh $f: X \longrightarrow Y$ thì $|X| \ge |Y|.$
  • Nếu có một song ánh $f: X \longrightarrow Y$ thì $|X| = |Y|.$

Ánh xạ và các bài toán đếm, đẳng thức tổ hợp.

Ví dụ 1. Cho tập $X_n = {1, 2, \cdots, n}$, gọi $P(X_n)$ là tập các tập con của $X_n$, và $S_n$ là tập các dãy nhị phân có độ dài $n$. Tìm một song ánh từ $P(X_n)$ vào $S_n$, suy ra số tập con của $X_n$.

Gợi ý

Định nghĩa một ánh xạ $f: P(X_n) \longrightarrow S_n$ như sau:
Với mỗi $S \in P(X_n)$ (tức là $S \subset X_n$) ta đặt $$ f(S)=y_1y_2 \dots y_n$$
trong đó
$$y_i=\begin{cases}
1, y_i \in S&\\
0, y_i \notin S.&
\end{cases}
$$
Ví dụ , nếu $X=\{1; 2; 3; 4; 5\}, S_1=\{4\}, S_2=\{2; 3; 5\}$ thì $f(S_1)=00010, f(S_2)=01101, f(\emptyset)=00000, f(X)=11111$ .
Dễ dàng kiểm tra đây là một song ánh từ $P(X)$ vào $Y$.
Do đó theo nguyên lý song ánh ta có $|P(X)|=|Y|=2^n$.

Ví dụ 2. Hãy tính trung bình cộng của tất cả các số N gồm 2014 chữ số thỏa mãn N chia hết cho 9 và các chữ số của N được lập từ $X={1,2,…,8}$

Gợi ý

Gọi M là tập các số thỏa yêu cầu đề bài.

Ta xây dựng một ánh xạ đi từ M đến M như sau: Với mỗi $N=\overline{a_1a_2…a_{2014}} \in M$ dặt $f(N)=\overline{b_1,b_2,…,b_{2014}}$ với $b_i=9-a_i$ với mọi $i=1,2,…,2014$. Vì $N+f(N)=99…9$ (2014 số 9) chia hết cho 9 và N chia hết cho 9 nên suy ra $f(N)$ cũng chia hết cho 9. Do đó $f$ là một ánh xạ đi từ M vào M. Hơn nữa dễ thấy $f$ là một song ánh. Từ đó suy ra $$ 2\sum_{N \in M}N=\sum_{N \in M}(N+f(N))=|M|.99…9 .$$ Vậy trung bình cộng của các số trong M là $99…9:2.$

Ví dụ 3. Cho tập S gồm tất cả các số nguyên dương trong đoạn $[1,2,…,2002]$. Gọi T là tập hợp tất cả các tập con khác rỗng của S. Với mỗi X thuộc T ký hiệu m(X) là trung bình cộng các phần tử thuộc X. Tính $$ m=\frac{\sum_{X \in T}m(X)}{|T|}. $$

Gợi ý

Xây dựng song ánh $f: T \longrightarrow T$ như sau: với mọi $X \in T $ đặt tương ứng $f(X)=\{2003-x: x \in X\}$.\\
Khi đó $m(X)+m(f(X))=2003$. Do đó $$2 \sum m(X)=\sum (m(X)+m( f(X)))=|T|.2003 \Rightarrow m=\dfrac{\sum m(X)}{|T|}=\dfrac{2003}{2}$$

Ví dụ 4.  Cho $X={1,2,…,n}$. Có bao nhiêu tập con $k$ phần tử của X sao cho trong mỗi tập con không chứa 2 số nguyên liên tiếp.

Gợi ý

Gọi A là tập tất cả các tập con $k $ phần tử của X mà trong mỗi tập không chứa 2 số nguyên liên tiếp và B là tập tất cả các tập con của tập $Y=\{1,2,…, n-(k-1) \}$. Ta xây dựng song ánh từ A đến B như sau: Lấy $S=\{s_1,s_2,…,s_k \} \in A$ (không mất tổng quát có thể giả sử $s_1<s_2<…<s_k$) đặt tương ứng với $f(S)=\{s_1, s_2-1, s_3-2,…, s_k-(k-1) \}$. Dễ chứng minh đây là một song ánh. Từ đó có $C^k_{n-k+1}$ tập thoả yêu cầu đề bài.

Bài tập rèn luyện 

Bài 1. Cho $X={ 1,2,..,n}$. Một tập con $S={s_1,s_2,…,s_k }$ của X ($s_1<s_2<…<s_k$) được gọi là \textit{m- tách được} $(m \in \mathbb{N})$ nếu $s_i-s_{i-1} \ge m; i=1,2,…,k$. Có bao nhiêu tập con m- tách được gồm $k$ phần tử của X, trong đó $0 \le k \le n-(m-1)(k-1)$.

Bài 2. Cho $X={1,2,…,n}$, với mỗi tập con khác rỗng $A_i={a_1,a_2,…,a_i }$ (không mất tổng quát giả sử $a_1>a_2>…>a_i$) ta định nghĩa \textit{tổng hỗn tạp} của $A_i$ là số $m(A_i)=a_1-a_2+a_3-… \pm a_i$. Tính $\sum \limits_{A_i \subset X} m(A_i)$.

Bài 3. Cho số nguyên dương $n$ và $d$ là một ước dương của $n$. Gọi S là tập tất cả những bộ $(x_1,x_2,…,x_n)$ nguyên dương thỏa $0 \le x_1 \le x_2 \le… \le x_n \le n$ và $d| x_1+x_2+…+x_n$. Chứng minh rằng có đúng một nửa các phần tử của S có tính chất $x_n=n$.

Bài 4. Gọi $a_n$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_n$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n+1}=2a_n$ với mọi số nguyên dương $n$.

Bài 5. Cho các số tự nhiên $k, n, m$ thỏa điều kiện $1<k \le n, m>1$. Hỏi có bao nhiêu chỉnh hợp chập $k: (a_1,a_2,…,a_k)$ của $n$ số tự nhiên đầu tiên mà mỗi chỉnh hợp đều thỏa mãn ít nhất một trong hai điều kiện sau:

i) Tồn tại $i, j \in {1,2,…,k}$ sao cho $i < j$ và $a_i>a_j$.

ii) Tồn tại $i \in {1,2,…,k}$ sao cho $a_i-i$ không chia hết cho $m$.

Bài 6. Cho các số nguyên dương $n, k, p$ với $k \ge 2$ và $k(p+1) \le n.$ Cho $n$ điểm phân biệt cùng nằm trên một đường tròn. Tô tất cả $n$ điểm đó bởi hai màu xanh, đỏ (mỗi điểm được tô bởi một màu) sao cho có đúng $k$ điểm được tô bởi màu xanh và trên mỗi cung tròn mà hai đầu mút là hai điểm màu xanh liên tiếp (tính theo chiều quay kim đồng hồ) đều có ít nhất $p$ điểm được tô màu đỏ. Hỏi có tất cả bao nhiêu cách tô khác nhau?

Bài 7. Gọi $a_n$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_n$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n+1}=2a_n$ với mọi số nguyên dương $n$.

Bài 8. Trong một hội nghị có $n$ nhà toán học. Biết rằng nếu hai nhà toán học nào đó quen nhau thì họ không quen chung thêm một người nào nữa, còn nếu hai nhà toán học này không quen nhau thì họ quen chung với đúng hai nhà toán học khác nữa. Chứng minh rằng $8n-7$ là số chính phương.

Bài 9. Trong một trại hè toán học có 40 học sinh. Biết rằng cứ 19 học sinh bất kỳ thì đều viết thư hỏi bài một học sinh khác (Nếu học sinh A viết thư hỏi bài học sinh B thì không nhất thiết học sinh B phải viết thư hỏi bài học sinh A và dĩ nhiên A cũng không viết thư hỏi chính mình). Chứng minh rằng trong trại hè này tồn tại một tập $T_0$ gồm 20 học sinh sao cho với mỗi $P \in T_0$ thì 19 người còn lại không đồng thời viết thư hỏi bài P.

Bài 10. Gọi M là số số nguyên dương trong hệ thập phân có $2n$ chữ số trong đó có $n$ chữ số 1 và $n$ chữ số 2. Gọi N là số số nguyên dương có $n$ chữ số trong hệ thập phân trong đó chỉ có các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh $|M|=|N|.$

(Hết phần 1)