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)