*

Bài viết phụ thuộc 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.

Bạn đang xem: Phương pháp giải bài tập ánh xạ

Ánh xạ là một khái niệm khó khăn và đặc trưng trong toán học, tất 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 những bài toán tổ hợp.

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

Định nghĩa. đến hai tập vừa lòng $X$ và $Y$ khác rỗng. Một ánh xạ $f$ tự tập $X$ mang lại tập $Y$ là 1 quy tắc đặt tương xứng mỗi phần tử $x$ của $X$ với một cùng chỉ 1 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: mang lại ánh xạ $f: X longrightarrow Y$.

$y = f(x)$ được điện thoại tư vấn là ảnh của $x$.$f(X) = f(x)$ album ảnh của $f$.$y in Y$ thì $f^-1(y) = xin X$ được gọi là tạo ảnh của $y$.

Đơn ánh, toàn ánh, tuy nhiên ánh

Ánh xạ $f: X longrightarrow Y$ được hotline là đơn ánh đối với $a,b in X$ nhưng mà $a e b$ thì $f(a) e f(b)$. Nói một phương pháp khác ánh xạ $f$ là một trong những đơn ánh nếu còn chỉ nếu cùng với $a, b in X$ mà lại $f(a)=f(b)$ thì suy ra $a=b.$Ánh xạ $f:X longrightarrow Y$ được gọi là toàn ánh nếu với mỗi thành phần $y in Y$ hầu hết tồn tại một trong những phần tử $x in X$ thế nào cho $f(x)=y$. Bởi vậy $f$ là toàn ánh nếu còn chỉ nếu $f(X)=Y$.Ánh xạ $f: X longrightarrow Y$ được call là tuy vậy ánh giữa $X$ cùng $Y$ nếu còn chỉ nếu nó vừa là 1-1 ánh với vừa là toàn ánh. Bởi thế $f$ là tuy vậy ánh đối 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ạ cùng tập hợp

Cho $A = 1, 2,cdots, n $. $X$ là tập khác rỗng. Nếu tất cả một tuy vậy ánh từ tập $X$ đến $A$ thì ta nói $X$ tất cả $n$ bộ phận và kí hiệu $|X| = n$.

Nếu ko tồn tại tuy vậy ánh thì ta nói $X$ tất cả vô hạn phần tử.

Nếu tồn tại một song ánh từ bỏ $X$ vào tập các số từ bỏ nhiên, ta nói $X$ gồm 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à nhì tập vừa lòng hữu hạn.

Nếu bao gồm một đối kháng á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 bao gồm một tuy vậy á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$, hotline $P(X_n)$ là tập những tập bé của $X_n$, và $S_n$ là tập những dãy nhị phân gồm độ dài $n$. Tìm một tuy nhiên ánh tự $P(X_n)$ vào $S_n$, suy ra số tập con của $X_n$.


Đị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=egincases1, y_i in S&\0, y_i otin S.&endcases$$Ví dụ , ví như $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 đó là một song ánh tự $P(X)$ vào $Y$.Do đó theo nguyên lý song ánh ta tất 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 nhu cầu N phân tách hết mang đến 9 và các chữ số của N được lập tự $X=1,2,…,8$


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

Ta xây dừng một ánh xạ đi tự M mang lại M như sau: Với mỗi $N=overlinea_1a_2…a_2014 in M$ dặt $f(N)=overlineb_1,b_2,…,b_2014$ với $b_i=9-a_i$ với tất cả $i=1,2,…,2014$. Vì chưng $N+f(N)=99…9$ (2014 số 9) phân tách hết mang lại 9 với N phân tách hết mang đến 9 bắt buộc suy ra $f(N)$ cũng phân chia hết mang lại 9. Cho nên vì thế $f$ là một ánh xạ đi từ bỏ M vào M. Hơn nữa dễ thấy $f$ là một song ánh. Từ kia suy ra $$ 2sum_N in MN=sum_N in M(N+f(N))=|M|.99…9 .$$ Vậy trung bình cộng của những số vào 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 khúc $<1,2,…,2002>$. Call T là tập hợp toàn bộ các tập con khác trống rỗng của S. Với từng X nằm trong T ký kết hiệu m(X) là trung bình cùng các phần tử thuộc X. Tính $$ m=fracsum_X in Tm(X). $$


Xây dựng tuy nhiên ánh $f: T longrightarrow T$ như sau: với mọi $X in T $ đặt khớp ứng $f(X)=2003-x: x in X$.\Khi đó $m(X)+m(f(X))=2003$. Vì vậy $$2 sum m(X)=sum (m(X)+m( f(X)))=|T|.2003 Rightarrow m=dfracsum m(X)T=dfrac20032$$


Ví dụ 4.  mang đến $X=1,2,…,n$. Gồm bao nhiêu tập nhỏ $k$ phần tử của X làm thế nào cho trong mỗi tập bé không chứa 2 số nguyên liên tiếp.


Gọi A là tập toàn bộ các tập con $k $ bộ phận của X mà trong những tập không cất 2 số nguyên liên tục và B là tập toàn bộ các tập nhỏ của tập $Y=1,2,…, n-(k-1) $. Ta xây dựng tuy nhiên ánh tự A mang lại B như sau: lấy $S=s_1,s_2,…,s_k in A$ (không mất tổng quát hoàn toàn có thể giả sử $s_1a_2>…>a_i$) ta khái niệm extittổng láo 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. đến số nguyên dương $n$ cùng $d$ là 1 ước dương của $n$. điện thoại tư vấn 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$ cùng $d| x_1+x_2+…+x_n$. Chứng minh rằng bao gồm đúng một phần hai các thành phần của S có đặc thù $x_n=n$.

Bài 4. hotline $a_n$ là số các xâu nhị phân độ nhiều năm $n$ không chứa ba bit 0, 1, 0 liên tiếp. điện thoại tư vấn $b_n$ là số các xâu nhị phân độ lâu năm $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 đa số số nguyên dương $n$.

Bài 5. cho các số thoải mái và tự nhiên $k, n, m$ thỏa đk $11$. Hỏi có bao nhiêu chỉnh thích hợp chập $k: (a_1,a_2,…,a_k)$ của $n$ số từ bỏ nhiên thứ nhất mà từng chỉnh hợp đều thỏa mãn ít nhất 1 trong các hai điều kiện sau:

i) sống thọ $i, j in 1,2,…,k$ làm sao để cho $i a_j$.

ii) trường tồn $i in 1,2,…,k$ sao để cho $a_i-i$ không chia hết đến $m$.

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

Bài 7. điện thoại tư vấn $a_n$ là số những xâu nhị phân độ nhiều năm $n$ ko chứa cha bit 0, 1, 0 liên tiếp. Call $b_n$ là số những xâu nhị phân độ lâu năm $n$ chứa tư bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng tỏ rằng $b_n+1=2a_n$ với đa số số nguyên dương $n$.

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

Bài 9. vào một trại hè toán học tất cả 40 học sinh. Hiểu được cứ 19 học sinh ngẫu nhiên thì đều viết thư hỏi bài một học sinh khác (Nếu học viên A viết thư hỏi bài học viên B thì không tốt nhất thiết học viên B yêu cầu viết thư hỏi bài học viên A và tất nhiên A cũng không viết thư hỏi chính mình). Chứng tỏ rằng vào trại hè này sống thọ một tập $T_0$ tất cả 20 học viên sao mang đến với từng $P in T_0$ thì 19 người còn lại không đồng thời viết thư hỏi bài xích P.

Xem thêm: Kính Mắt 2 Lớp Nam - Kính Cận Râm Tháo Lắp Tj013

Bài 10. hotline M là số số nguyên dương vào hệ thập phân bao gồm $2n$ chữ số trong số đó có $n$ chữ hàng đầu và $n$ chữ số 2. Gọi N là số số nguyên dương tất cả $n$ chữ số vào hệ thập phân trong các số ấy chỉ có các chữ số 1, 2, 3, 4 với số chữ số 1 bằng số chữ số 2. Minh chứng $|M|=|N|.$